Queues and deques

First in, first out. Join the back, leave the front. The stack's mirror image.

The family

• Queue — FIFO: enqueue back, dequeue front
• Deque — both ends: push/pop front and back
• All O(1) on a doubly linked list
• A deque is a stack and a queue, depending which end you take

Watch FIFO order

Green = front (served next), blue = back (just arrived). Out in the same order as in.

The trap: list.pop(0)

list.pop(0) is O(n) → O(n²) to drain. 24× slower than deque at 32000.

Takeaway

Use collections.deque + popleft, never list.pop(0). FIFO gives you fair, arrival-order service in O(1). Next: a fixed-size queue that reuses its space — the ring buffer.