Colas y deques

Primero en entrar, primero en salir. Te formas al final, sales por el frente. La imagen invertida del stack.

La familia

• Cola — FIFO: enqueue por atrás, dequeue por el frente
• Deque — ambos extremos: push/pop al frente y atrás
• Todo O(1) sobre una lista doblemente ligada
• Un deque es un stack y una cola, según de qué extremo saques

Mira el orden FIFO

Verde = frente (el próximo en ser atendido), azul = final (acaba de llegar). Salen en el mismo orden en que entraron.

La trampa: list.pop(0)

list.pop(0) es O(n) → O(n²) para vaciarla. 24× más lento que deque con 32000.

Para llevar

Usa collections.deque + popleft, nunca list.pop(0). FIFO te da servicio justo, por orden de llegada, en O(1). Sigue: una cola de tamaño fijo que reutiliza su espacio — el ring buffer.