Colas: la estructura FIFO que ordena al mundo (y a tus procesos)

Si la pila es LIFO —el último que entra, el primero que sale—, la cola es lo contrario: FIFO, First In, First Out. El primero que llega es el primero que se atiende. Como una fila en el banco, o como la cola del pan, o como las tareas pendientes en una impresora.

En software, las colas son el mecanismo natural para procesar eventos en orden, distribuir trabajo entre workers, implementar comunicación asíncrona y recorrer estructuras por niveles. Sin ellas, RabbitMQ, Kafka, las task queues de Laravel o las message queues de Android no existirían.

Este es el cuarto artículo de Por dentro de las estructuras. Ya vimos arrays, listas enlazadas y pilas; ahora le toca a la cola.

La idea central: FIFO

Una cola tiene dos extremos:

• Front (o head): el elemento que lleva más tiempo, el próximo en salir.

• Rear (o tail): donde se agregan los nuevos.

Y dos operaciones principales:

• enqueue(x): añadir al final.

• dequeue(): sacar el primero.

Visualmente:

dequeue ← [A] [B] [C] [D] ← enqueue
         front          rear

Llega E: [A] [B] [C] [D] [E]. Se llama dequeue: sale A, queda [B] [C] [D] [E].

Ese orden natural explica por qué las colas son omnipresentes: si queremos garantizar que los mensajes, peticiones o tareas se procesen en el orden en el que llegaron, FIFO es la política que necesitamos.

Cómo se vería en memoria

Hay dos implementaciones clásicas:

1. Sobre una lista enlazada. Mantenemos dos punteros, head y tail. Enqueue agrega al tail (O(1)), dequeue quita del head (O(1)). Cada nodo vive disperso en el heap:

head → [A|•] → [B|•] → [C|•] → [D|nil] ← tail

2. Sobre un array circular. Reservamos un buffer fijo y mantenemos dos índices (front y rear) que avanzan con aritmética modular. Cuando rear llega al final, "rebota" al inicio, reutilizando el hueco que dejó el front:

posición:  0    1    2    3    4    5    6    7
array:   [ _ ][ B ][ C ][ D ][ E ][ _ ][ _ ][ _ ]
              ↑front              ↑rear

Si no fuera circular, cada dequeue dejaría huecos al inicio y tendríamos que correr el array entero (O(n)). La circularidad es lo que permite O(1) en ambos extremos.

Implementación en PHP

PHP no trae una clase Queue nativa pero sí una SplQueue en la Standard PHP Library, que está implementada como una lista doblemente enlazada:

$cola = new SplQueue();

$cola->enqueue("A");
$cola->enqueue("B");
$cola->enqueue("C");

echo $cola->dequeue(); // "A"
echo $cola->dequeue(); // "B"
echo $cola->count();   // 1

Si no quieres depender de SplQueue, puedes simularla con funciones de array: array_push para enqueue y array_shift para dequeue. Funciona, pero cuidado: array_shift reindexa el array completo y es O(n). Para colas grandes, úsalo solo si el tamaño es pequeño o si no te importa la complejidad.

$cola = [];
array_push($cola, "A");
array_push($cola, "B");
$primero = array_shift($cola); // "A", pero O(n)

Una implementación manual sobre lista enlazada quedaría así:

class NodoCola {
    public mixed $valor;
    public ?NodoCola $siguiente = null;

    public function __construct(mixed $valor) {
        $this->valor = $valor;
    }
}

class Cola {
    private ?NodoCola $frente = null;
    private ?NodoCola $final = null;
    private int $tamano = 0;

    public function enqueue(mixed $valor): void {
        $nodo = new NodoCola($valor);
        if ($this->final === null) {
            $this->frente = $nodo;
            $this->final = $nodo;
        } else {
            $this->final->siguiente = $nodo;
            $this->final = $nodo;
        }
        $this->tamano++;
    }

    public function dequeue(): mixed {
        if ($this->frente === null) {
            throw new RuntimeException("Cola vacía");
        }
        $valor = $this->frente->valor;
        $this->frente = $this->frente->siguiente;
        if ($this->frente === null) {
            $this->final = null;
        }
        $this->tamano--;
        return $valor;
    }

    public function peek(): mixed {
        return $this->frente?->valor;
    }

    public function estaVacia(): bool {
        return $this->frente === null;
    }
}

Implementación en Java

En Java la cosa está bien resuelta: la interfaz Queue tiene varias implementaciones; la recomendada moderna es ArrayDeque, no LinkedList.

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> cola = new ArrayDeque<>();
cola.offer("A");      // enqueue
cola.offer("B");
cola.offer("C");

String primero = cola.poll();   // "A" (dequeue)
String siguiente = cola.peek(); // "B" (sin sacar)

La interfaz Queue tiene dos familias de métodos:

OperaciónLanza excepciónDevuelve null/falseenqueueadd(x)offer(x)dequeueremove()poll()peekelement()peek()

Usa offer/poll/peek cuando la cola puede estar vacía o llena (en colas acotadas); usa add/remove/element cuando una falla indica un bug grave.

¿Por qué ArrayDeque y no LinkedList?

Ambas implementan Queue, pero:

• ArrayDeque usa un array circular redimensionable. Tiene mejor localidad de cache, menos overhead por nodo (no tiene que guardar punteros), menos presión sobre el GC. Operaciones O(1) amortizado en ambos extremos.

• LinkedList es una lista doblemente enlazada. Cada nodo es un objeto en el heap con dos referencias y un valor. Más lenta en la práctica.

Para colas (y pilas) generales, ArrayDeque es la elección correcta el 95% del tiempo. LinkedList solo gana cuando necesitas acceso por índice barato durante el uso como List, pero eso ya no es una cola.

Implementación manual sobre array circular

public class ColaCircular {
    private int[] datos;
    private int frente, final_, tamano;

    public ColaCircular(int capacidad) {
        datos = new int[capacidad];
        frente = 0;
        final_ = -1;
        tamano = 0;
    }

    public void enqueue(int valor) {
        if (tamano == datos.length) {
            throw new IllegalStateException("Cola llena");
        }
        final_ = (final_ + 1) % datos.length;
        datos[final_] = valor;
        tamano++;
    }

    public int dequeue() {
        if (tamano == 0) throw new IllegalStateException("Cola vacía");
        int valor = datos[frente];
        frente = (frente + 1) % datos.length;
        tamano--;
        return valor;
    }

    public int peek() {
        if (tamano == 0) throw new IllegalStateException("Cola vacía");
        return datos[frente];
    }
}

Nota el uso de % datos.length: esa es la aritmética modular que hace al buffer "circular".

Operaciones y su costo

OperaciónLista enlazadaArray circularenqueueO(1)O(1) amortizadodequeueO(1)O(1)peekO(1)O(1)Buscar un elementoO(n)O(n)EspacioO(n) + overhead por nodoO(capacidad)

El "amortizado" en array circular se debe a que, cuando el buffer se llena, hay que redimensionarlo (copiar a uno más grande), lo que es O(n). Pero como ese costo se distribuye entre muchas operaciones, el promedio por operación sigue siendo O(1).

Variantes importantes

Deque (double-ended queue)

Permite enqueue y dequeue en ambos extremos. ArrayDeque es, como su nombre indica, un deque. Útil cuando necesitas flexibilidad: la puedes usar como pila o como cola, o como ambas simultáneamente.

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1); // añade al frente
deque.offerLast(2);  // añade al final
deque.pollFirst();   // saca del frente
deque.pollLast();    // saca del final

Cola circular acotada

La implementación que vimos arriba con array fijo. Se usa en sistemas donde la memoria es un recurso crítico (embedded, kernels, drivers) o cuando quieres un tope natural (ej. buffer de audio, log rotativo).

Cola de prioridad (priority queue)

No es FIFO estricta: cada elemento tiene una prioridad y se extrae siempre el de mayor (o menor) prioridad. Se implementa normalmente con un heap binario, lo que da O(log n) para enqueue y dequeue.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.poll(); // 1 (el menor)
pq.poll(); // 3
pq.poll(); // 5

Las priority queues son la base de Dijkstra, A*, schedulers de sistemas operativos y cualquier cosa que necesite "atender al más urgente".

Colas concurrentes

En sistemas multihilo, las colas estándar no son thread-safe. Java provee:

• ConcurrentLinkedQueue — cola no bloqueante basada en compare-and-swap.

• ArrayBlockingQueue / LinkedBlockingQueue — colas con bloqueo, ideales para patrones producer-consumer.

• LinkedBlockingDeque — deque con bloqueo.

Si tienes varios hilos metiendo y sacando mensajes, no uses ArrayDeque: necesitas una de estas.

Ventajas y desventajas

Ventajas:

• Orden natural FIFO, indispensable para procesamiento justo.

• Operaciones O(1) en los extremos.

• Separa el productor del consumidor (útil para asincronía).

• Variantes para casi cualquier necesidad (deque, circular, priority, concurrente).

Desventajas:

• Acceso solo por los extremos. No puedes indexar ni buscar sin recorrer.

• Si la capacidad es fija, puede desbordarse; si es dinámica, hay coste amortizado por redimensionamiento.

• En la versión con lista enlazada, overhead por nodo.

Casos de uso reales

1. Schedulers del sistema operativo: el kernel mantiene una cola de procesos listos para ejecutar.

2. Message queues (RabbitMQ, Kafka, SQS, Redis Streams): son colas distribuidas que garantizan orden y desacoplamiento productor/consumidor.

3. Task queues en frameworks web (Laravel Queues, Sidekiq, Celery): encolan jobs pesados para que workers en background los procesen.

4. Buffers de I/O: teclado, red, streams de audio/video usan colas circulares.

5. BFS (Breadth-First Search): el algoritmo de recorrido por niveles usa una cola para saber qué nodo visitar después. Lo veremos en la Serie 3.

6. Impresoras y spoolers: los trabajos de impresión se procesan en orden de llegada.

7. Simulaciones: colas de eventos discretos (discrete-event simulation) modelan sistemas como tráfico, redes o procesos industriales.

Cómo recorrer una cola

A diferencia de un array, una cola no está pensada para recorrerse "al vuelo"; sus operaciones primarias son enqueue/dequeue. Pero en Java, Queue extiende Collection, así que puedes iterar con un for-each:

Queue<String> cola = new ArrayDeque<>(List.of("A", "B", "C"));
for (String s : cola) {
    System.out.println(s); // A, B, C
}

Importante: iterar no vacía la cola. Si quieres consumirla, haz un while (!cola.isEmpty()) cola.poll();.

En PHP con SplQueue puedes iterar con foreach porque implementa Iterator:

foreach ($cola as $item) {
    echo $item;
}

Ejemplo completo: simulador de turnos

Imagina un banco con una sola ventanilla. Clientes llegan, se les atiende en orden de llegada:

import java.util.ArrayDeque;
import java.util.Queue;

class Cliente {
    String nombre;
    int tiempoServicio;

    Cliente(String nombre, int tiempoServicio) {
        this.nombre = nombre;
        this.tiempoServicio = tiempoServicio;
    }
}

public class Banco {
    public static void main(String[] args) {
        Queue<Cliente> cola = new ArrayDeque<>();
        cola.offer(new Cliente("Ana", 3));
        cola.offer(new Cliente("Bruno", 5));
        cola.offer(new Cliente("Clara", 2));

        int tiempoTotal = 0;
        while (!cola.isEmpty()) {
            Cliente c = cola.poll();
            System.out.printf("Atendiendo a %s (%d min)%n", c.nombre, c.tiempoServicio);
            tiempoTotal += c.tiempoServicio;
        }
        System.out.println("Tiempo total: " + tiempoTotal + " min");
    }
}

Salida:

Atendiendo a Ana (3 min)
Atendiendo a Bruno (5 min)
Atendiendo a Clara (2 min)
Tiempo total: 10 min

Este esqueleto es la base de cualquier simulación de turnos, call center, cola de soporte o dispatcher de tareas.

Errores comunes

1. Usar List.remove(0) como dequeue

Si tienes un ArrayList y haces list.remove(0), funciona pero es O(n): Java tiene que correr todos los elementos una posición a la izquierda. Para cola, usa ArrayDeque o LinkedList vía la interfaz Queue.

2. Confundir add y offer

En colas acotadas (como ArrayBlockingQueue), add lanza IllegalStateException si está llena, mientras que offer devuelve false. Elige según si el desbordamiento es un bug o una condición esperada.

3. No manejar la cola vacía

poll() devuelve null si la cola está vacía, pero remove() lanza NoSuchElementException. Hay que decidir cuál usar y ser consistente.

4. Usar la misma cola desde varios hilos sin sincronización

ArrayDeque no es thread-safe. Si dos hilos hacen offer simultáneamente, el estado interno se corrompe. Para escenarios concurrentes usa ConcurrentLinkedQueue o las variantes bloqueantes.

5. Cola de prioridad no respeta el orden de inserción para elementos iguales

PriorityQueue no es estable: si dos elementos tienen la misma prioridad, no hay garantía de orden entre ellos. Si necesitas estabilidad, añade un tiebreaker (timestamp o contador) a la prioridad.

6. Olvidar vaciar colas en tareas de larga duración

En un servidor que procesa mensajes, si las colas internas crecen más rápido que el consumidor, terminas con un OutOfMemoryError. Monitorea el tamaño y aplica backpressure (rechazar o demorar nuevos productores).

Resumen

Una cola es la estructura FIFO: el primero que entra es el primero que sale. Se implementa con lista enlazada (dos punteros, head y tail) o con array circular (dos índices y aritmética modular). Ambas ofrecen enqueue y dequeue en O(1).

En PHP, usa SplQueue o implementa sobre lista enlazada; en Java, ArrayDeque vía la interfaz Queue es la elección moderna por defecto. Para concurrencia, usa ConcurrentLinkedQueue o ArrayBlockingQueue. Para prioridad, PriorityQueue.

Las colas son la base de message brokers, schedulers, buffers de I/O, BFS y cualquier sistema que procese eventos en orden.

En el siguiente artículo entramos a la estructura que quizá más use cualquier lenguaje moderno detrás de escena: las tablas hash, que transforman búsquedas O(n) en O(1) promedio mediante una función matemática astuta.