Listado completo de tutoriales
72 - Colecciones: Queue y PriorityQueue |
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.
import 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.
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:
import 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() + "-");
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)
import 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);
}
}
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:
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);
}
}