Queues, Deques and Circular Buffers

1First in, first out

A stack serves the newest waiting item. A queue serves the oldest. One word of difference, and completely different behaviour.

A queue supports two operations, on opposite ends:

• enqueue(x) — add x at the back
• dequeue() — remove and return the item at the front

2The pop(0) trap

The obvious Python implementation is quietly quadratic. This is the single most common performance bug in beginner-to-intermediate code.

A list looks like it can be a queue: append to add at the back, pop(0) to take from the front. It works. It is also O(n) per removal, because Chapter 3 told us why — an array's contract is that element i lives at a fixed offset, so removing the front means shifting every remaining element one slot left.

Draining a queue of n items this way costs n + (n−1) + (n−2) + … element moves — which is n²/2. On a thousand items that is half a million moves you did not ask for. On a hundred thousand it is five billion, and your program appears to hang.

from collections import deque
import time

N = 40_000

# --- the trap ---
q = list(range(N))
t0 = time.perf_counter()
while q:
    q.pop(0)           # O(n) each time  →  O(n²) overall
t1 = time.perf_counter()

# --- the fix ---
d = deque(range(N))
t2 = time.perf_counter()
while d:
    d.popleft()        # O(1) each time  →  O(n) overall
t3 = time.perf_counter()

print(f"list.pop(0):    {(t1-t0)*1000:8.1f} ms")
print(f"deque.popleft():{(t3-t2)*1000:8.1f} ms")

# Double N. The list time roughly QUADRUPLES; the deque time doubles.

3The circular buffer

The classic fix, and the one you would implement in C. A fixed array plus two indices and one modulo.

The problem with a list-backed queue is that the front keeps moving right, abandoning space behind it. The fix is to let the queue wrap around and reuse that space: a fixed array with a head index (where the next item leaves) and a tail index (where the next item arrives), both advancing modulo the capacity.

class RingBuffer:
    def __init__(self, capacity):
        self._buf = [None] * capacity
        self._cap = capacity
        self._head = 0        # next item to leave
        self._tail = 0        # next free slot
        self._size = 0

    def enqueue(self, x):
        if self._size == self._cap:
            raise OverflowError("buffer full")
        self._buf[self._tail] = x
        self._tail = (self._tail + 1) % self._cap    # ← the whole trick
        self._size += 1

    def dequeue(self):
        if self._size == 0:
            raise IndexError("dequeue from an empty buffer")
        x = self._buf[self._head]
        self._buf[self._head] = None                 # release the reference
        self._head = (self._head + 1) % self._cap
        self._size -= 1
        return x

    def __len__(self):
        return self._size

# Both operations: a couple of assignments and one modulo. No shifting,
# no allocation, ever. O(1) with a very small constant.

Ring buffers are everywhere in systems where memory is fixed and allocation is forbidden: audio buffers, network packet queues, kernel logs, embedded firmware. When the buffer fills, a real system picks a policy — block, drop the newest, or overwrite the oldest. Your terminal's scrollback is the last of those.

4deque: the one you will actually use

Python ships a double-ended queue that is O(1) at both ends. It is the right answer to nearly every queue-shaped problem in Python.

collections.deque (“deck”) supports O(1) append and pop at both ends. Internally it is a doubly linked list of fixed-size array blocks — which gets it the cache locality of arrays and the O(1) end operations of a linked list.

from collections import deque

d = deque([1, 2, 3])

d.append(4)         # add at the right   O(1)
d.appendleft(0)     # add at the left    O(1)
d.pop()             # remove from right  O(1)
d.popleft()         # remove from left   O(1)

d[0]                # O(1)  — the ends are cheap
d[len(d) // 2]      # O(n)  — the MIDDLE is not. This is the trade.

# A bounded deque: pushing past maxlen silently drops from the other end.
recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.append(x)
print(recent)       # deque([3, 4, 5], maxlen=3)
                    # a rolling window of the last 3, for free

5The monotonic deque

Chapter 6's monotonic stack, with one extra ability: throwing away from the other end too. It solves sliding-window maximum in O(n).

The problem: given an array and a window size k, report the maximum in every window as it slides. The obvious solution recomputes the max per window: O(n·k). A heap gets it to O(n log k). A monotonic deque gets it to O(n).

The insight is one sentence: if a value arrives that is larger than something already in the window, that smaller thing can never be the maximum again — the new value is bigger and will outlive it. So throw it away immediately.

from collections import deque

def sliding_max(xs, k):
    dq = deque()          # indices, values strictly DECREASING front to back
    out = []
    for i, x in enumerate(xs):
        # 1. drop indices that have fallen out of the window (from the FRONT)
        if dq and dq[0] <= i - k:
            dq.popleft()

        # 2. drop values smaller than x — they can never win again (from the BACK)
        while dq and xs[dq[-1]] <= x:
            dq.pop()

        dq.append(i)

        # 3. the front is always the maximum of the current window
        if i >= k - 1:
            out.append(xs[dq[0]])
    return out

sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3)   # [3, 3, 5, 5, 6, 7]

Both ends are used, and for different reasons — which is exactly why this needs a deque rather than a stack:

• The front is popped because an index has expired out of the window.
• The back is popped because a value has become irrelevant.

And the cost argument is the same one as always: each index enters the deque once and leaves once, so the total work is at most 2n. The nested while does not make it quadratic.

>_Playground

Measure the pop(0) trap yourself, then watch a ring buffer wrap around.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.