Circular and ring buffers

What this chapter covers

A queue that grows forever is fine until memory isn't. A ring buffer is the fix: fix the capacity up front, lay the elements out in a circle, and let the write position wrap around to the start when it runs off the end. You get an O(1) FIFO queue that never allocates after construction — and a useful new power, the ability to overwrite the oldest item when full, which is exactly what you want for a rolling log of the last N events. This chapter builds one with nothing but an array and two indices, and shows that the whole trick is a single modulo.

A bit of history

The ring buffer doesn't have a famous inventor — it's one of those ideas that fell out of hardware and never left. Early machines needed to move data between components running at different speeds, and a fixed circular buffer with a read pointer chasing a write pointer was the natural way to do it without allocating memory you didn't have. That pattern became standard in the 1960s and 70s for I/O buffering and digital signal processing, and it's still everywhere close to the metal: Unix pipes, the terminal driver, audio systems like JACK, network card rings, the Linux kernel's kfifo, and the lock-free ring buffers at the heart of high-frequency trading systems like the LMAX Disruptor. When latency has to be predictable and allocation is the enemy, this is the structure.

The intuition

Picture a clock face with slots instead of hours. You keep two hands: a write hand (the tail) pointing at the next free slot, and a read hand (the head) pointing at the oldest item. Push writes where the write hand points and moves it one slot clockwise; pop reads where the read hand points and moves it one slot clockwise. When either hand passes the last slot, it wraps back to the first — that's the "ring."

Because the slots get reused as the hands go around, the buffer never grows and never allocates. The only question is what happens when the write hand catches up to the read hand — when the buffer is full. You have two honest choices: refuse the push (backpressure — tell the producer to wait), or overwrite the oldest item and move the read hand along with you (keep only the most recent N). Both are useful; they're different tools.

Complexity: how it scales

Every operation is a write or read at a known index plus an increment and a modulo — all $O(1)$, with no shifting, no searching, and crucially no allocation after the buffer is built. Space is fixed at $O(\text{capacity})$ regardless of how many items flow through; a buffer of 1000 slots handles a billion pushes in the same 1000 slots. There's no recurrence and no amortization here — unlike the dynamic array, a ring buffer never resizes, so its O(1) is worst-case, not averaged. The chart streams a large number of pushes through a fixed size-1000 buffer; the line is straight because the per-push cost is genuinely constant:

What it's good at, what it isn't

A ring buffer is the right tool for a bounded stream — a fixed window over data that keeps flowing. Its fixed size is a feature, not a limitation: no allocation means no garbage-collector pauses and no memory growth, which is why real-time and embedded systems love it. The worst-case O(1) with predictable memory is worth more in those settings than a fancier structure's better average.

Its limits are the flip side of that fixed size. If you don't know the maximum capacity, or it can spike arbitrarily, a ring buffer will either reject data (refuse mode) or silently lose it (overwrite mode) — and either can be a bug if you picked the wrong mode. It's also not random-access or searchable; it's a queue with a wraparound, nothing more.

The data, or the inputs

The face-off streams a large number of pushes through a fixed 1000-slot buffer in overwrite mode — the "keep the most recent 1000" workload — so the constant-time, constant-memory behaviour is what's being measured. The animation uses a tiny six-slot buffer and a hand-written script, because the thing to actually see is the tail wrapping from the last slot back to the first, and the overwrite when it fills.

Build it, one function at a time

Push is where the wraparound lives. Write at the tail, advance the tail with a modulo so it wraps, and — if the buffer is full — either refuse or drop the oldest by advancing the head:

def push(self, value):
    """O(1): write at the tail, then advance the tail — wrapping to 0 when it
    runs off the end. If the buffer is full, either refuse or drop the oldest
    item (advancing the head) to make room."""
    if self._count == self._cap:
        if not self._overwrite:
            raise IndexError("push to a full ring buffer")
        self._head = (self._head + 1) % self._cap   # forget the oldest
        self._count -= 1
    self._buf[self._tail] = value
    self._tail = (self._tail + 1) % self._cap       # the wraparound
    self._count += 1

Pop is the mirror: read at the head, clear the slot, advance the head with the same wraparound. It always returns the oldest item, because a ring buffer is still a FIFO queue underneath:

def pop(self):
    """O(1): read at the head, clear the slot, advance the head with the same
    wraparound. Returns the oldest item — this is still a FIFO queue."""
    if self._count == 0:
        raise IndexError("pop from an empty ring buffer")
    value = self._buf[self._head]
    self._buf[self._head] = None
    self._head = (self._head + 1) % self._cap
    self._count -= 1
    return value

That's the whole structure. Two indices, one array, and % capacity doing all the work of making a finite array behave like an endless circle.

Watch it work

Here's a six-slot buffer in overwrite mode. The slots are fixed in place — slot 0 through slot 5 never move — and it's the positions that travel around them. Green is the oldest item (the next to pop); blue slots are occupied; dark slots are free. Step through it and watch the tail fill slots left to right, then wrap back to slot 0 when it runs off the end, and finally overwrite the oldest item once the buffer is full. The data moves in a circle even though the array is a straight line:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our RingBuffer, two indices and a modulo. The library tab is collections.deque(maxlen=N): give a deque a maxlen and it becomes a bounded, overwrite-oldest ring buffer with no index arithmetic to write yourself.

"""A ring buffer — a fixed-size queue that reuses its space by wrapping around.

A normal queue grows without bound. A ring buffer fixes the capacity up front and
lays the elements out in a circle: when the write position runs off the end of the
array, it wraps back to the start. That makes it O(1) with zero allocation after
construction, and gives it a useful trick — when it's full, it can overwrite the
oldest item, which is exactly what you want for a "last N events" log.
"""


class RingBuffer:
    def __init__(self, capacity, overwrite=False):
        self._cap = capacity
        self._buf = [None] * capacity   # the fixed backing array, never resized
        self._head = 0                  # index of the oldest item (next to pop)
        self._tail = 0                  # index of the next free slot (next write)
        self._count = 0
        self._overwrite = overwrite     # when full: drop the oldest vs. refuse

    # region: push
    def push(self, value):
        """O(1): write at the tail, then advance the tail — wrapping to 0 when it
        runs off the end. If the buffer is full, either refuse or drop the oldest
        item (advancing the head) to make room."""
        if self._count == self._cap:
            if not self._overwrite:
                raise IndexError("push to a full ring buffer")
            self._head = (self._head + 1) % self._cap   # forget the oldest
            self._count -= 1
        self._buf[self._tail] = value
        self._tail = (self._tail + 1) % self._cap       # the wraparound
        self._count += 1
    # endregion

    # region: pop
    def pop(self):
        """O(1): read at the head, clear the slot, advance the head with the same
        wraparound. Returns the oldest item — this is still a FIFO queue."""
        if self._count == 0:
            raise IndexError("pop from an empty ring buffer")
        value = self._buf[self._head]
        self._buf[self._head] = None
        self._head = (self._head + 1) % self._cap
        self._count -= 1
        return value
    # endregion

    def is_full(self):
        return self._count == self._cap

    def __len__(self):
        return self._count

    def to_list(self):
        """Oldest to newest — walk `count` slots forward from the head."""
        return [self._buf[(self._head + i) % self._cap] for i in range(self._count)]

    def raw(self):
        """Backing array + head/tail/count, for the animation."""
        return list(self._buf), self._head, self._tail, self._count

"""collections.deque(maxlen=N) is a ring buffer in disguise. Give a deque a
maxlen and it becomes bounded: once it's full, every append silently drops the
item at the opposite end — exactly the overwrite-oldest behaviour of our ring
buffer, implemented in C with no Python-level index arithmetic.

So the face-off is our RingBuffer against `deque(maxlen=N)`, the standard-library
way to keep "the most recent N" of something.
"""
from collections import deque


# region: bounded_deque
def make_bounded(capacity):
    """A bounded deque: appends past `capacity` drop the oldest (leftmost)."""
    return deque(maxlen=capacity)
# endregion


# region: run_ops
def run_ops_deque(ops, capacity):
    """Drive ('push', x) / ('pop',) on a bounded deque, overwrite-on-full."""
    dq = deque(maxlen=capacity)
    popped = []
    for op in ops:
        if op[0] == "push":
            dq.append(op[1])       # drops the oldest automatically when full
        elif dq:
            popped.append(dq.popleft())
    return popped, list(dq)
# endregion

Scratch vs library

Both are O(1) per push, so the lines are straight and the gap is a constant factor. Streaming 800000 pushes through a size-1000 buffer took our RingBuffer about 85 ms against deque(maxlen)'s 8.8 ms — roughly ten times slower:

Ten times is a big constant, and it's honest about what Python costs: our push does an explicit modulo, two attribute lookups, and an index assignment per item, all in interpreted bytecode, where deque does the whole bounded-append in C. The asymptotics are identical — both flat lines — so on a workload where the buffer is the bottleneck you'd use the deque. You build the ring buffer to understand what maxlen is doing, and because in a lower-level language, where you don't have a deque handed to you, this two-index array is the thing you'd write.

Where you'll actually meet it

Ring buffers live wherever data streams past at a fixed window. Audio and video pipelines use them to bridge the producer (the microphone, the network) and the consumer (the speaker, the decoder) without dropping to allocation on the real-time path. Network cards hand packets to the OS through descriptor rings. Logging systems keep the last N lines in a ring so a crash dump has recent context without unbounded memory. dmesg, the Linux kernel log, is a ring buffer. And any time you've written deque(maxlen=100) to keep a rolling window of recent values, you've used one — this chapter is what that maxlen does underneath.

Takeaways

A ring buffer is a fixed array plus two wrapping indices: push at the tail, pop at the head, and % capacity folds the ever-advancing positions back into the same slots forever. It's $O(1)$ worst-case with no allocation, which makes it the queue of choice when memory is bounded and latency must be predictable — and its overwrite-when-full mode is the natural way to keep "the most recent N" of a stream.

That closes out the linear structures. Arrays, linked lists, stacks, queues, and ring buffers are the containers you reach for by default, each a different answer to "which end do I work on, and does the size grow." The next tier changes the question entirely: instead of ordering elements in a line, hashing scatters them by their content so you can find any one in constant time — starting with the hash table.