Ring Buffer From Scratch

Implement RingBuffer, a fixed-capacity first-in first-out queue over a pre-allocated buffer. push adds at the tail and fails when full. pop takes from the head.

Ring buffers sit in the hot path of low-latency systems: market-data handlers stage packets in them, loggers hand records across threads through them, and gateways queue outbound orders in them. They use a fixed block of memory, no allocation after construction, and index arithmetic instead of pointer chasing.

The interface is:

• the constructor takes capacity (at least 1) and allocates storage for exactly that many elements, once, there.
• push(value): appends at the tail; returns false (and changes nothing) when full.
• pop(): removes and returns the head, or nothing when empty.
• front(): the head without removing it, or nothing when empty.
• size(), empty() and full().

class RingBuffer:
    def __init__(self, capacity: int) -> None: ...
    def push(self, value: int) -> bool: ...
    def pop(self) -> int | None: ...
    def front(self) -> int | None: ...
    def size(self) -> int: ...
    def empty(self) -> bool: ...
    def full(self) -> bool: ...

push returns False when full, and pop() and front() return None when empty. Allocate one list in the constructor and never call list.pop(0) or insert(0, ...), which shift every element and are the \(O(n)\) this structure exists to avoid. collections.deque is banned. Indices must wrap; the buffer must keep working through many times capacity operations.

The provided driver run_ring_buffer(capacity, ops) applies a list of operations to a fresh buffer, returns one output per op, and is what the tests call. Each op is ("push", value), ("pop",), ("front",), ("size",), ("empty",) or ("full",). Two more ops are shorthands: ("rotate", value) pushes, first popping the head when the buffer is full, and ("swap", value) pops the head and then pushes.

Examples

run_ring_buffer(2, [("push", 1), ("push", 2), ("push", 3)])
# [True, True, False]  (third push rejected: full)

run_ring_buffer(2, [("push", 7), ("push", 8), ("pop",), ("push", 9), ("pop",), ("pop",)])
# [True, True, 7, True, 8, 9]  (wrap-around preserves FIFO order)

Constraints

• Values are integers; capacity up to \(10^5\).
• All operations must be \(O(1)\): the hidden tests drive many times capacity operations through a buffer, so per-operation shifting or reallocation will not finish in time. The largest hidden test runs 200,000 operations at capacity 100,000.
• Track size explicitly or reserve a slot; both are acceptable, but full() and empty() must be exact (the classic head==tail ambiguity is yours to resolve).