Colas en Java

Las colas son estructuras de datos similares a las pilas pero con un comportamiento diferente, esta también es una estructura básica puesto que se usa en muchos algoritmos y situaciones en programación.

Visita la página de listas para mayor detalle sobre esta estructura básica.

1. ¿Qué es una cola?

Una cola es una estructura de datos enlazada que sigue una disciplina FIFO (First In, First Out – Primero en entrar, Primero en salir) en la cual el primer elemento que entra es el primero en ser retirado, adicionalmente la estructura, aunque continua siendo una estructura lineal no se puede manipular cualquier elemento como sucedía con las listas, en las colas solamente se puede acceder al elemento que esta en la parte frontal, de manera que si se quiere alcanzar el último elemento, primero se requerirá desencolar todos los otros elementos. La siguiente figura muestra gráficamente una cola.

Las colas tienen muchos usos en informática, un ejemplo sencillo consiste en la representación de una fila de un banco o el procesamiento secuencial de una serie de actividades, por ejemplo el envío de notificaciones de correo electrónico en una aplicación transaccional.

2. Implementación de una cola

La implementación de una cola enlazada utiliza la misma clase Node que se utilizó en las listas enlazadas, la diferencia radica que en los métodos que se utilizan para manipular la cola y que se resumen a continuación:

• add: este método se encarga de agregar un nuevo elemento en la parte de atrás (último) de la cola.
• remove: este método remueve el elemento del frente de la cola (primer elemento) y lo devuelve.

2.1. Interface

A continuación se muestra el código correspondiente a las operaciones de una cola con su respectiva documentación.

package queues;
/**
 * Provee las acciones que se pueden realizar con una cola
 * @author ochoscar
 * @param < T > Tipo genérico de los cuales se almacenaran elementos dentro de la cola
 */
public interface IQueue< T > {
    /**
     * Método que verifica si la cola esta vacía
     * @return Devuelve true si la cola esta
     * vacía y false en caso contrario
     */
    public boolean isEmpty();
    /**
     * Método que determina el tamaño de la cola
     * @return Devuelve un entero que indica el tamaño de la cola
     */
    public int size();
    /**
     * Agrega un elemento al final de la cola
     * @param item Item de tipo genérico a ser agregado a la cola
     * @return Devuelve la misma cola que llamo al método
     */
    public IQueue add(T item);
    /**
     * Remueve un elemento del frente de la cola y lo devuelve para su manipulación
     * @return El elemento que se encontraba al frente de la cola
     */
    public T remove();
}

2.2. Clase Cola en Java

Las Colas de datos en Java se pueden implementar con la clase y consideraciones que se muestran a continuación.

La implementación de la interface anterior se encuentra en el siguiente código. Observe que se referencia tanto el primer como el último elemento a fin de realizar las operaciones de agregado y eliminación de forma óptima en cuanto a rendimiento se refiere. Algo importante también es que las operaciones de la cola no requieren de ciclos, por lo tanto la estructura se vuelve supremamente eficiente y así mismo no aporta mayor valor realizar una cola con arreglos, aunque es perfectamente posible.

package queues;
/**
 * Clase que encapsula las diferentes acciones de una cola enlazada
 * @author ochoscar
 * @param < T > Tipo genérico que contra los item de la cola
 */
public class Queue< T > implements IQueue< T > {
    ////////////////////
    // Atributos
    ////////////////////
    /** Referencia al primer nodo de la cola */
    private Node< T > front;
    /** Referencia al ultimo elemento de la cola */
    private Node< T > back;
    /** Tamaño de la cola */
    private int queueSize = 0;
    ////////////////////
    // Métodos
    ////////////////////
    /**
     * Método que verifica si la cola esta vacía
     * @return Devuelve true si la cola esta
     * vacía y false en caso contrario
     */
    @Override
    public boolean isEmpty() {
        return queueSize == 0;
    }
    /**
     * Método que determina el tamaño de la cola
     * @return Devuelve un entero que indica el tamaño de la cola
     */
    @Override
    public int size() {
        return queueSize;
    }
    /**
     * Agrega un elemento al final de la cola
     * @param item Item de tipo genérico a ser agregado a la cola
     * @return Devuelve la misma cola que llamo al método
     */
    @Override
    public IQueue add(T item) {
        Node< T > newNode = new Node(item, null);
        if(queueSize == 0) {
            front = back = newNode;
        } else {
            back.setNext(newNode);
            back = newNode;
        }
        queueSize++;
        return this;
    }
    /**
     * Remueve un elemento del frente de la cola y lo devuelve para su manipulación
     * @return El elemento que se encontraba al frente de la cola
     */
    public T remove() {
        if(queueSize == 0) return null;
        T item = front.getItem();
        front = front.getNext();
        if(front == null) back = null;
        queueSize--;
        return item;
    }
}

3. Artículos de Interés

Listas enlazadas en Java

Pilas en Java

Encapsulamiento en Java