Lesson 15 · Linear structures

Circular Queues

A circular queue (or ring buffer) is an array-backed queue that connects its logical end back to its beginning. It solves the array-shifting problem of standard queues by reusing empty spaces at the front.

The Empty Space Problem

As a naive array-backed queue operates without shifting, the front and rear pointers both move continuously to the right. Eventually, rear hits the end of the array.

Even if you have dequeued many elements, leaving empty spaces at the beginning of the array, the queue reports that it is 'full' because rear cannot advance.

Pointers only move right
Empty space at the front is wasted
The array becomes useless once rear hits the end

Wrapping Around with Modulo

A circular queue solves this by conceptually bending the array into a circle. When the rear pointer reaches the end, it wraps around back to index 0 (if index 0 is empty).

This is achieved using modulo arithmetic: next_index = (current_index + 1) % capacity. This ensures the pointers loop infinitely within the array bounds.

Array remains linear in memory
Pointers wrap around logically
% capacity keeps indices in bounds

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.

Code example

Array-Backed Ring Buffer

class CircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.k = k
        self.front = 0
        self.size = 0
    def enqueue(self, val):
        if self.size == self.k: return False
        rear = (self.front + self.size) % self.k
        self.q[rear] = val
        self.size += 1
    def dequeue(self):
        if self.size == 0: return False
        self.front = (self.front + 1) % self.k
        self.size -= 1
cq = CircularQueue(3)
for value in 'ABC':
    cq.enqueue(value)
cq.dequeue()
cq.enqueue('D')
print('Array physically contains [' + ', '.join(cq.q) + ']')

#include <vector>
using namespace std;

class CircularQueue {
    vector<int> q; int k, front, size;
public:
    CircularQueue(int k) : k(k), front(0), size(0) { q.resize(k); }
    bool enqueue(int val) {
        if (size == k) return false;
        int rear = (front + size) % k;
        q[rear] = val; size++; return true;
    }
    bool dequeue() {
        if (size == 0) return false;
        front = (front + 1) % k; size--; return true;
    }
};

class CircularQueue {
    int[] q; int k, front, size;
    public CircularQueue(int k) {
        this.k = k; this.q = new int[k];
        this.front = 0; this.size = 0;
    }
    public boolean enqueue(int val) {
        if (size == k) return false;
        int rear = (front + size) % k;
        q[rear] = val; size++; return true;
    }
    public boolean dequeue() {
        if (size == 0) return false;
        front = (front + 1) % k; size--; return true;
    }
}

InputCapacity 3. Enqueue A, B, C. Dequeue A. Enqueue D.

OutputArray physically contains [D, B, C]

Example

Run the example step by step

Output

Tracking Full vs Empty

In a circular queue, the condition for 'empty' is usually front == rear. But if the queue wraps around completely, the condition for 'full' might also look like front == rear.

To distinguish between full and empty, implementations either maintain a separate size counter, or intentionally leave one slot empty so 'full' is detected when (rear + 1) % capacity == front.

size variable makes logic trivial
Alternatively, leave one slot empty
Overwriting old data turns it into a 'Ring Buffer'

Ring Buffers in Systems

When a circular queue is allowed to overwrite old data when full, it is called a Ring Buffer. This is extensively used in systems programming.

For example, capturing the last 100 lines of a log file, buffering audio for playback, or tracking recent network packets. It provides a highly efficient, lock-less data stream of a fixed maximum size.

Constant O(1) memory footprint
No garbage collection or reallocation
Perfect for continuous streams of data