Circular Queue
A queue in a fixed array never shifts anything. The front and rear are just indices, and when one reaches the last slot it wraps to slot 0. A slot freed at the front gets reused at the rear, so the array is a ring.
An empty queue in an array of 4 slots. Items join at the rear and leave from the front, and both indices wrap around to slot 0 instead of shifting anything.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.
Rear is at slot 0, 1 of 4 slots used. Where does 3 go?
Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.
Rear is at slot 1, 2 of 4 slots used. Where does 9 go?
Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.
Front is at slot 0 with 5. After removing it, where is the front?
Answer: The next slot. The front steps forward to slot 1. Slot 0 is free for the rear to reuse.
Front is at slot 1 with 3. After removing it, where is the front?
Answer: The next slot. The front steps forward to slot 2. Slot 1 is free for the rear to reuse.
Rear is at slot 2, 1 of 4 slots used. Where does 7 go?
Answer: The next slot. There is room and the rear is not at the last slot, so it just steps forward.
Rear is at slot 3, 2 of 4 slots used. Where does 2 go?
Answer: Wraps to slot 0. Slot 3 is the last one, and there is room, so the index wraps: (3 + 1) mod 4 = 0.
How it runs, step by step
An empty queue in an array of 4 slots. Items join at the rear and leave from the front, and both indices wrap around to slot 0 instead of shifting anything.
Empty circular queue with 4 slots. Running 8 operations: enqueue 5, enqueue 3, enqueue 9, dequeue, dequeue, enqueue 7, enqueue 2, peek.
enqueue 5 into slot 0, where the front already waits. Size 1.
Enqueue 5 into slot 0. Size 1.
enqueue 3 into slot 1, one past the old rear. Size 2.
Enqueue 3 into slot 1. Size 2.
enqueue 9 into slot 2, one past the old rear. Size 3.
Enqueue 9 into slot 2. Size 3.
dequeue returns 5 from slot 0. Nothing shifts. The front moves to slot 1. Size 2.
Dequeue removes 5 from slot 0. The front moves to slot 1.
dequeue returns 3 from slot 1. Nothing shifts. The front moves to slot 2. Size 1.
Dequeue removes 3 from slot 1. The front moves to slot 2.
enqueue 7 into slot 3, one past the old rear. Size 2.
Enqueue 7 into slot 3. Size 2.
enqueue 2. The rear was at the last slot, 3, so it wraps to slot 0. That slot was freed by an earlier dequeue. Size 3.
Enqueue 2. The rear wraps around to slot 0. Size 3.
peek shows the front, 9 in slot 2, without removing it.
Peek shows the front item, 9. Nothing changes.
Done: 5 enqueues, 2 dequeues, 1 wrap. 3 items left, front at slot 2. Every operation was O(1) because nothing ever shifted.
Done. 3 items remain, with the front at slot 2. 1 wrap around the array.
Remember
- Front and rear are indices into a fixed array. Dequeue moves the front, it never shifts items.
- The next slot is (index + 1) mod capacity, which is how a pointer wraps from the last slot to 0.
- Keep a size counter. Front equal to rear looks the same when the queue is empty and when it is full.
Topics covered
Where this is used
Operating systemsThe Linux kernel log
Everything printk writes goes into a fixed ring buffer, and dmesg just reads that ring. A driver may log from an interrupt handler, where allocating memory is not allowed, so the buffer has to be preallocated and bounded, and the oldest lines are overwritten rather than the buffer growing. That is why the earliest boot messages quietly disappear from dmesg on a machine that logs heavily.
AudioReal-time audio buffers
ALSA gives an application a fixed ring of sample frames with two pointers into it: the sound hardware advances one as it plays or captures, the application advances the other as it fills or drains, each at its own pace. Neither side ever waits on an allocation, which a callback with a few milliseconds of deadline cannot afford, so JACK ships a lock-free ring buffer of its own for handing samples to and from the processing thread. An underrun is nothing more exotic than one pointer catching up to the other before the next block was ready.
NetworkingNetwork card descriptor rings
A NIC and its driver share a ring of packet descriptors: the card advances a write index as frames arrive, the driver advances a read index as it consumes them. The ring must be fixed because it is DMA-mapped memory the hardware writes into directly, and the only thing the two sides exchange is a pair of indices, so there is no lock on the packet path. DPDK hands these same rings straight to user space.
ConcurrencyThe LMAX Disruptor
The queue behind the LMAX trading exchange is a circular queue with a power-of-two capacity and entries allocated once at startup. Because slots are reused rather than allocated per message, passing millions of events a second creates no garbage, and the wrap is an AND rather than a division. Producers and consumers coordinate purely by publishing sequence numbers into that ring.
Why it works this way
Three ways to tell empty from full
With nothing but a head and a tail index there are three standard fixes. Keep a separate size counter, as the code here does. Leave one slot permanently unused, so full is (tail + 1) % capacity == head, which costs a slot but keeps all the state in the two indices. Or let head and tail count every item ever enqueued and dequeued, never wrapping, and apply the modulo only when indexing. The two index-only forms both suit a ring shared between a single producer and a single consumer, because each side writes only its own index and reads the other's, so no lock is needed on the fast path. The never-wrapping form is usually the one picked of the two: it uses every slot, and tail - head is the exact count rather than something that has to be reconstructed.
Why capacity is almost always a power of two
A % whose divisor the compiler cannot see is a real integer division, far slower than the arithmetic around it, on a path that is meant to be a handful of instructions. When capacity is a power of two, index & (capacity - 1) gives the same answer in one instruction. That is why the Linux kernel's circular buffer helpers, the CIRC_CNT and CIRC_SPACE macros, are defined only for power-of-two buffers, and why the LMAX Disruptor rejects a ring size that is not one. It also makes the never-wrapping counter form safe: an unsigned counter that rolls over at 2^32 lands exactly where the mask expects, because the capacity divides 2^32, so tail - head is still the correct count. In C or C++, declare those counters signed instead and the overflow is undefined behaviour, which is the classic bug in hand-rolled ring buffers.
Why dequeue writes null into the slot it just read
The queue works without that line: size already says the slot is free, and the next enqueue will overwrite it. But in a garbage collected language the array still holds a reference, so the queue keeps the object alive long after the consumer finished with it, and a long-lived queue quietly pins one dead object per slot. Java's ArrayBlockingQueue, which is a circular array queue with exactly this shape, clears the slot on every take for that reason, and ArrayDeque does the same when it removes an element.
What happens when it is full is a policy decision
Returning false is one answer. The other two are to overwrite the oldest item, advancing head along with the write index, which is what a log or telemetry ring does, and to block until a consumer frees a slot, which is the bounded buffer of the producer-consumer problem. Overwriting never stalls the producer but drops data silently; blocking keeps every item but lets one slow consumer stall a fast producer. Picking the wrong one is how a monitoring agent ends up pausing the service it is supposed to be watching.
Read more
- Circular bufferWikipedia
- Circular buffersLinux kernel documentation · kernel.org
- Producer-consumer problemWikipedia
- LMAX DisruptorLMAX Exchange
- Queue implemented with an array, visualisedUSF