Ring Buffers & Streaming Window Designs

The gap this subtopic closes

You've built a queue's behavior (FIFO ordering) constantly — every BFS in Trees and Graphs pushes and pops from one. What hasn't come up yet is how a queue is actually implemented on top of an array, and why getting that wrong is a classic, easy-to-miss performance bug. This subtopic covers the circular buffer (ring buffer) — the mechanism underneath every array-backed queue, most streaming/windowing designs, and a surprising amount of low-level systems code (audio buffers, network packet queues, OS kernel ring buffers) — and a cluster of "design a data structure with a time or ordering constraint" interview problems that lean on it directly.

Why "queue on an array" is harder than "stack on an array"

A stack only ever adds/removes from one end — appending to (or popping from) the end of a dynamic array is O(1) amortized, so a stack-on-an-array is trivial. A queue needs O(1) at both ends: enqueue at the back, dequeue from the front. The naive implementation — arr.pop(0) in Python, or manually shifting every remaining element left by one after removing the front — is O(n) per dequeue, silently turning an algorithm you believed was O(n) overall (n enqueues + n dequeues) into O(n²).

The fix: two pointers turn the array into a ring

Track a head index (next position to dequeue from) and a tail index (next position to enqueue into), and when either one reaches the end of the backing array, wrap it back to index 0 with modular arithmetic — instead of ever shifting elements, you just move where "the front" and "the back" point.

class CircularQueue:
    def __init__(self, capacity):
        self.buf = [None] * capacity
        self.capacity = capacity
        self.head = 0
        self.size = 0

    def enqueue(self, val):
        if self.size == self.capacity:
            raise OverflowError("queue is full")
        tail = (self.head + self.size) % self.capacity
        self.buf[tail] = val
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("queue is empty")
        val = self.buf[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return val

Both operations are O(1), with zero shifting of existing elements — the array's contents never move; only head and the derived tail position move, wrapping around via % capacity exactly like a clock face wrapping from 11 back to 12. This is the same head/tail-with-modular-wraparound idea, applied to a plain array, that a circular (doubly) linked list achieves with pointers instead — both are "ring" structures, just backed by different underlying storage.

Full vs. empty ambiguity — the classic off-by-one. When head == tail, is the buffer full or empty? Both states produce the identical pointer configuration if you don't track anything else, which is why the implementation above tracks an explicit size counter rather than trying to disambiguate purely from head/tail position (the alternative fix — reserving one slot as always-empty so head == tail can only mean "empty" — works too, but wastes one slot of capacity and is a more error-prone invariant to get exactly right under interview pressure).

Real-world case study: where ring buffers actually run

Ring buffers aren't a toy teaching structure — they're the standard implementation wherever you need a fixed-size, fast, FIFO buffer between a producer and a consumer running at different speeds: audio/video streaming pipelines (a fixed-size ring buffer absorbs small timing jitter between the audio hardware's read rate and the decoder's write rate without allocating), OS kernel packet queues (Linux's kernel ring buffers for network packet processing, and the dmesg kernel log buffer itself is a ring buffer — old messages are silently overwritten once it's full, which is exactly the fixed-capacity, oldest-evicted behavior below applies to logically), and the lock-free single-producer/single-consumer queues used in high-frequency trading and other latency-sensitive systems, precisely because a ring buffer's fixed-size, no-shifting design avoids both dynamic allocation and unpredictable pauses under load.

Practice: Design Circular Queue / Deque and stream-windowing designs

Design Circular Queue and Design Circular Deque ask you to implement exactly the mechanism above — a deque additionally needs insertion/removal at both ends, which the same head/size-with-modular-arithmetic approach extends to cleanly (front insert: decrement head with wraparound before writing; back insert: write at the wrapped tail position, as above).

Moving Average from Data Stream and Design Hit Counter are the natural next step: both need "the sum/count of everything within the last k elements (or k seconds) of a stream," which is a fixed-size sliding window over an unbounded stream — recognize this as the same shape as the Sliding Window topic's fixed-size window pattern, just with the window's contents held in a ring buffer instead of tracked via two array indices, because the stream itself (unlike an array) isn't sitting in memory to index into directly. Design Underground System is a step further again: it composes a hash map (station/passenger lookup, the Arrays & Hashing pattern) with running-average bookkeeping per route — a good capstone problem for "combine two simple structures to satisfy several requirements at once," the same design instinct you exercised earlier with LRU/LFU cache in the Linked List topic.

Comparison: the three "ordered, evolving state" designs across this roadmap

	LRU/LFU Cache (Linked List topic)	Skip List / ordered set (previous subtopic)	Ring buffer (this subtopic)
What it optimizes for	O(1) access + O(1) reorder-to-front	O(log n) ordered search/insert/delete	O(1) fixed-window FIFO with no shifting
Core structures combined	Hash map + doubly linked list	Stacked sparse linked lists	Array + modular-arithmetic head/tail
Real-world analogs	Browser/CPU/CDN caches	Redis ZSET, LSM-tree memtables	Kernel packet queues, audio buffers, `dmesg`

Seeing these three next to each other is the actual point of this topic: each is "compose two simple ideas to satisfy a couple of specific operations in O(1) or O(log n)," and recognizing which combination a new design question wants is a transferable skill, not three unrelated memorized designs.

Complexity summary

Operation	Naive array queue (`pop(0)`)	Circular buffer
Enqueue	O(1) amortized	O(1)
Dequeue	O(n) (shifts every remaining element)	O(1)
Space	O(capacity)	O(capacity), fixed and pre-allocated

Pitfalls and interview gotchas

Using list.pop(0) (or equivalent) and calling it O(1). This is the single most common silent-performance-bug version of "implement a queue" — it's correct, and it's O(n) per call, which compounds into O(n²) across a loop that looks like it should be O(n).
Getting the full/empty disambiguation wrong. Either track an explicit size (simplest, shown above) or reserve one sentinel slot — pick one and be consistent; conflating head == tail with "always empty" is a common off-by-one.
Forgetting the modulo on the tail computation, or applying it inconsistently between enqueue and dequeue — both head and the computed tail position need the same % capacity wraparound logic.
Not handling capacity-zero or capacity-one edge cases explicitly if the problem allows them — trace these by hand before trusting the general formula, same habit as the boundary-testing discipline from Binary Search.

How to talk about this in an interview

"A plain array queue that shifts elements on every dequeue is O(n) per operation, which silently turns an O(n)-total algorithm into O(n²). I'll use a circular buffer instead — track head and size, compute the write position with modular arithmetic so the array wraps around like a ring instead of shifting — giving O(1) enqueue and dequeue with a fixed, pre-allocated amount of memory. This is the same mechanism behind kernel packet queues and audio ring buffers, for exactly this reason: fixed size, no allocation, no shifting, under real-time constraints."

If you get asked to design this as a class, not just an algorithm

The LLD roadmap's Ring Buffer / Circular Queue subtopic picks up from here — the overflow policy (block, drop-oldest, reject) as an explicit class-level decision, and the single-producer/single-consumer lock-free case, the same "DSA algorithm becomes an LLD class" jump the Linked List topic's LRU Cache made.

Further Resources (Optional)

GeeksforGeeks — Circular Queue Data StructureArticle15m
Wikipedia — Circular bufferReference15m
NeetCode — Design Circular Queue (LC 622) walkthroughVideo12m
Linux Kernel Documentation — Circular Buffers (kfifo)Reference15m

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Moving Average from Data StreamEasyPremiumFree replacement~2/520m
Design Hit CounterMediumPremiumFree replacement~3/525m