Build a Ring Buffer

The clock, made structural

Module 3 promised the mod-as-clock model would run a real structure. Here it is: a ring buffer (circular queue) is a fixed-size array where the front and back wrap around — index arithmetic mod capacity. No shifting, no compaction, no allocation after construction: both queue operations are pure index moves.

capacity 5:      [ _, B, C, D, _ ]
                      ↑        ↑
                    head      (tail lands here next)
enqueue(E):      [ _, B, C, D, E ]      tail wraps: (4+1) % 5 = 0
enqueue(F):      [ F, B, C, D, E ]      the "ring" in action

Think of it like the clock on your wall: when the hand moves past 12, it doesn't crash into a wall waiting for a 13th hour — it just wraps around to 1. A ring buffer's index does the same thing every time it passes the last slot.

Trace the formula the code actually uses — tail = (head + size) % capacity — against this exact example. Before enqueue(E): head = 1, size = 3 (B, C, D occupy indices 1, 2, 3). tail = (1 + 3) % 5 = 4 — matches the empty slot the diagram points at. After writing E there, size becomes 4, so the next tail is (1 + 4) % 5 = 5 % 5 = 0 — the wrap the diagram calls out, derived from the same formula rather than tracked separately.

Fixed capacity is a feature in the ring's home turf — network buffers, keyboard input, audio streams, log rings — where bounded memory and zero allocation are requirements, not limitations.

The one design decision: full vs empty

With head and tail both moving, head == tail is ambiguous: an empty ring and a completely full ring look identical. Derive why: both start at head = tail = 0. Enqueue capacity (call it C) elements without ever dequeuing, and tail advances once per insertion — after C insertions the new tail index is C mod C = 0. So the C-element (full) state and the 0-element (empty) state both land on head == tail == 0 — two different amounts of data, one identical pair of coordinates. Every implementation must break the tie. The two standard answers:

1. Keep a size counter (we do this — simplest and clearest);
2. Sacrifice one slot: define "full" as (tail + 1) % capacity == head — the ring stops accepting one slot before tail would ever catch head, so a full ring always has head != tail (they're exactly 1 apart), while empty stays head == tail. The states are distinguishable again — at the cost of one cell that can never hold data.

The implementation

class RingBuffer:
    def __init__(self, capacity: int) -> None:
        self._store = [None] * capacity
        self._capacity = capacity
        self._head = 0                    # index of front element
        self._size = 0                    # breaks the full/empty tie

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

    def enqueue(self, value) -> bool:
        if self.is_full():
            return False                  # or: overwrite / raise — a policy
        tail = (self._head + self._size) % self._capacity   # derived!
        self._store[tail] = value
        self._size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty ring")
        value = self._store[self._head]
        self._store[self._head] = None    # release the reference
        self._head = (self._head + 1) % self._capacity      # the wrap
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty ring")
        return self._store[self._head]

Watch the ring fill, drain, and wrap on the diagram's own example — in a circular layout, wrapping from the last slot to the first isn't a jump, it's just the next neighbor:

Design notes worth reading against the code:

• tail is derived, not stored: (head + size) % capacity. One fewer variable to keep consistent — the same invariant-shrinking instinct as Module 7's dummy node. (Storing tail is also fine; then size or the sacrificial slot must disambiguate.)
• The wraps are the Module 3 clock: (head + 1) % capacity steps the ring; in a language where indices could go negative, the ((x % n) + n) % n fix would apply — here they only grow, so plain % is safe in both languages.
• Full-ring policy is a real decision: reject (ours), overwrite the oldest (logging rings do this — the ring becomes a "last N items" window), or block (producer-consumer queues). The structure is the same; the policy is the product requirement.

That "O(1) worst case, not amortized" line is the ring's quiet superpower: no operation EVER spikes. Systems that can't tolerate a pause (audio callbacks, interrupt handlers) choose rings precisely to avoid the dynamic array's rare-but-real O(n) copy.