52The queue — first in, first out

In Chapter 51 we built the stack — last in, first out, always handing you back the newest thing you gave it. Here we build its mirror image, and it turns out to be everywhere. A queue is how your operating system shares the CPU, how a search sweeps a maze level by level, how every keystroke you type waits its turn. The rule is dead simple. First In, First Out: add at the back, remove from the front, nobody jumps the line. Here's the plan. We'll write the obvious Python queue out of a plain list, watch it quietly betray us on big inputs, then fix it two ways: a ring buffer that bends a fixed array into a circle, and collections.deque, the tool you'll actually reach for. The whole way through we keep asking the one question that decides everything. When you pull the item off the front, what does the machine actually have to move? By the end you'll have a queue that adds and removes in true O(1). You'll know exactly why the natural version secretly crawls at O(n), and you'll have seen — in memory — the one trick that fixes it.

01One rule, and it means order

Let's start with the shape of the thing. A queue is a linear collection with two doors, one at each end, and a law about which door does what. The back door is enqueue: a new item goes in there, and only there. The front door is dequeue: an item comes out there, and only there. Watch what that one law forces. Because you always remove the oldest surviving item, the one that has waited longest, the queue preserves arrival order perfectly. First in, first out. A stack is LIFO and a queue is FIFO. Both are nothing more than a rule about which end you touch.

And that rule is not a toy. FIFO is fairness: the request that arrived first gets served first, so no task starves while newer ones cut the line. It is also buffering. When a fast producer feeds a slow consumer — your keyboard feeding a busy program, a network card feeding your app — a queue holds the backlog in the exact order it arrived. The consumer then drains it at its own pace without losing or reordering a thing. Keep those two words, fairness and buffering, in mind. Every real use at the end of this chapter is one of them.

Now the part this volume cares about most: what does a queue actually look like in RAM? The honest first picture is a row of slots — a contiguous block, exactly the array of 8-byte references from Volume 1 — plus two markers. One marker, front, points at the oldest live item, the next to leave. The other, back, points at the next free slot, where the next arrival will land. Enqueue writes at back and nudges back forward. Dequeue reads at front and nudges front forward. Nothing else moves.

If both operations touch a single slot and bump a single index, both should be O(1). So why does the most natural Python queue crawl to a halt on big inputs? →

02Why a plain list makes a terrible queue

Reach for a queue in Python and the obvious move is a list: append to add at the back, pop(0) to remove from the front. It looks right. It even works — for a while. Then it dies, and the reason is buried in how a list lives in memory. Recall from Volume 1: a Python list is a contiguous array of references with a fixed front pinned at index 0. There is no movable front marker. So when you delete index 0, the list cannot just advance a pointer. It must keep index 0 meaning index 0. That forces every one of the remaining n−1 references to slide down one slot and close the hole.

"Slides down one slot" is a bulk memory copy — internally a single memmove of n−1 pointers. For six items it is invisible. For a million-item queue, every single dequeue copies almost eight megabytes of references before it can return one value. That is O(n) per removal, which makes draining the whole queue O(n²). We do not have to trust the reasoning; we can time it. Here each trial dequeues one item from a size-n queue and re-enqueues it, so the size stays fixed and we isolate the cost of one front removal:

import timeit
from collections import deque

for n in (10_000, 100_000, 1_000_000):
    tl = timeit.timeit("l.append(l.pop(0))",       # dequeue front, re-enqueue
                       setup=f"l=list(range({n}))", number=5000) / 5000
    td = timeit.timeit("d.append(d.popleft())",    # same, but a deque
                       setup=f"from collections import deque; d=deque(range({n}))",
                       number=5000) / 5000
    print(f"n={n:>9}   list {tl*1e9:8.0f} ns   deque {td*1e9:4.0f} ns")

# n=    10000   list    14790 ns   deque   27 ns
# n=   100000   list   151925 ns   deque   28 ns
# n=  1000000   list   526401 ns   deque   24 ns

Read the list column top to bottom. Ten thousand items: ~15 µs per dequeue. Ten times the items: ~152 µs. That is ten times the cost, a dead-straight line, exactly what O(n) predicts. The deque column beside it never twitches: ~25 nanoseconds whether it holds ten thousand items or a million. (Numbers are from this machine and will vary. The shapes — one climbing, one flat — are the law.) Push it further and it stops being a benchmark and becomes pain. Draining a 100,000-item queue front-to-back took the list 7.5 seconds; the deque did the same job in 5.4 milliseconds. That is about 1,400× faster, and the gap widens with every extra item.

The list's sin was a front that couldn't move. What if we let it move — and let both ends wander freely around a fixed block of slots? →

03The ring buffer — two indices chasing around a fixed array

Here is the human insight that fixes everything, and it is beautifully cheap. The whole problem was that dequeuing tried to keep the front pinned at index 0. So don't pin it. Keep the same contiguous array, but let front and back be movable integer indices. Dequeue? Just advance front by one. The old slot is now dead space, and we don't care. Enqueue? Write at back, then advance back by one. No element ever moves. Both operations are a write and an add: genuine O(1).

But if both indices only ever crawl forward, they march off the end of a fixed array. The fix is the trick that names the structure: wrap around. When an index reaches the last slot, its next step goes back to slot 0, computed with a single modulo, (i + 1) % capacity. The array is no longer a line; it is a ring. The live queue is the arc of slots from front up to back. That arc drifts around the circle as items come and go, forever reusing the slots that dequeues freed behind it. This is a ring buffer (also called a circular buffer), and it is one of the most-used structures in all of systems programming.

A ring buffer is perfect when you know the capacity up front. But Python's queue of choice grows without bound and still gives O(1) at both ends. How? →

04collections.deque — the real fix, and its memory

You will rarely hand-roll a ring buffer in Python. You will reach for collections.deque (pronounced "deck," from double-ended queue), the standard library's answer to exactly this problem. It gives you O(1) append and pop at the back and O(1) appendleft and popleft at the front, with no shifting, ever. For a FIFO queue you use just two of its four doors: append to enqueue, popleft to dequeue.

from collections import deque

q = deque()          # an empty FIFO
q.append("A")        # enqueue at the back
q.append("B")
q.append("C")
first = q.popleft()  # dequeue from the front  ->  "A"  (first in, first out)
print(first, list(q))
# A ['B', 'C']

Line by line: deque() builds an empty double-ended queue. Three appends enqueue A, B, C at the back in order. popleft() removes from the front and returns "A", the oldest item, exactly FIFO. What remains is B then C. Same five lines a list would use, minus the O(n) landmine.

What does a deque look like in memory, and why does it stay O(1) at both ends? Not one contiguous array — that would re-create the list's problem at one end or the other. Instead a deque is a doubly linked list of fixed-size blocks. Each block is a small contiguous array (64 reference slots in CPython), and the blocks are chained with next/prev pointers. The deque keeps direct pointers to the first and last block, plus the write position inside each. Adding at either end writes into the end block. When an end block fills, a new block is linked on. No element is ever copied to make room; growth just links another block.

That design has a memory price worth naming out loud. An empty list weighs 56 bytes. An empty deque weighs 760 bytes, because it pre-allocates its first block of slots up front. So for tiny collections a deque is heavier. But per element the two converge on the same figure, about 8 bytes each, because both, at bottom, store 8-byte references (Vol 1), not the objects themselves:

import sys
from collections import deque
print(sys.getsizeof([]),        sys.getsizeof(deque()))       # empty:  56   760
for n in (1000, 10000):
    print(n, sys.getsizeof(list(range(n))), sys.getsizeof(deque(range(n))))
# 1000    8056    8680
# 10000  80056   83128

At 10,000 items the list holds 80,056 bytes and the deque 83,128. The deque's small surplus is the per-block bookkeeping: the next/prev pointers and partly-filled end blocks. Both are ~8 bytes times n plus a fixed header, a container of references, precisely the Volume 1 model. The deque buys you O(1) at both ends for a modest, near-constant space premium — a very good trade.

You now have a real O(1) FIFO. The last question is the one that makes it worth knowing: where does the machine — and the wider world — actually run on queues? →

05How the machine feels it, and why search runs on queues

Big-O says the ring buffer and a naive pointer-per-node linked queue are both O(1) per operation. The metal disagrees about which is fast. A ring buffer is one contiguous array, so consecutive slots sit in consecutive cache lines. Walking the queue streams through the CPU cache (Volume 3) at full speed. A linked queue with one heap node per item scatters those nodes anywhere in memory, so every dequeue chases a pointer to an address the cache never predicted — a stall of hundreds of cycles, again and again. The deque splits the difference on purpose. 64 items per block means you get long contiguous runs (cache-friendly) with only an occasional pointer hop between blocks. That block size is not arbitrary; it is tuned so the pointer-chase is rare relative to the streaming. This is the whole reason a heap lives in a flat array too — a lesson the heap chapter makes central.

That is the deepest "wow" in the chapter: BFS and a queue are the same idea. The queue holds the frontier — nodes seen but not yet explored. Dequeue the oldest, enqueue its undiscovered neighbours at the back, repeat. Because a queue is FIFO, everything one step from the start is processed before anything two steps away. So BFS sweeps outward in perfect concentric rings and lands on the shortest path first. Change one line — dequeue from a stack instead — and the identical loop becomes depth-first search. The container chooses the algorithm. That is the 1% move in miniature: the data structure is the strategy.

06When to reach for a queue

Good at data structures is mostly one skill: matching the access pattern to the container on sight. The queue's tell is unmistakable — whenever items must be handled in arrival order, and you always take the oldest first. That is fairness (serve who came first) or buffering (a fast source, a slow drain, order preserved between them). The instant you catch yourself writing list.pop(0) in a loop, stop. You have found a queue wearing a list's clothes, and it is quietly O(n²). Type from collections import deque instead.

You have the FIFO half of the story. But notice the widget above did something a pure queue never needs: it added and removed at both ends. That double-ended power — appendleft as easily as append — is not a queue at all. It is the deque in full, and its 64-slot block design is a small marvel of engineering worth a chapter of its own.

Next (chapter 53): the deque — one structure that is a stack and a queue at once. We open up those linked blocks of 64, see why that exact number, and watch appendleft and popleft stay O(1) at the end nobody else can touch. →