Circular Queue: Efficient Fixed-Size FIFO Buffer

Circular Queue (Ring Buffer)

A circular queue is a fixed-size queue implemented using an array where the rear wraps around to the beginning when it reaches the end. This eliminates the need to shift elements after dequeue operations.

The Problem with Linear Queues

In a simple array-based queue, dequeue leaves unused space at the front:

Initial:    [A, B, C, _, _]  front=0, rear=3
Dequeue A:  [_, B, C, _, _]  front=1, rear=3
Dequeue B:  [_, _, C, _, _]  front=2, rear=3
Enqueue D:  [_, _, C, D, _]  front=2, rear=4
Enqueue E:  [_, _, C, D, E]  front=2, rear=5 <- array full!

Slots 0 and 1 are wasted even though the queue only has 3 elements.

Circular Solution

With modular arithmetic, the rear wraps around:

rear = (rear + 1) % capacity
front = (front + 1) % capacity

Initial:    [A, B, C, _, _]  front=0, rear=3, size=3
Dequeue A:  [_, B, C, _, _]  front=1, rear=3, size=2
Dequeue B:  [_, _, C, _, _]  front=2, rear=3, size=1
Enqueue D:  [_, _, C, D, _]  front=2, rear=4, size=2
Enqueue E:  [_, _, C, D, E]  front=2, rear=0, size=3
Enqueue F:  [F, _, C, D, E]  front=2, rear=1, size=4

Now slots 0 and 1 are reused!

Full vs Empty Detection

Both full and empty states have front == rear, so we need a way to distinguish:

1. Size counter: Track the number of elements. Full when size == capacity. Empty when size == 0.
2. Waste one slot: Full when (rear + 1) % capacity == front. Empty when front == rear. This wastes one slot but avoids a separate counter.
3. Boolean flag: Use a full flag that is set when rear catches up to front.

Operations

enqueue(x):
    if is_full(): throw "overflow"
    array[rear] = x
    rear = (rear + 1) % capacity
    size++

dequeue():
    if is_empty(): throw "underflow"
    x = array[front]
    front = (front + 1) % capacity
    size--
    return x

Applications

• Producer-consumer buffers: Kernel I/O buffers, audio/video streaming buffers
• Network packet buffers: Fixed-size buffers in routers and switches
• Keyboard input buffer: OS stores keystrokes in a circular buffer
• Logging: Fixed-size log buffers that overwrite oldest entries when full