Listado completo de tutoriales

72 - Colecciones: Queue y PriorityQueue


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:

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.

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:

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() + "-");

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:

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);
    }
}

Problema propuesto

  1. 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 8 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.

Solución

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);
    }
}

Retornar