Queue
Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out - primero en entrar primero en salir)
Confeccionaremos un programa que permita utilizar la interfaz Queue y mediante la clase LinkedList administre la lista tipo cola.
Programa:
Ver videoimport java.util.LinkedList; import java.util.Queue; public class PruebaQueue { public static void main(String[] args) { Queue<String> cola1 = new LinkedList<String>(); System.out.println("Insertamos tres elementos en la cola: juan, ana y luis"); cola1.add("juan"); cola1.add("ana"); cola1.add("luis"); System.out.println("Cantidad de elementos en la cola:" + cola1.size()); System.out.println("Extraemos un elemento de la cola:" + cola1.poll()); System.out.println("Cantidad de elementos en la cola:" + cola1.size()); System.out.println("Consultamos el primer elemento de la cola sin extraerlo:" + cola1.peek()); System.out.println("Cantidad de elementos en la cola:" + cola1.size()); System.out.println("Extraemos uno a un cada elemento de la cola mientras no este vacía:"); while (!cola1.isEmpty()) System.out.print(cola1.poll() + "-"); System.out.println(); Queue<Integer> cola2 = new LinkedList<Integer>(); cola2.add(70); cola2.add(120); cola2.add(6); System.out.println("Imprimimos la cola de enteros"); for (Integer elemento : cola2) System.out.print(elemento + "-"); System.out.println(); System.out.println("Borramos toda la cola"); cola2.clear(); System.out.println("Cantidad de elementos en la cola de enteros:" + cola2.size()); } }
La diferencia con respecto a la administración de pilas en Java es que para trabajar con colas debemos crear un objeto de la clase LinkedList e implementar la interfaz Queue:
Queue<String> cola1 = new LinkedList<String>();
La clase LinkedList implementa la interfaz Queue que es la que declara los método principales para trabajar una cola.
Añadimos elementos al final de la cola mediante el método 'add':
cola1.add("juan"); cola1.add("ana"); cola1.add("luis");
Para conocer la cantidad disponemos del método size():
System.out.println("Cantidad de elementos en la cola:" + cola1.size());
Para extraer el nodo de principio de la lista tipo cola lo hacemos mediante el método 'poll':
System.out.println("Extraemos un elemento de la cola:" + cola1.poll());
Si queremos conocer el objeto primero de la cola sin extraerlo lo hacemos mediante el método 'peek':
System.out.println("Consultamos el primer elemento de la cola sin extraerlo:" + cola1.peek());
Para conocer si la cola se encuentra vacía llamamos al método 'isEmpty':
while (!cola1.isEmpty()) System.out.print(cola1.poll() + "-");
Podemos utilizar un for para recorrer todos los elementos de la colección de tipo Queue con la siguiente sintaxis (no se eliminan los elementos de la cola):
for (Integer elemento : cola2) System.out.print(elemento + "-");
Para eliminar todos los elementos de una pila empleamos el método clear:
cola2.clear();
Más datos podemos conseguir visitando la documentación oficial de la interfaz Queue.
PriorityQueue
Una variante de una cola clásica la implementa la clase PriorityQueue. Cuando se agregan elementos a la cola se organiza según su valor, por ejemplo si es un número se ingresan de menor a mayor.
Veamos un ejemplo como se organizan los valores en la cola con prioridad:
Programa:
Ver videoimport java.util.PriorityQueue; public class PruebaPriorityQueue { public static void main(String[] args) { PriorityQueue<Integer> cola1 = new PriorityQueue<Integer>(); cola1.add(70); cola1.add(120); cola1.add(6); System.out.println("Imprimimos la cola con prioridades de enteros"); while (!cola1.isEmpty()) System.out.print(cola1.poll() + "-"); } }
Creamos un objeto de la clase PriorityQueue que almacene objetos de la clase Integer:
PriorityQueue<Integer> cola1 = new PriorityQueue<Integer>();
Cargamos tres objetos en la cola de prioridad:
cola1.add(70); cola1.add(120); cola1.add(6);
Mediante un while comenzamos a recuperar los elementos de la cola con prioridad y podemos comprobar que el primero de la cola es el que tiene el valor 6, luego el 70 y finalmente el 120:
while (!cola1.isEmpty()) System.out.print(cola1.poll() + "-");
Problema de aplicación de una cola
Cuando implementamos desde cero el concepto de una cola con el lenguaje Java desarrollamos una serie de ejercicios de aplicación. Los volveremos a codificar pero ahora utilizando la interfaz Queue y la clase LinkedList.
Planteo del problema:
Este práctico tiene por objetivo mostrar la importancia de las colas en las Ciencias de la Computación y más precisamente en las simulaciones.
Las simulaciones permiten analizar situaciones de la realidad sin la necesidad de ejecutarlas realmente. Tiene el beneficio que su costo es muy inferior a hacer pruebas en la realidad.
Desarrollar un programa para la simulación de un cajero automático.
Se cuenta con la siguiente información:
- Llegan clientes a la puerta del cajero cada 2 ó 3 minutos.
- Cada cliente tarda entre 2 y 4 minutos para ser atendido.
Obtener la siguiente información:
1 - Cantidad de clientes que se atienden en 10 horas.
2 - Cantidad de clientes que hay en cola después de 10 horas.
3 - Hora de llegada del primer cliente que no es atendido luego de 10 horas (es decir la persona que está primera en la cola cuando se cumplen 10 horas)
Programa:
Ver videoimport javax.swing.*; import java.awt.event.*; import java.util.LinkedList; import java.util.Queue; public class Cajero extends JFrame implements ActionListener { private JLabel l1, l2, l3; private JButton boton1; public Cajero() { setLayout(null); boton1 = new JButton("Activar Simulación"); boton1.setBounds(10, 10, 180, 30); add(boton1); boton1.addActionListener(this); l1 = new JLabel("Atendidos:"); l1.setBounds(10, 50, 300, 30); add(l1); l2 = new JLabel("En cola:"); l2.setBounds(10, 90, 300, 30); add(l2); l3 = new JLabel("Minuto de llegada:"); l3.setBounds(10, 130, 400, 30); add(l3); } public void actionPerformed(ActionEvent e) { if (e.getSource() == boton1) { simulacion(); } } public void simulacion() { int estado = 0; int llegada = 2 + (int) (Math.random() * 2); int salida = -1; int cantAtendidas = 0; Queue<Integer> cola = new LinkedList<Integer>(); for (int minuto = 0; minuto < 600; minuto++) { if (llegada == minuto) { if (estado == 0) { estado = 1; salida = minuto + 2 + (int) (Math.random() * 3); } else { cola.add(minuto); } llegada = minuto + 2 + (int) (Math.random() * 2); } if (salida == minuto) { estado = 0; cantAtendidas++; if (!cola.isEmpty()) { cola.poll(); estado = 1; salida = minuto + 2 + (int) (Math.random() * 3); } } } l1.setText("Atendidos:" + String.valueOf(cantAtendidas)); l2.setText("En cola" + String.valueOf(cola.size())); if (!cola.isEmpty()) l3.setText("Minuto llegada:" + String.valueOf(cola.peek())); } public static void main(String[] ar) { Cajero cajero1 = new Cajero(); cajero1.setBounds(0, 0, 340, 250); cajero1.setDefaultCloseOperation(EXIT_ON_CLOSE); cajero1.setVisible(true); } }
Problema propuesto
Un supermercado tiene tres cajas para la atención de los clientes.
Las cajeras tardan entre 7 y 11 minutos para la atención de cada cliente.
Los clientes llegan a la zona de cajas cada 2 ó 3 minutos. (Cuando el cliente llega, si todas las cajas tienen 6 personas, el cliente se marcha del supermercado)
Cuando el cliente llega a la zona de cajas elige la caja con una cola menor.Realizar una simulación durante 10 horas y obtener la siguiente información:
Ver video
a - Cantidad de clientes atendidos por cada caja.
b - Cantidad de clientes que se marcharon sin hacer compras.
c - Tiempo promedio en cola.
import javax.swing.*; import java.awt.event.*; import java.util.LinkedList; import java.util.Queue; public class Supermercado extends JFrame implements ActionListener { private JButton boton1; private JLabel l1, l2, l3; public Supermercado() { setLayout(null); boton1 = new JButton("Activar Simulación"); boton1.setBounds(10, 10, 180, 30); add(boton1); boton1.addActionListener(this); l1 = new JLabel("Clientes atendidos por caja:"); l1.setBounds(10, 50, 400, 30); add(l1); l2 = new JLabel("Se marchan sin hacer compras:"); l2.setBounds(10, 90, 400, 30); add(l2); l3 = new JLabel("Tiempo promedio en cola:"); l3.setBounds(10, 130, 400, 30); add(l3); } public void actionPerformed(ActionEvent e) { if (e.getSource() == boton1) { simulacion(); } } public void simulacion() { int estado1 = 0, estado2 = 0, estado3 = 0; int marchan = 0; int llegada = 2 + (int) (Math.random() * 2); int salida1 = -1, salida2 = -1, salida3 = -1; int cantAte1 = 0, cantAte2 = 0, cantAte3 = 0; int tiempoEnCola = 0; int cantidadEnCola = 0; Queue<Integer> cola1 = new LinkedList<Integer>(); Queue<Integer> cola2 = new LinkedList<Integer>(); Queue<Integer> cola3 = new LinkedList<Integer>(); for (int minuto = 0; minuto < 600; minuto++) { if (llegada == minuto) { if (estado1 == 0) { estado1 = 1; salida1 = minuto + 7 + (int) (Math.random() * 5); } else { if (estado2 == 0) { estado2 = 1; salida2 = minuto + 7 + (int) (Math.random() * 5); } else { if (estado3 == 0) { estado3 = 1; salida3 = minuto + 7 + (int) (Math.random() * 5); } else { if (cola1.size() == 6 && cola2.size() == 6 && cola3.size() == 6) { marchan++; } else { if (cola1.size() <= cola2.size() && cola1.size() <= cola3.size()) { cola1.add(minuto); } else { if (cola2.size() <= cola3.size()) { cola2.add(minuto); } else { cola3.add(minuto); } } } } } } llegada = minuto + 2 + (int) (Math.random() * 2); } if (salida1 == minuto) { cantAte1++; estado1 = 0; if (!cola1.isEmpty()) { estado1 = 1; int m = cola1.poll(); salida1 = minuto + 7 + (int) (Math.random() * 5); tiempoEnCola = tiempoEnCola + (minuto - m); cantidadEnCola++; } } if (salida2 == minuto) { cantAte2++; estado2 = 0; if (!cola2.isEmpty()) { estado2 = 1; int m = cola2.poll(); salida2 = minuto + 7 + (int) (Math.random() * 5); tiempoEnCola = tiempoEnCola + (minuto - m); cantidadEnCola++; } } if (salida3 == minuto) { cantAte3++; estado3 = 0; if (!cola3.isEmpty()) { estado3 = 1; int m = cola3.poll(); salida3 = minuto + 7 + (int) (Math.random() * 5); tiempoEnCola = tiempoEnCola + (minuto - m); cantidadEnCola++; } } } l1.setText("Clientes atendidos por caja: caja1=" + cantAte1 + " caja2=" + cantAte2 + " caja3=" + cantAte3); l2.setText("Se marchan sin hacer compras:" + marchan); if (cantidadEnCola > 0) { int tiempoPromedio = tiempoEnCola / cantidadEnCola; l3.setText("Tiempo promedio en cola:" + tiempoPromedio); } } public static void main(String[] ar) { Supermercado super1 = new Supermercado(); super1.setBounds(0, 0, 390, 250); super1.setDefaultCloseOperation(EXIT_ON_CLOSE); super1.setVisible(true); } }
No hay comentarios:
Publicar un comentario