Skip to main content

Queue (Colas): FIFO, variantes (colas dobles, de prioridad)

Una cola (Queue) es una estructura de datos lineal que sigue el principio FIFO (First In, First Out), es decir, el primer elemento en entrar es el primero en salir.

Características​

  1. Tiene dos extremos:
    • Front (frente): por donde se eliminan los elementos.
    • Rear (final): por donde se insertan los elementos.
  2. Operaciones fundamentales:
    1. enqueue: Inserta un elemento en el final de la cola.
    2. dequeue: Elimina el elemento al frente de la cola.
    3. peek/front: Devuelve el elemento al frente sin eliminarlo.
    4. isEmpty: Verifica si la cola está vacía.

Ejemplo de FIFO​

Una fila en el banco: el primero que llega es el primero en ser atendido.

Variantes de Colas​

  1. Colas dobles (Deque - Double-Ended Queue):
    • Permiten inserciones y eliminaciones por ambos extremos.
    • Métodos adicionales:
      • enqueueFront: insertar al frente.
      • dequeueRear: eliminar del final.
  2. Colas de prioridad (Priority Queue):
    • Cada elemento tiene una prioridad asociada.
    • Al hacer dequeue, se elimina el elemento con mayor prioridad (no necesariamente el más antiguo).

Cola FIFO​

  • enqueue: Se inserta en el extremo Rear.
  • dequeue: Se elimina en el extremo Front.

Ejemplo Técnico​

Implementación con arrays:

QueueArray.java
public class QueueArray<T> {
    private Object[] elements;
    private int front, rear, size, capacity;

    public QueueArray(int capacity) {
        this.capacity = capacity;
        elements = new Object[capacity];
        front = size = 0;
        rear = -1;
    }

    public void enqueue(T data) {
        if (size == capacity) throw new RuntimeException("Queue overflow");
        rear = (rear + 1) % capacity;
        elements[rear] = data;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        T data = (T) elements[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return (T) elements[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Implementación con listas enlazadas:

QueueLinkedList.java
class Node<T> {
    T data;
    Node<T> next;
    Node(T data) { this.data = data; }
}

public class QueueLinkedList<T> {
    private Node<T> front, rear;

    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    public T dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        T data = front.data;
        front = front.next;
        if (front == null) rear = null;
        return data;
    }

    public T peek() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

Diagrama de Secuencia​

  1. El usuario solicita agregar un elemento a la cola (enqueue) con el valor 10.
  2. La cola crea una instancia de nodo con el valor 10.
  3. El nodo creado se almacena en la cola.
  4. Se valida si la cola está vacía.
  5. En caso de estar vacía, se establece el frente y el final de la cola en el nuevo nodo.
  6. Si no está vacía, se establece el siguiente nodo del final en el nuevo nodo.
  7. Luego, se actualiza el final.
  8. El usuario solicita agregar otro elemento a la cola (enqueue) con el valor 20.
  9. La cola crea una instancia de nodo con el valor 20.
  10. El nodo creado se almacena en la cola.
  11. Se establece que el siguiente nodo del final es el nuevo nodo.
  12. Se actualiza el final.
  13. El usuario solicita eliminar un elemento de la cola (dequeue).
  14. Se valida si la cola está vacía.
  15. En caso de estar vacía, se retorna un mensaje de desbordamiento.
  16. Si la cola no está vacía, se almacena el valor del frente en una variable temporal.
  17. El frente actualiza su valor con la referencia al nodo siguiente.
  18. Si el frente está vacío, entonces el final también se vacía.
  19. Se devuelve el elemento eliminado.

Aplicaciones Prácticas​

  • Sistemas operativos: planificación de procesos.
  • Colas de impresión: los documentos se imprimen en orden de llegada.
  • Redes: paquetes de datos procesados en orden de llegada.
  • Sistemas de atención al cliente: turnos FIFO.
  • Deque: usado en algoritmos de ventanas deslizantes (sliding window).
  • Priority Queue: usado en algoritmos como Dijkstra para encontrar caminos más cortos.

Buenas Prácticas​

  • SRP: La cola debe encargarse solo de la gestión de elementos FIFO.
  • Abstracción: Variantes (Deque, Priority Queue) deben implementarse como extensiones sin modificar la base.
  • Pruebas unitarias: Validar desbordamiento, subdesbordamiento y prioridades.
  • Interfaces claras: Métodos como enqueue, dequeue, peek y isEmpty facilitan el uso.

Referencias​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
  • Weiss, M. A. (2020). Data Structures and Algorithm Analysis in Java (4th ed.). Pearson.
  • McDowell, G. (2016). Cracking the Coding Interview. CareerCup.
  • Python 3
  • Jest