Ring Buffer / Circular Queue

Problem framing

Design a fixed-capacity FIFO — enqueue(x), dequeue() — that never shifts elements. Tests whether you recognize a plain array/list's "remove from front" as a hidden O(n) op, and whether you can compose a clean class around head/tail modular arithmetic. This is the algorithmic core behind Design Circular Queue, Design Hit Counter, and "track the last N seconds of a stream" — the class-design version asks you to wrap it in an API and reason about what happens when producer and consumer run on different threads.

Class	Responsibility
RingBuffer<T>	enqueue(x), dequeue(), isFull(), isEmpty(); owns fixed array + head, size
capacity	Fixed at construction — no resize; overflow policy is a caller decision (block, drop-oldest, or reject)

Core mechanic

Wrapping both indices with modular arithmetic instead of ever shifting elements is the entire trick — head and size (or head/tail directly) turn a flat array into a logical circle.

Overflow policy — the class-design decision an algorithm-only answer skips

Policy	Use case
Reject / return false	Caller must handle backpressure explicitly (bounded task queues)
Block until space	Producer-consumer with a BlockingQueue-style contract
Drop oldest (overwrite)	Fixed-size sliding window over a live stream — correctness depends on discarding old data (a rolling average, a "last N events" monitor)

Naming which policy the requirements imply — and that this is a decision, not a detail — is the differentiator over just implementing enqueue/dequeue.

Concurrency: single producer/consumer vs. many

Setup	Approach
Single producer, single consumer	Lock-free with volatile/atomic head/tail indices is achievable and is what high-frequency-trading and audio-buffer implementations lean on for latency
Multiple producers/consumers	Needs a lock or CAS loop around the index updates — the single-writer trick above doesn't generalize without more care

This is the same primitive the Linux kernel's kfifo and most lock-free SPSC (single-producer-single-consumer) queues in low-latency systems are built on — bounded, contiguous memory, no allocation on the hot path.

Common pitfalls

Using a language's built-in "remove from front" list operation and assuming it's O(1) — on a plain array/list that's O(n) (shifts every remaining element), silently degrading an O(n) algorithm to O(n²) end to end. Confusing size == 0 and size == capacity when both leave head == tail — track size explicitly rather than inferring emptiness/fullness from index equality alone.

DSA crossover

The algorithmic mechanics, complexity analysis, and hands-on LeetCode practice (Design Circular Queue, Design Circular Deque, Design Hit Counter, Moving Average from Data Stream) live in the DSA roadmap's Ring Buffers & Streaming Window Designs subtopic. This page is the class-design, overflow-policy, and concurrency framing on top of that algorithm.

Where this goes next

Extensible APIs & Plugin Architecture generalizes Factory and Strategy patterns at component boundaries — registries, DI, and Open/Closed beyond infrastructure primitives.