Colas y deques

De qué trata este capítulo

Una cola es la imagen invertida del stack. Donde un stack te entrega el elemento más nuevo, una cola te entrega el más viejo: primero en entrar, primero en salir. Ese es el orden que necesita todo lo que debe atenderse de manera justa, en el orden en que fue llegando: un spooler de impresión, una cola de tareas, la frontera pendiente de una búsqueda en anchura. En este capítulo construimos una cola y a su prima de dos extremos, el deque, sobre una lista doblemente ligada, para que toda operación en los extremos sea O(1); y luego vemos la forma más común en que la gente arruina las colas en Python, y cuánto cuesta.

Un poco de historia

Las colas son más viejas que las computadoras: vienen de las matemáticas de las filas de espera. En 1909 el ingeniero danés Agner Krarup Erlang, que trabajaba para la compañía telefónica de Copenhague, publicó el primer estudio sobre cómo esperan las llamadas a que se libere una línea, y con eso fundó lo que hoy llamamos teoría de colas. La unidad de tráfico telefónico, el erlang, lleva su nombre. Cuando llegaron las computadoras heredaron tanto las matemáticas como la estructura: los sistemas operativos encolan procesos que esperan CPU, las redes encolan paquetes que esperan un enlace, y las impresoras encolan trabajos que esperan la bandeja. La disciplina FIFO aparece en todos lados donde un recurso escaso atiende muchas peticiones, porque atenderlas en orden de llegada es la noción más simple de lo que es justo.

La intuición

Una cola es una fila en un mostrador. Te formas al final; te atienden por el frente; no te puedes meter. El que lleva más tiempo esperando pasa primero. Enqueue agrega al final, dequeue quita del frente, y esa es toda la interfaz.

Un deque — se pronuncia "dec", abreviatura de double-ended queue — relaja la regla y te deja agregar y quitar en ambos extremos. Esa sola generalización lo convierte en la navaja suiza de la familia: usa solo el final y es un stack; usa entrada por atrás y salida por el frente y es una cola. Como un deque puede hacer todo lo que hacen un stack o una cola, es la estructura que la librería estándar realmente incluye, y la que vas a usar en la práctica.

Complejidad: cómo escala

Construida sobre una lista doblemente ligada, cada operación toca únicamente un extremo, así que enqueue, dequeue y las cuatro operaciones del deque son $O(1)$: ligar o desligar un nodo y listo, sin recorrer nada ni mover nada. El espacio es $O(n)$. El puntero prev del capítulo de listas ligadas es lo que hace que sacar por atrás salga tan barato como por el frente; sin él, encontrar la nueva cola significaría recorrer toda la lista.

Aquí no hay recurrencia: el punto es que el costo se mantiene plano. La gráfica de abajo encola n elementos y luego desencola los n, midiendo nuestra cola contra la de la librería; ambas líneas son rectas, porque O(1) por operación significa trabajo total lineal:

En qué es buena y en qué no

Usa una cola siempre que importe el orden de llegada y solo agregues por un extremo y saques por el otro. Igual que con el stack, su restricción es su fuerza: FIFO es fácil de razonar y O(1) de mantener, y la generalización del deque cubre los casos donde necesitas ambos extremos sin perder la garantía de tiempo constante.

Lo que una cola no es: indexable ni buscable. No puedes pedir el quinto de la fila sin caminar hasta él. Y hay una trampa específica de Python que merece su propia advertencia, porque es facilísimo caer en ella y sale carísimo sin hacer ruido:

Los datos, o las entradas

La comparación le da a la cola justo el patrón que expone la trampa: encolar n elementos y luego desencolar los n. Ahí es exactamente donde list.pop(0) se vuelve cuadrático, así que hace visible la diferencia entre O(1) y O(n) por dequeue. La animación usa un guion diminuto escrito a mano, de ocho operaciones sobre una fila de cinco elementos, porque ahí lo que importa es el orden en que salen las cosas, no la velocidad.

Constrúyela, una función a la vez

El deque es la base. Empujar al final liga un nodo a la cola:

def push_back(self, value):
    """O(1): link a node onto the tail (the back of the line)."""
    node = _Node(value)
    node.prev = self._tail
    if self._tail is not None:
        self._tail.next = node
    else:
        self._head = node
    self._tail = node
    self._n += 1

Empujar al frente es el espejo: ligar a la cabeza.

def push_front(self, value):
    """O(1): link a node onto the head (the front of the line)."""
    node = _Node(value)
    node.next = self._head
    if self._head is not None:
        self._head.prev = node
    else:
        self._tail = node
    self._head = node
    self._n += 1

Sacar del frente quita la cabeza, en O(1), con solo mover el puntero de cabeza: sin recorrer nada, que es toda la ventaja sobre una lista.

def pop_front(self):
    """O(1): remove and return the front. No shifting — just move the head."""
    if self._head is None:
        raise IndexError("pop from empty deque")
    node = self._head
    self._head = node.next
    if self._head is not None:
        self._head.prev = None
    else:
        self._tail = None
    self._n -= 1
    return node.value

Y sacar por atrás es la operación que nos compra el puntero prev: quitar la cola igual de barato.

def pop_back(self):
    """O(1): remove and return the back — the payoff of the prev pointer."""
    if self._tail is None:
        raise IndexError("pop from empty deque")
    node = self._tail
    self._tail = node.prev
    if self._tail is not None:
        self._tail.next = None
    else:
        self._head = None
    self._n -= 1
    return node.value

La cola entonces es simplemente un deque con la interfaz reducida a FIFO: formarse al final, salir por el frente, nada intermedio.

class Queue:
    """A FIFO queue is just a deque with the operations restricted: you join at
    the back and leave from the front, and can't touch anything in between."""

    def __init__(self):
        self._d = Deque()

    def enqueue(self, value):
        self._d.push_back(value)      # join the back of the line

    def dequeue(self):
        return self._d.pop_front()    # the person who's waited longest goes first

    def __len__(self):
        return len(self._d)

    def to_list(self):
        return self._d.to_list()

Míralo funcionar

Aquí tienes una cola como una filita en un mostrador. El verde es el frente, el próximo en ser atendido; el azul es el final, el que acaba de llegar. Avanza paso a paso: los elementos se forman al final (azul), y cada dequeue toma el del frente (verde), el que lleva más tiempo esperando. Fíjate que el orden de salida coincide con el de entrada: A, B, C, D salen exactamente en la secuencia en que llegaron, que es toda la promesa de FIFO:

El código completo

Las dos versiones en un solo lugar; cambia entre ellas. La pestaña "desde cero" es nuestro Deque y la Queue construida encima. La pestaña de librería es collections.deque, la estructura doblemente ligada que de verdad vas a usar, más la versión con list.pop(0), que dejamos únicamente para mostrar qué no hacer.

"""A queue — first in, first out — and its two-ended cousin the deque, both built
on a doubly linked list so every end operation is O(1).

A queue is the mirror of the stack from the last chapter: instead of taking the
newest item, you take the oldest. That's the ordering you want any time work has
to be served in the order it arrived — a print spooler, a task queue, the frontier
of a breadth-first search.
"""


class _Node:
    __slots__ = ("value", "prev", "next")

    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


class Deque:
    """A double-ended queue on a doubly linked list: O(1) at BOTH ends. The prev
    pointer is what lets us pop from the back as cheaply as the front."""

    def __init__(self):
        self._head = None
        self._tail = None
        self._n = 0

    # region: push_back
    def push_back(self, value):
        """O(1): link a node onto the tail (the back of the line)."""
        node = _Node(value)
        node.prev = self._tail
        if self._tail is not None:
            self._tail.next = node
        else:
            self._head = node
        self._tail = node
        self._n += 1
    # endregion

    # region: push_front
    def push_front(self, value):
        """O(1): link a node onto the head (the front of the line)."""
        node = _Node(value)
        node.next = self._head
        if self._head is not None:
            self._head.prev = node
        else:
            self._tail = node
        self._head = node
        self._n += 1
    # endregion

    # region: pop_front
    def pop_front(self):
        """O(1): remove and return the front. No shifting — just move the head."""
        if self._head is None:
            raise IndexError("pop from empty deque")
        node = self._head
        self._head = node.next
        if self._head is not None:
            self._head.prev = None
        else:
            self._tail = None
        self._n -= 1
        return node.value
    # endregion

    # region: pop_back
    def pop_back(self):
        """O(1): remove and return the back — the payoff of the prev pointer."""
        if self._tail is None:
            raise IndexError("pop from empty deque")
        node = self._tail
        self._tail = node.prev
        if self._tail is not None:
            self._tail.next = None
        else:
            self._head = None
        self._n -= 1
        return node.value
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self._head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out


# region: queue
class Queue:
    """A FIFO queue is just a deque with the operations restricted: you join at
    the back and leave from the front, and can't touch anything in between."""

    def __init__(self):
        self._d = Deque()

    def enqueue(self, value):
        self._d.push_back(value)      # join the back of the line

    def dequeue(self):
        return self._d.pop_front()    # the person who's waited longest goes first

    def __len__(self):
        return len(self._d)

    def to_list(self):
        return self._d.to_list()
# endregion

"""collections.deque is the queue and deque you actually use in Python — a doubly
linked list of blocks with O(1) at both ends, exactly like ours but tuned in C.

The instructive comparison is the WRONG one: a plain list used as a queue. `append`
is fine, but taking from the front with `pop(0)` shifts every remaining element
one slot left — O(n) per dequeue, O(n²) to drain the queue. It's the single most
common accidental-quadratic bug in Python, and this chapter's face-off shows it.
"""
from collections import deque


# region: deque_queue
def run_queue_deque(ops):
    """FIFO on a deque: append to the back, popleft from the front. Both O(1)."""
    q = deque()
    out = []
    for op in ops:
        if op[0] == "enq":
            q.append(op[1])
        else:
            out.append(q.popleft())
    return out
# endregion


# region: list_queue
def run_queue_list(ops):
    """FIFO on a plain list — the anti-pattern. `pop(0)` is O(n) because every
    element after index 0 shifts left, so draining n items is O(n^2)."""
    q = []
    out = []
    for op in ops:
        if op[0] == "enq":
            q.append(op[1])
        else:
            out.append(q.pop(0))
    return out
# endregion

Desde cero vs. librería

Ahora la comparación completa, con el antipatrón de vuelta. Nuestra cola y el deque son ambos O(1) por operación, así que sus líneas se mantienen planas y abajo. La línea de list.pop(0) es la lección: se curva hacia arriba con fuerza, porque vaciar una lista desde el frente es O(n²):

Con 32000 elementos, el deque de la librería terminó en unos 2.2 ms, nuestra cola ligada en 12.5 ms, y el antipatrón de lista en 52.5 ms. Nuestra cola queda en medio por la razón de siempre: es O(1) como el deque, pero cada nodo es un objeto de Python aparte, con el overhead de los punteros y llamadas a métodos por operación, mientras que el deque liga bloques de elementos en C. Lo importante de verdad es cómo la línea de la lista se despega de las otras dos: esa es una diferencia de clase de complejidad, O(n²) contra O(n), y es exactamente el bug del que habla la advertencia de arriba.

Dónde te la vas a encontrar de verdad

Las colas mueven los sistemas que están debajo de tus programas. El scheduler del sistema operativo mantiene los procesos en colas esperando CPU. Los routers de red encolan paquetes; los brokers de mensajes como RabbitMQ y Kafka son colas que rentas por mes. La búsqueda en anchura de los capítulos de grafos es la búsqueda en profundidad con el stack cambiado por una cola: ese solo cambio es la diferencia entre explorar primero lo más cercano y primero lo más profundo. Y cualquier esquema productor/consumidor — un hilo generando trabajo, otro haciéndolo — es una cola entre los dos. Siempre que el trabajo deba atenderse en el orden en que llegó, esta es la estructura.

Puntos clave

Una cola es FIFO — te formas al final, sales por el frente, ambas $O(1)$ — y un deque lo generaliza a O(1) en ambos extremos, que es la razón por la que el deque es el que te da la librería estándar y la primitiva de la que se tallan el stack y la cola. Construye cualquiera de ellos sobre una lista doblemente ligada y los extremos se mantienen baratos; en Python, collections.deque es la versión afinada que de verdad conviene usar.

Lo único que tienes que llevarte de este capítulo es la advertencia: una lista no es una cola, porque sacar de su frente es O(n). Usa deque y popleft, y nunca vas a escribir ese ciclo accidentalmente cuadrático que agarra a todos alguna vez. Con stacks y colas en la mano ya tienes los dos ordenamientos fundamentales; el siguiente capítulo ve qué pasa cuando una cola tiene tamaño fijo y debe reutilizar su espacio: el ring buffer.