52The queue — first in, first out

In Chapter 51 we built the stack — last in, first out. It always hands 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. It is how a search sweeps a maze level by level, and 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, and nobody jumps the line. Here's the plan. We'll write the obvious Python queue out of a plain list, then watch it quietly betray us on big inputs. After that we fix it two ways. First a ring buffer, which bends a fixed array into a circle. Then collections.deque, the tool you'll actually reach for. And 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; a queue is FIFO; both are nothing more than a rule about which end you touch.

Let's make that concrete before we go further. Say three web requests hit your server in order: R1, then R2, then R3. Each one enqueues at the back as it arrives, so the line reads R1, R2, R3 from front to back. Now the server is ready to work. It dequeues from the front and gets R1, the one that has waited longest. Dequeue again and it gets R2, then R3. The order out is exactly the order in. Nobody who arrived later was served first. That is the whole promise of a queue, and every use in this chapter is just this small trace played out at scale.

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, and the picture there is a fast producer feeding a slow consumer — your keyboard feeding a busy program, or a network card feeding your app. A queue holds that backlog in the exact order it arrived, and the consumer drains it at its own pace without losing or reordering a thing. Keep those two words, fairness and buffering, in mind, because 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 one to leave. The other, back, points at the next free slot, where the next arrival will land. To enqueue, we write at back and nudge back forward. To dequeue, we read at front and nudge front forward. Nothing else moves.

Put real addresses on that picture and it stops being abstract. Say the block starts at address 1000 and each reference is 8 bytes, so slot 0 lives at 1000, slot 1 at 1008, slot 2 at 1016, and on up. If front holds the index 2 and back holds 5, the live items sit in slots 2, 3, and 4 — three of them — at addresses 1016, 1024, and 1032. To dequeue, we read slot 2 and bump front to 3. The value at 1016 never budged — we just stopped pointing at it. That is the whole trick in one line: the data stays put and two small integers do all the walking.

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. Every one of the remaining n−1 references has to slide down one slot to 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. But 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, because 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. (The numbers come 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, about 1,400× faster, and the gap widens with every extra item.

Those numbers check against each other. Ten times the items gave ten times the per-dequeue cost, 15 µs climbing to 152 µs, which is the straight line O(n) demands — a size-10n queue shifts ten times as many pointers per removal. The full-drain gap is starker still, because there both costs compound: draining 100,000 items is O(n²) work for the list against O(n) for the deque. 7.5 seconds versus 5.4 milliseconds is roughly a 1,400× spread, and every tenfold jump in n widens it by another factor of ten. The deque is not a little faster here. It is a different curve.

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, and the old slot is now dead space we simply don't care about. Enqueue? Write at back and advance back by one. No element ever moves. Both operations are a write and an add, which is genuine O(1).

Walk the indices once and you will feel the problem coming. Take a fixed array of capacity 4, with front and back both starting at 0. Enqueue three items and back climbs 0 → 1 → 2 → 3. Now dequeue two and front climbs 0 → 1 → 2. The live queue is just the one item in slot 2, yet back is already sitting at the last slot. Enqueue once more: that fills slot 3, and back tries to step to slot 4, which does not exist. Slots 0 and 1 sit empty and wasted behind us. The indices only crawl forward, so they run out of room while the array is nearly empty. That is the exact wall the next idea climbs over.

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. We compute that 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.

Watch the wrap happen with real numbers. Take a ring of capacity 8, so the valid slots are 0 through 7. If back is sitting at slot 7 and a new item arrives, we compute (7 + 1) % 8, which is 8 % 8 = 0 — back lands on slot 0, the slot some earlier dequeue freed. One item later it steps to (0 + 1) % 8 = 1, then 2, and on around the circle. The modulo is the whole ring in one operator: it turns a straight line of indices into a loop that never runs out, as long as the live count stays under the capacity.

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 — 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. Then popleft() removes from the front and returns "A", the oldest item, exactly FIFO, and what remains is B then C. These are the same five lines a list would use, minus the O(n) landmine.

INPUTfrom collections import deque

orders = deque()                       # the whole constructor

orders.append("#1041 latte")           # enqueue at the BACK
orders.append("#1042 flat white")
orders.append("#1043 cortado")
print("waiting:", len(orders), list(orders))

while orders:                          # the emptiness guard, same shape as a stack's
    ticket = orders.popleft()          # dequeue from the FRONT - oldest first
    print("  serving", ticket, "| still waiting:", list(orders))

print("empty?", not orders)
try:
    orders.popleft()
except IndexError as e:
    print("popleft on empty:", type(e).__name__ + ":", e)

recent = deque(maxlen=3)               # a bounded queue SILENTLY drops
for t in ["#1041", "#1042", "#1043", "#1044"]:
    recent.append(t)
    print("  maxlen=3 ->", list(recent))

OUTPUTwaiting: 3 ['#1041 latte', '#1042 flat white', '#1043 cortado']
  serving #1041 latte | still waiting: ['#1042 flat white', '#1043 cortado']
  serving #1042 flat white | still waiting: ['#1043 cortado']
  serving #1043 cortado | still waiting: []
empty? True
popleft on empty: IndexError: pop from an empty deque
  maxlen=3 -> ['#1041']
  maxlen=3 -> ['#1041', '#1042']
  maxlen=3 -> ['#1041', '#1042', '#1043']
  maxlen=3 -> ['#1042', '#1043', '#1044']

One caution before we look inside. A deque has four doors, and only one pair gives you a queue. append then popleft is FIFO: in at the back, out at the front, oldest first. Flip to append then pop — both at the same end — and you have rebuilt the stack from Chapter 51, newest first. Same object, opposite discipline. So the FIFO promise does not live in the deque itself — it lives in which two methods you choose to call. Pick the pair that matches the order you need, and never mix them without meaning to.

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.

Put a number on those blocks. A CPython deque block holds 64 references, so a deque of 1,000 items needs at least 1,000 ÷ 64 ≈ 15.6 blocks — round up to 16 — chained together. Fifteen of them are full, holding 960 items, and the sixteenth carries the last 40. Each block adds one next and one prev pointer, so the linking overhead is just 16 × 2 = 32 extra pointers for the entire 1,000-item deque. That is why the per-block bookkeeping is a rounding error beside the references themselves: a handful of pointers guarding thousands of slots.

That design has a memory price worth naming out loud. An empty list weighs 56 bytes, while 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, and that is because both, at bottom, store 8-byte references (Vol 1) rather than 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 the partly-filled end blocks. Both are ~8 bytes times n plus a fixed header, each a container of references, precisely the Volume 1 model. So the deque buys you O(1) at both ends for a modest, near-constant space premium, and that is a very good trade.

You can check that 8-bytes-plus-header claim by hand. A reference is 8 bytes, and the list holds 10,000 of them, so the slots alone are 10,000 × 8 = 80,000 bytes. Add the list's fixed 56-byte header and you get 80,056 — exactly the number the tool reported. Nothing mysterious is hiding in there. The list is a header stapled to a flat run of references, just as Volume 1 drew it. The deque's 83,128 is the same story with a little more bookkeeping: the same 80,000 bytes of references, plus the next/prev pointers and the slack in its partly-filled end blocks.

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 puts one heap node per item, scattered anywhere in memory. So every dequeue chases a pointer to an address the cache never predicted. That is 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, which are 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, the nodes seen but not yet explored. Dequeue the oldest, enqueue its undiscovered neighbours at the back, and 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. Now change one line to 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.

Picture it on a tiny grid to see the rings. Start at cell S and enqueue it. Dequeue S, then enqueue its four neighbours — the cells exactly one step away. Because they all sit at the back, the queue empties every distance-1 cell before it touches a distance-2 cell. When you finally dequeue a distance-1 cell and enqueue its undiscovered neighbours, those are distance-2, and they line up behind everything closer. So the search always finishes a whole ring before it starts the next. The first time you reach your target, you reached it in the fewest steps possible — that is why BFS finds the shortest path, and it is the FIFO rule doing every bit of the work.

Count the rings and the shortest-path claim becomes something you can check. Ring 0 is just S itself, the start. Ring 1 is its 4 neighbours, one step out. Ring 2 is everything one step beyond those, two steps from S, and so the pattern goes. Because the queue drains ring 0 completely, then ring 1, then ring 2, the moment a target pops out of the queue its ring number is its distance from S in steps. If your target sits in ring 3, BFS reached it in 3 steps and could not have done it in fewer — every earlier ring held the cells that were closer, and all of them came out first.

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. 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.

class TwoStackQueue:
    """A FIFO queue built from two LIFO stacks - and nothing else."""

    def __init__(self):
        self._in = []            # arrivals land here, newest on top
        self._out = []           # departures leave from here, OLDEST on top

    def enqueue(self, x):
        self._in.append(x)       # always O(1)

    def _flip(self):
        # Pour _in into _out. Popping a stack reverses it, so the oldest
        # arrival - buried at the bottom of _in - ends up on TOP of _out.
        while self._in:
            self._out.append(self._in.pop())

    def dequeue(self):
        if not self._out:        # only refill when _out has run dry
            if not self._in:
                raise IndexError("dequeue from empty queue")
            self._flip()
        return self._out.pop()   # O(1) on every call that finds _out stocked

    def __len__(self):
        return len(self._in) + len(self._out)


q = TwoStackQueue()
for t in ["A", "B", "C"]:
    q.enqueue(t)
print("in:", q._in, "out:", q._out)          # nothing has flipped yet
print("dequeue ->", q.dequeue())             # this one pays for the flip
print("in:", q._in, "out:", q._out)
print("dequeue ->", q.dequeue())             # free
q.enqueue("D")                               # arrives on the IN side
print("in:", q._in, "out:", q._out)
print("dequeue ->", q.dequeue())             # still free - out was stocked
print("dequeue ->", q.dequeue())             # out empty -> flip D across
print("len:", len(q))
try:
    q.dequeue()
except IndexError as e:
    print("empty:", type(e).__name__ + ":", e)

# in: ['A', 'B', 'C'] out: []
# dequeue -> A
# in: [] out: ['C', 'B']
# dequeue -> B
# in: ['D'] out: ['C']
# dequeue -> C
# dequeue -> D
# len: 0
# empty: IndexError: dequeue from empty queue

# THE AMORTIZED PROOF: count the moves, not the clock.
moves = 0
class Counted(TwoStackQueue):
    def _flip(self):
        global moves
        while self._in:
            self._out.append(self._in.pop()); moves += 1

c = Counted()
for i in range(100_000):
    c.enqueue(i)
for i in range(100_000):
    c.dequeue()
print("100,000 items ->", moves, "flip moves total =", moves / 100_000, "per item")

# 100,000 items -> 100000 flip moves total = 1.0 per item

# WHY THE FLIP IS RARE - and why "1.0" is the whole answer.
# Follow one item all the way through. It is pushed onto _in exactly once.
# It is moved across to _out exactly once. It is popped off _out exactly
# once. Three touches, fixed, forever - no matter how many other items are
# in the queue when its turn comes. That is why the counter printed exactly
# 100,000 moves for 100,000 items: 1.0 each, not 1.4, not n.
#
# The pour LOOKS expensive because one unlucky dequeue moves everything
# waiting. But that dequeue is buying the free ride for every dequeue behind
# it - _out is now stocked, and the next k calls just pop. Charge the cost
# to the items rather than to the calls and it flattens to a constant: this
# is amortized O(1), the exact bookkeeping the list's overallocation used.
#
# Break the rule and watch it die. Drop the `if not self._out:` guard so
# every dequeue re-pours the whole queue, and count again at n = 10,000:
#
#   guarded        10,000 moves  (      1.0 per item)
#   unguarded 100,000,000 moves  ( 10,000.0 per item)
#
# That is n moves against n**2 - measured, not estimated - and you have
# rebuilt list.pop(0) out of two stacks. The two stacks were never the
# trick. The GUARD was.
#
# Worth knowing where you have seen this: two stacks make a queue, and the
# same trick in reverse (two queues make a stack) is the classic pair. The
# structure was never in the container. It was always in the discipline.

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. →