Colas (Queues)

 Desde el punto de vista teórico una cola es un tipo de dato abstracto (TDA) que sigue el principio FIFO (first in, first out) que implica que el primer elemento en ser agregado en la cola es también el primero en ser removido de la misma.

En la imagen se observa una cola con tres elementos, cuando se inserta uno nuevo, este se coloca al final de la cola (elemento D).

Cuando se elimina un elemento, se remueve el primero en haber ingresado, en caso de la cola es el elemento A.

En el mundo real podemos encontrar este ejemplo en las colas de un banco, la cadena de impresión de documentos, etc.

En el caso de la cola en el banco, la primera persona en llegar es también la primera en irse (suponiendo una única ventanilla) y en los documentos a imprimir, la impresora imprime según el orden de llegada.

Queues en Java

Existen diversas colecciones que permite implementar de forma rápida y sencilla a las colas como la interfaz "Queue" o la clase "LinkedList"

El siguiente ejemplo ilustra como construir una cola, agregar elementos y luego irlos retirando. Para ello, se crea una colección llamada cola de tipo Queue con una implementación de lista enlazada (LinkedList) que almacena valores enteros.

package test;

import java.util.LinkedList;
import java.util.Queue;

public class Colas {

    public static void main(String[] args) {
        Queue<Integer> cola = new LinkedList<>();

        System.out.println("Agregando valores");
        for (int i = 0; i < 5; i++) {
            cola.add(i);
            System.out.println("Valor: " + i);
        }
        
        System.out.println("\nRetirando valores");
        while (cola.peek()!=null) {
            System.out.println("Valor: " + cola.poll());            
        }
    }
}

La salida del resultado sería:

Agregando valores
Valor: 0
Valor: 1
Valor: 2
Valor: 3
Valor: 4

Retirando valores
Valor: 0
Valor: 1
Valor: 2
Valor: 3
Valor: 4

El primer elemento en ser agregado es "0" y al retirar a los elementos, el primero en ser removido también es el "0" comprobando el principio FIFO.

Creando una clase Colas

La siguiente clase emula de forma simple el funcionamiento de una cola, para ello utiliza un array de tipo Object

package tda;

public class Colas {

    private Object[] data;
    private final int length;
    private int pointer;

    public Colas(int length) {
        this.length = length;
        this.data = new Object[length];
        this.pointer = -1;
    }

    public void add(Object element) {
        this.data[pointer+1] = element;
        pointer = (pointer < length - 1) ? pointer + 1 : pointer;
    }

    public Object[] getData() {
        return this.data;
    }

    public int getLength() {
        return length;
    }

    public Object pop() {
        Object value = this.data[0];
        for (int i = 0; i < data.length-1; i++) {
            data[i] = data[i+1];            
        }
        this.data[pointer] = null;
        pointer--;
        return value;
    }

}

Para comprobar el funcionamiento se utiliza lo siguiente:

package test;

import java.util.Arrays;
import tda.Colas;

public class TestColas {

    public static void main(String[] args) {
        Colas colaInt = new Colas(4);
        colaInt.add(0);
        colaInt.add(1);
        colaInt.add(2);
        colaInt.add(3);
        for (int i = 0; i < 4; i++) {
            System.out.println("Dato ingresado: "+colaInt.getData()[i]);
        }
        System.out.println("=================================");
        System.out.println("Sale: "+colaInt.pop());
        System.out.println("Sale: "+colaInt.pop());        
        System.out.println("Sale: "+colaInt.pop());
        System.out.println("=================================");
        colaInt.add(5); // Agregamos el 5
        System.out.println(Arrays.toString(colaInt.getData()));      
    }

}

La salida del resultado sería:

Dato ingresado: 0
Dato ingresado: 1
Dato ingresado: 2
Dato ingresado: 3
=================================
Sale: 0
Sale: 1
Sale: 2
=================================
[3, 5, null, null]

Se comprueba el principio FIFO al insertar primero al 0, el primero en ser retirado es el mismo 0