Circular queue (ring buffer)
mediumOne modulo wraps the write position back to slot 0, so a fixed block of memory serves an unbounded sequence of operations. This is what backs audio pipelines and kernel packet queues.
O(1)Space O(capacity)Saved in this browser - no sign-up, nothing sent anywhere.
How circular queue (ring buffer) works
A plain array queue has a leak: front only advances, so the slots behind it become dead space. The fix is one modulo. Write at (head + size) mod capacity and the write position wraps back to slot 0 when it runs off the end - a fixed block of memory now serves an unbounded stream of operations.
Full and empty need care. With only head and tail pointers the two states look identical - both have head equal to tail - so this variant keeps an explicit size counter, incremented on enqueue and decremented on dequeue. The alternative is deliberately wasting one slot to break the tie.
This structure is what a network buffer is. Ring buffers back audio pipelines, kernel packet queues and lock-free producer-consumer channels precisely because they never allocate after startup: capacity is fixed at construction, and when the ring fills, the design must choose - reject, block, or overwrite.
Step by step
- Capacity 6, holding 14, 27, 8 in slots 0 through 2. head is 0 and size is 3.
- enqueue(52): the write lands at (0 + 3) mod 6 = slot 3, and size becomes 4.
- dequeue: return 14 from slot 0, advance head to (0 + 1) mod 6 = 1. Slot 0 is instantly reusable.
- enqueue 61, then 33: the writes land in slots 4 and 5, filling the array's right edge.
- enqueue(90): (1 + 5) mod 6 = 0 - the write wraps into the freed slot at the start. That wrap is the entire trick.
- size now equals capacity 6, so the next enqueue is refused. A ring never grows; it rejects, blocks or overwrites.
Complexity
| Worst case time | O(1) |
|---|---|
| Space | O(capacity) |
Reference implementation
Python
class CircularQueue:
def __init__(self, capacity):
self.data = [None] * capacity
self.head = 0
self.size = 0
def enqueue(self, v):
if self.size == len(self.data):
raise OverflowError("full")
self.data[(self.head + self.size) % len(self.data)] = v
self.size += 1
def dequeue(self):
if self.size == 0:
raise IndexError("empty")
v = self.data[self.head]
self.head = (self.head + 1) % len(self.data)
self.size -= 1
return vJavaScript
class CircularQueue {
constructor(capacity) {
this.data = new Array(capacity);
this.head = 0;
this.size = 0;
}
enqueue(v) {
if (this.size === this.data.length) return false;
this.data[(this.head + this.size) % this.data.length] = v;
this.size++;
return true;
}
dequeue() {
if (this.size === 0) return undefined;
const v = this.data[this.head];
this.head = (this.head + 1) % this.data.length;
this.size--;
return v;
}
}Worth noticing
Modulo turns the array into a ring
(head + size) mod capacity wraps the write position back to slot 0 when it runs off the end. That single operation lets a fixed block of memory serve an unbounded stream of enqueues and dequeues.
Why a size counter and not just two pointers
With head and tail alone, full and empty look identical - both have head == tail. Keeping an explicit size resolves the ambiguity. The alternative is to waste one slot deliberately.
This is what a network buffer is
Ring buffers back audio pipelines, kernel packet queues and lock-free producer/consumer channels, precisely because they never allocate after startup.
Common pitfalls
- Testing fullness with head equals tail: that is also exactly what empty looks like. Keep a size counter or sacrifice one slot.
- Forgetting the modulo on one of the two updates - the write position or the head advance - so an index eventually runs off the array.
- Leaving the full-buffer policy undecided: when producers outpace consumers the ring must reject, block or overwrite, and the choice belongs in the design, not in production surprises.
- Paying for division in hot paths: production ring buffers often pick power-of-two capacities so the wrap becomes a bitmask instead of a modulo.
Where it is used
- Audio pipelines, where a fixed buffer absorbs jitter between producer and consumer.
- Kernel packet queues - the network card writes in, the OS drains out.
- Lock-free producer-consumer channels between threads, allocation-free after startup.
- Keyboard and UART input buffers in embedded systems that have no allocator at all.
Frequently asked questions
What is the time complexity of a circular queue?
Every operation is O(1) worst case - enqueue is one modulo and one write, dequeue is one read and one modulo advance. Space is O(capacity), fixed at construction, which is the point: the memory footprint never changes however many operations flow through.
How do you tell a full circular queue from an empty one?
With head and tail pointers alone you cannot - both states have head equal to tail. Either keep an explicit size counter, as this implementation does, or deliberately leave one slot unused so that full and empty become distinguishable conditions.
What happens when a circular queue is full?
One of three things, and it is a design decision: reject the write, as this implementation does; block the producer until space appears; or overwrite the oldest element, as bounded logs do. A ring buffer never grows - fixed capacity is its defining property, not a limitation.
Why use a circular queue instead of a normal queue?
A plain array queue strands the slots behind front as dead space, and a growable one allocates as it expands. The ring reuses every slot via modulo and never allocates after startup - which is why audio, networking and embedded code, where allocation mid-stream is unacceptable, rely on it.