Stacks, Queues and Ring Buffers

A stack and a queue are arrays or linked lists with most of their interface taken away. A stack lets you touch only the most recent item, a queue only the oldest. The restriction is what makes each operation O(1), and it is why these two shapes run undo histories, parsers, graph searches and every producer-consumer system ever built.

A ring buffer is a queue of fixed size. Its one real design decision, what happens when it is full, is visible in every log, audio stream and network card, and it is the same decision every service makes, knowingly or not, about its request queue.

The Stack: Last In, First Out

A stack adds and removes at one end only: push puts an item on top, pop takes the top item off. Undo histories are stacks, and so are backtracking search (Chapter 9), depth-first search (Chapter 8), bracket matching in a parser (Chapter 13) and the call stack itself (Chapter 3). In each case the most recent unfinished thing is the one to deal with next.

A Python list is a correct stack. Appending to its end and popping from its end are both O(1), because neither moves any other element (see Arrays and Dynamic Arrays). Nothing else is needed.

An explicit stack is also how deep recursion is made safe. The call stack is a stack the language manages, and CPython 3.15 stops it at 1,000 frames by default. A depth-first walk that keeps its own list of nodes still to visit has no such limit, and holds a million pending nodes in about 8 megabytes of pointers.

The Queue: First In, First Out

A queue adds at the back and takes from the front. Breadth-first search (Chapter 8), job queues and request buffers are queues, and they are fair by construction: the oldest waiter always goes next.

A Python list is the wrong queue. Taking from its front shifts every remaining element one slot left (see Arrays and Dynamic Arrays), so draining 100,000 items from the front moves about five billion pointers in total.

items = list(range(100_000))
while items:
    items.pop(0)          # 0.86 s: every pop shifts the rest
q = deque(range(100_000))
while q:
    q.popleft()           # 0.0036 s: nothing shifts

The listing drains the same 100,000 numbers from the front twice, once from a list and once from the standard library's deque. On CPython 3.15 the list took 0.86 seconds and the deque 3.6 milliseconds, more than two hundred times faster. The code differs by one method name.

The Deque

A deque, a double-ended queue, is O(1) at both ends. CPython's deque is a doubly linked list of fixed blocks, each holding 64 slots (see Linked Lists). Adding at either end writes into the end block, and allocates a new block only when that one is full. That keeps both ends cheap and most of the memory contiguous.

The price is the middle. Reaching an element by index means walking blocks from the nearer end, O(n) in the worst case, and a deque cannot be sliced at all: asking for a slice raises a type error. A deque is a queue that happens to allow indexing, not a general sequence.

The block design is also a memory decision. A deque of a million items needs about 16,000 blocks, each allocated once and reused as the ends move, instead of one huge array that would have to be copied as it grows. The ends are fast because the work at an end never depends on how many items sit in the middle.

The Ring Buffer

A ring buffer is a fixed array with two indexes, a head where the next item is read and a tail where the next item is written. When either index reaches the end of the array, it wraps around to the start. Once allocated, the buffer never allocates again, and its memory is bounded by construction.

With a capacity that is a power of two, the wrap is a single bitwise AND with the capacity minus one, instead of a division. And one producer and one consumer can share a ring without a lock, because each writes only its own index: the producer moves the tail, the consumer moves the head. That works only if each side sees the other's writes in the right order, which is the memory ordering that Chapter 11 explains.

When the Ring Is Full

A fixed capacity is a promise that something will give way, and choosing what gives way is the design. One choice is to overwrite the oldest entry. A kernel's log buffer does this, as do a flight recorder and a feature that keeps "the last 30 seconds" of audio or metrics. The other choice is to refuse the newest entry. A network card whose receive ring is full drops the arriving packet, and a sound recorder whose buffer is full loses the incoming audio, leaving a gap in the recording.

In both cases the loss is deliberate. The only open question is whether anyone counts it. An overwrite that is counted is a policy; an overwrite that is not counted looks like a bug.

The Cost in a System You Run

An unbounded queue between a fast producer and a slow consumer never drops anything. It turns overload into memory growth and waiting time instead. Requests pile up, the oldest ones time out while still in the queue, the process runs out of memory, and the work is lost anyway, later and more expensively than if it had been refused at the door.

A bounded queue with an explicit policy for when it is full turns the same overload into something the producer can see: it blocks the producer, drops the item, or rejects it with an error. That signal is backpressure (Chapter 12), and it is what lets the system in front slow down, retry later or send the work elsewhere.