Lesson 14 · Linear structures

Circular Queues

A circular queue treats one fixed array as a ring: instead of shifting elements when the front advances, the indices wrap with modulo arithmetic. Enqueue and dequeue are both O(1) with no allocation and no copying, which is why the same structure is called a ring buffer in systems code.

The Space a Linear Queue Throws Away

Implement a queue on a plain array with a front and a rear index. Enqueue writes at rear and increments it; dequeue reads at front and increments that. Both are O(1), which looks like a success.

The problem appears after a few operations. front only ever moves forward, so the slots it has passed are abandoned — occupied by nothing but unreachable for reuse. After enqueuing and dequeuing repeatedly, rear reaches the end of the array while most of the array sits empty behind front.

At that point the queue reports itself full while holding almost nothing. A 1000-slot array that has processed 1000 items is exhausted even if only three items are currently queued.

The obvious repair — shift everything left when the queue fills — makes dequeue or the compaction step O(n), which defeats the purpose. This is exactly what Python's list.pop(0) does on every call, and it is why draining a list-as-queue is O(n²).

The actual fix is to stop treating the array as a line and start treating it as a ring. When rear reaches the end, it continues at index 0, reusing the space front has already vacated. The array is finite but the indices cycle through it indefinitely, so no slot is ever wasted.

front advancing leaves earlier slots unreachable
The queue reports full while most of the array is unused
Shifting to compact makes an operation O(n)
Treat the array as a ring so freed slots come back into use

Modulo Does the Wrapping

The mechanism is one operator. Advancing any index becomes i = (i + 1) % capacity, so incrementing past the last slot yields 0 rather than an out-of-bounds value.

Enqueue writes at rear, then advances rear with that expression. Dequeue reads at front, then advances front the same way. Both remain O(1) — a modulo is a single instruction — and no element ever moves.

That is genuinely the whole trick. The rest of the design is bookkeeping around it.

When the capacity is a power of two, the modulo can be replaced by a bitwise and: i = (i + 1) & (capacity - 1). This is measurably faster than a division and is why performance-critical ring buffers — network stacks, audio pipelines, lock-free queues — always size themselves to a power of two. It is a genuine engineering detail rather than micro-optimisation trivia, since these buffers run on every packet or every audio frame.

An alternative to modulo entirely is to let the indices grow without bound and mask only when addressing the array. head and tail become monotonically increasing counters, the number of elements is simply tail - head with no ambiguity at all, and the array index is tail & (capacity - 1). This is the design most lock-free ring buffers use, because it sidesteps the full-versus-empty problem described next — at the cost of needing to handle integer overflow, which with 64-bit counters is not a practical concern.

Whichever form you choose, the invariant to hold in mind is that front is where the next element leaves and rear is where the next element arrives, and both chase each other around the ring.

(i + 1) % capacity is the entire wrapping mechanism
Both operations stay O(1) and no element ever moves
A power-of-two capacity replaces modulo with a cheaper bitmask
Unbounded counters with masked indexing avoid the ambiguity below

Full and Empty Look Identical

This is the one genuine subtlety of the structure, and it is where exam questions concentrate.

With indices that wrap, the queue is empty when front == rear — nothing has been added since the last removal. But after the queue fills completely, rear wraps all the way around and lands back on front, so the queue is full when front == rear as well.

The same condition describes both states. Reading the indices alone cannot distinguish a queue holding nothing from one holding everything, and an implementation that does not resolve this will either overwrite live data or reject valid insertions.

There are two standard resolutions, and knowing both is worth more than knowing one.

Keep an explicit count. Maintain a size field incremented on enqueue and decremented on dequeue. Empty is size == 0, full is size == capacity, and the ambiguity disappears entirely. It costs one integer and uses the full capacity. The drawback is that size is a third piece of shared state, which complicates lock-free implementations where two indices can be updated atomically but three cannot.

Leave one slot unused. Declare the queue full when (rear + 1) % capacity == front, so rear is never allowed to catch front from behind. Empty stays front == rear, and the two conditions are now distinct. It costs one slot of capacity — an array of size n holds n−1 elements — and requires no extra state, which is why it is the classic textbook answer and the choice for concurrent buffers.

A third option is the monotonic counter approach from the previous section, where tail - head gives the count directly and neither state is ambiguous. It is the cleanest of the three when the language's integer arithmetic cooperates.

Resolving the ambiguity
Approach	Empty test	Full test	Cost
Explicit count	`size == 0`	`size == capacity`	One integer; full capacity used
Sacrifice a slot	`front == rear`	`(rear+1) % cap == front`	One slot; no extra state
Unbounded counters	`tail == head`	`tail - head == cap`	Needs wide integers

front == rear means both empty and full — the core ambiguity
A size counter resolves it and uses every slot
Sacrificing one slot resolves it with no extra shared state
Concurrency favours the slot sacrifice — fewer variables to update atomically

Key reference

Terms, operations, and practical uses

Buffer mechanics

Modulo ArithmeticUsing the % operator to wrap a pointer back to 0 when it exceeds the array's capacity.
Wrap AroundThe conceptual behavior of a linear array behaving like a connected ring.
Fixed CapacityCircular queues are usually allocated once with a maximum size and never resized to maintain performance.

State tracking

Empty StateUsually detected when the front pointer equals the rear pointer.
Full StateDetected when the next position of the rear pointer equals the front pointer.
Sacrificial SlotA common implementation trick where one slot in the array is intentionally left empty to distinguish Full from Empty.

System applications

Ring BufferA circular queue that is allowed to overwrite the oldest data when full, creating a sliding window of recent history.
Audio StreamingBuffering incoming audio data into a ring to prevent stuttering while the sound card reads from it.
Network PacketsNetwork cards use circular rings of descriptors in hardware to manage incoming and outgoing packets efficiently.

Implementation

Array-Backed Ring Buffer

class CircularQueue:
    """Fixed-capacity ring buffer. Nothing shifts: the indices wrap."""

    def __init__(self, k):
        self.q = [None] * k
        self.k = k
        self.front = 0
        self.size = 0          # an explicit size makes full and empty distinguishable

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.k

    def enqueue(self, val):
        if self.is_full():
            return False
        rear = (self.front + self.size) % self.k   # wrap with modulo
        self.q[rear] = val
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return False
        self.front = (self.front + 1) % self.k     # advance, never shift
        self.size -= 1
        return True

    def to_list(self):
        """Read the live items in logical order, starting at front."""
        return [self.q[(self.front + i) % self.k] for i in range(self.size)]


cq = CircularQueue(4)
for value in 'ABC':
    cq.enqueue(value)
cq.dequeue()               # A leaves
cq.dequeue()               # B leaves; slots 0 and 1 are now reusable
cq.enqueue('D')            # goes to slot 3
cq.enqueue('E')            # wraps back to slot 0

print('Array physically holds [' + ', '.join(str(v) for v in cq.q) + ']')
print('Queue logically holds  [' + ', '.join(cq.to_list()) + ']')

#include <iostream>
#include <vector>
#include <string>
using namespace std;
class CircularQueue {
    vector<string> q;
    int k, front_, size_;
    public:
    CircularQueue(int cap) : q(cap, "-"), k(cap), front_(0), size_(0) {
    }
    bool isEmpty() const {
        return size_ == 0;
    }
    bool isFull() const {
        return size_ == k;
    }
    bool enqueue(const string& val) {
        if (isFull()) return false;
        int rear = (front_ + size_) % k; // wrap with modulo
        q[rear] = val;
        size_++;
        return true;
    }
    bool dequeue() {
        if (isEmpty()) return false;
        front_ = (front_ + 1) % k; // advance, never shift
        size_--;
        return true;
    }
    void print() const {
        cout << "Array physically holds [";
        for(int i = 0; i < k; i++) {
            if (i) cout << ", ";
            cout << q[i];
        }
        cout << "]\n";
        cout << "Queue logically holds  [";
        for(int i = 0; i < size_; i++) {
            if (i) cout << ", ";
            cout << q[(front_ + i) % k];
        }
        cout << "]\n";
    }
};
int main() {
    CircularQueue cq(4);
    cq.enqueue("A");
    cq.enqueue("B");
    cq.enqueue("C");
    cq.dequeue(); // A leaves
    cq.dequeue(); // B leaves
    cq.enqueue("D"); // slot 3
    cq.enqueue("E"); // wraps to slot 0
    cq.print();
}

import java.util.StringJoiner;
public class Main {
    static class CircularQueue {
        private final String[] q;
        private final int k;
        private int front = 0, size = 0;
        CircularQueue(int cap) {
            k = cap;
            q = new String[cap];
            java.util.Arrays.fill(q, "-");
        }
        boolean isEmpty() {
            return size == 0;
        }
        boolean isFull() {
            return size == k;
        }
        boolean enqueue(String val) {
            if (isFull()) return false;
            int rear = (front + size) % k; // wrap with modulo
            q[rear] = val;
            size++;
            return true;
        }
        boolean dequeue() {
            if (isEmpty()) return false;
            front = (front + 1) % k; // advance, never shift
            size--;
            return true;
        }
        void print() {
            StringJoiner phys = new StringJoiner(", ", "[", "]");
            for (String s : q) phys.add(s);
            StringJoiner logi = new StringJoiner(", ", "[", "]");
            for (int i = 0; i < size; i++) logi.add(q[(front + i) % k]);
            System.out.println("Array physically holds " + phys);
            System.out.println("Queue logically holds  " + logi);
        }
    }
    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(4);
        cq.enqueue("A");
        cq.enqueue("B");
        cq.enqueue("C");
        cq.dequeue(); // A leaves
        cq.dequeue(); // B leaves
        cq.enqueue("D"); // slot 3
        cq.enqueue("E"); // wraps to slot 0
        cq.print();
    }
}

Watch it run

Step through it

Running on Capacity 4. Enqueue A, B, C. Dequeue A, B. Enqueue D, E — watch rear wrap.

Output

Read all 10 Steps

Empty queue One fixed block of 4 slots. front marks the first live item, size counts them. Nothing ever shifts — only the indices move.
Enqueue A rear = (front + size) % 4 = 0. Write A, size becomes 1. No shifting, so this is O(1).
Enqueue B, C rear = (0+1)%4 = 1, then (0+2)%4 = 2. Size is 3; one slot is still free.
Dequeue A Do not shift anything. Just advance front = (0+1)%4 = 1 and drop size to 2. A is still in memory but is no longer part of the queue.
Dequeue B front = (1+1)%4 = 2, size 1. Two slots at the front are now reusable — this is precisely the space a naive linear queue would leak.
Enqueue D rear = (2+1)%4 = 3. Write D into the last physical slot; size is 2.
Enqueue E — the wrap rear = (2+2)%4 = 0. The modulo sends the write back to slot 0, reclaiming the space A left behind. This single expression is the whole data structure.
Reading it back The queue is C, D, E — start at front and step forward with modulo. Logical order and physical order no longer match, and that is fine.
Full and empty look identical If we only tracked front and rear, then full and empty would both give front == rear — indistinguishable. Two standard fixes: keep an explicit size counter (used here), or waste one slot so full means (rear+1)%N == front.
Why it is called a ring buffer Fixed memory, O(1) enqueue and dequeue, no shifting and no allocation — which is why UART drivers, audio pipelines and log buffers all use this shape.

Why Systems Code Runs on Ring Buffers

Circular queues are far more common in infrastructure than in application code, and the reasons are specific.

Fixed memory, allocated once. A ring buffer's capacity is decided up front and never changes, so there is no allocation during operation and no unpredictable pause from growing. For a kernel handling interrupts or an audio callback with a deadline measured in microseconds, an allocation at the wrong moment is a failure, not a slowdown.

Bounded by design. An unbounded queue converts a throughput problem into unbounded memory growth and a much later, worse failure. A ring buffer forces the decision early: when it fills, you must block the producer, drop the newest item, drop the oldest, or reject with an error. There is no default, and choosing wrongly is how systems fail under load — but at least the choice is explicit.

For streaming data, dropping the oldest is often correct: in an audio buffer or a live video feed, stale frames are worthless, so overwriting them is the right behaviour rather than a compromise.

Contiguous and cache-friendly. The elements sit in one array, so sequential access is prefetched. A linked-list queue chases pointers across scattered memory and allocates a node per element.

Single producer, single consumer without locks. This is the property that matters most in practice. If exactly one thread enqueues and one dequeues, the producer touches only rear and the consumer only front, so with appropriate memory ordering the queue needs no mutex at all. Lock-free SPSC ring buffers are the standard mechanism for moving data between a real-time audio thread and the rest of an application, and between a network driver and the kernel.

Concrete examples: keyboard and network interface input buffers, audio and video streaming pipelines, log buffers that keep the most recent n entries, the Linux kernel's kfifo, and producer-consumer handoffs generally.

The cost of all this is the fixed capacity. If the number of elements is genuinely unbounded, a circular queue is the wrong structure — use a linked-list queue or a dynamic array that grows, and accept the allocation.

Fixed allocation means no pauses — essential for real-time paths
A bounded queue forces an explicit overflow policy
Single-producer single-consumer needs no lock: separate indices
Wrong choice when the element count is genuinely unbounded