Circular Queue - Learning Module

Loading content...

0/276

Circular Queue: Wrapping Around the Array

From Line to Ring — The Elegant Solution

In the previous page, we discovered a fundamental flaw in linear queue implementations: the wasted space problem. Once elements are dequeued, their slots become permanently unusable, eventually exhausting the queue even when most of its capacity is empty.

The solution lies in a simple but powerful conceptual shift: instead of treating the array as a straight line with a beginning and end, we treat it as a ring where the last position connects back to the first. This structure is called a circular queue, ring buffer, or circular buffer.

This page explores the mechanics of circular queues in detail, showing how a single mathematical operation—the modulus—transforms an impractical data structure into an elegant, efficient one.

What You Will Learn

By the end of this page, you will understand: (1) The conceptual model of circular queues as ring structures, (2) How modular arithmetic enables pointer wraparound, (3) Step-by-step implementation of enqueue and dequeue with wraparound, and (4) Visual tracing of circular queue operations through multiple cycles.

The Ring Buffer Concept

A circular queue (or ring buffer) is a queue implementation that treats the underlying array as if its ends were connected, forming a continuous loop. When a pointer reaches the last index and needs to advance, it "wraps around" to index 0.

Mental Model — From Line to Circle:

Consider an array of 5 elements. In the linear model:

Linear View:
[0] → [1] → [2] → [3] → [4] → (end, blocked)

In the circular model, we connect the end back to the beginning:

Circular View:
    [0]
   ↙   ↘
 [4]     [1]
   ↖   ↗
 [3] ← [2]

Now there's no "end"—just a continuous cycle of positions. After position 4 comes position 0, after 0 comes 1, and so on indefinitely.

Real-World Ring Buffers

Ring buffers are ubiquitous in systems programming. Audio/video streaming uses them to buffer frames. Network drivers use them for packet queues. Operating systems use them for I/O buffers. The Linux kernel's kfifo (kernel FIFO) is a sophisticated ring buffer implementation. Understanding circular queues gives you insight into how real systems handle data flow.

Why "Circular" Works for Queues:

Recall the queue contract:

Enqueue: Add to the rear (rear advances)
Dequeue: Remove from the front (front advances)

In a linear queue, front chases rear through the array. Once rear hits the end, the chase is over—even if front has vacated early positions.

In a circular queue, rear can wrap around and start filling those vacated positions. Front continues chasing rear around the ring. The chase never ends (until the queue is truly full).

The Key Invariant:

At any moment, the valid queue elements occupy a contiguous segment of the ring, from front to rear (following the circular direction). This segment may wrap around from the array's end to its beginning:

Non-wrapped (elements in middle):
[ ] [ ] [A] [B] [C] [ ] [ ]
         ↑       ↑
       front    rear

Wrapped (elements span the boundary):
[D] [E] [ ] [ ] [ ] [A] [B] [C]
     ↑               ↑
    rear           front

In the wrapped case, the queue contains elements at indices 5, 6, 7, 0, 1 (in that logical order).

Modular Arithmetic — The Magic Behind Wraparound

The key to implementing circular queues is modular arithmetic—specifically, the modulus operator (%). This operator returns the remainder after division.

The Core Formula:

newIndex = (currentIndex + 1) % capacity

This single line handles all wraparound cases:

If currentIndex + 1 < capacity: returns currentIndex + 1 (normal increment)
If currentIndex + 1 == capacity: returns 0 (wraparound!)

Walkthrough with Capacity 5:

modular-arithmetic-demo.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const capacity = 5;
 
// Normal increments (no wraparound)
console.log((0 + 1) % 5);  // 1 → next index after 0
console.log((1 + 1) % 5);  // 2 → next index after 1
console.log((2 + 1) % 5);  // 3 → next index after 2
console.log((3 + 1) % 5);  // 4 → next index after 3
 
// Wraparound case
console.log((4 + 1) % 5);  // 0 → wraps from 4 back to 0!
 
// Continuing the cycle
console.log((0 + 1) % 5);  // 1 → cycle continues
console.log((1 + 1) % 5);  // 2 → and on forever
 
/* The sequence: 0 → 1 → 2 → 3 → 4 → 0 → 1 → 2 → 3 → 4 → 0 → ...
   This is exactly the behavior we need for circular indexing! */

Why Modulus Works:

The modulus operator a % b computes the remainder when a is divided by b. For non-negative integers:

5 % 5 = 0 (5 goes into 5 exactly once, remainder 0)
6 % 5 = 1 (5 goes into 6 once, remainder 1)
4 % 5 = 4 (5 goes into 4 zero times, remainder 4)

This means any calculation that overflows the array bounds automatically wraps to a valid index.

Generalizing to Any Offset:

You can advance by more than one position:

// Advance by k positions
newIndex = (currentIndex + k) % capacity

// Go backward by 1 (with care for negative numbers)
newIndex = (currentIndex - 1 + capacity) % capacity

The addition of capacity before the modulus handles the case where subtraction would yield a negative number (which JavaScript's % doesn't handle well).

Language-Specific Modulus Behavior

In some languages (like Python), the modulus operator handles negative numbers gracefully. In others (like JavaScript, Java, C++), negative modulus can return negative results. When moving backward in a circular queue, always add the capacity before taking the modulus to ensure positive indices: (index - 1 + capacity) % capacity.

Circular Queue Structure and Initialization

Let's define the structure of a circular queue. The fundamental components are the same as a linear queue—array, front, rear, size, capacity—but their behavior differs due to wraparound.

Pointer Conventions:

There are two common conventions for what rear represents:

Rear points to the last element: rear is the index of the most recently added element
Rear points to the next empty slot: rear is where the next element will be placed

We'll use convention 1 (rear points to the last element) with a separate size counter. This makes the full/empty detection simpler.

circular-queue-structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class CircularQueue<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;  // Explicit size counter
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be positive");
        }
        
        this.capacity = capacity;
        this.data = new Array(capacity);
        
        // Initial state: queue is empty
        this.front = 0;
        this.rear = -1;  // No elements yet (will become valid on first enqueue)
        this.count = 0;
    }
 
    // isEmpty: O(1) - Queue has no elements
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    // isFull: O(1) - Queue has reached capacity
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    // size: O(1) - Current number of elements
    size(): number {
        return this.count;
    }
 
    // getCapacity: O(1) - Maximum possible elements
    getCapacity(): number {
        return this.capacity;
    }
}

Initial State Visualization:

Capacity: 5

           front
             ↓
Indices: [0]  [1]  [2]  [3]  [4]
Data:    [ ]  [ ]  [ ]  [ ]  [ ]
             ↑
           rear = -1 (no valid element yet)
           
count = 0, isEmpty() = true, isFull() = false

Why Use a Separate Count?

Using an explicit count variable simplifies the implementation significantly:

Easy Full/Empty Detection: count === 0 means empty; count === capacity means full
No Ambiguity: Without a counter, front === rear can mean both empty and full
O(1) Size Queries: Instantly know how many elements exist

Some implementations avoid the counter by sacrificing one slot (using only capacity - 1 elements), but the counter approach is cleaner.

Implementing Circular Enqueue

The enqueue operation in a circular queue is similar to the linear version, except we use modular arithmetic to wrap the rear pointer.

Algorithm:

Check if the queue is full (reject if so)
Advance rear using modular arithmetic: rear = (rear + 1) % capacity
Place the element at the new rear position
Increment the count

circular-enqueue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Enqueue: O(1) - Add element to rear with circular wraparound
enqueue(element: T): void {
    if (this.isFull()) {
        throw new Error("Queue Overflow: Cannot enqueue to a full queue");
    }
    
    // Circular increment: wraps from (capacity-1) to 0
    this.rear = (this.rear + 1) % this.capacity;
    
    // Place element at new rear position
    this.data[this.rear] = element;
    
    // Update count
    this.count++;
}
 
/* Example walkthrough with capacity 5:
 
Initial: front=0, rear=-1, count=0
         [_] [_] [_] [_] [_]
 
enqueue('A'):
  rear = (-1 + 1) % 5 = 0
  data[0] = 'A', count = 1
         [A] [_] [_] [_] [_]
          ↑ front/rear
 
enqueue('B'):
  rear = (0 + 1) % 5 = 1
  data[1] = 'B', count = 2
         [A] [B] [_] [_] [_]
          ↑   ↑
        front rear
 
enqueue('C'), enqueue('D'), enqueue('E'):
         [A] [B] [C] [D] [E]   count = 5 (FULL)
          ↑               ↑
        front            rear
*/

Handling the -1 Initial Rear

When rear starts at -1 and we compute (-1 + 1) % 5, we get 0. This correctly positions the first element at index 0. The modulus operation handles this edge case naturally.

The Wraparound in Action:

Now let's see what happens after some dequeues, when rear needs to wrap around:

wraparound-enqueue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* Continuing from a state after some operations:
 
State: front=2, rear=4, count=3
       [_] [_] [C] [D] [E]
                ↑       ↑
              front    rear
 
The queue has 3 elements (C, D, E) with 2 empty slots at the front.
 
enqueue('F'):
  rear = (4 + 1) % 5 = 0    // WRAPAROUND!
  data[0] = 'F', count = 4
       [F] [_] [C] [D] [E]
        ↑   ↑
       rear front
 
enqueue('G'):
  rear = (0 + 1) % 5 = 1
  data[1] = 'G', count = 5 (FULL)
       [F] [G] [C] [D] [E]
            ↑   ↑
          rear front
 
Now the logical queue order is: C, D, E, F, G
- front points to C (index 2)
- rear points to G (index 1)
- Elements "wrap around" from the end to the beginning!
*/

Space Reclaimed!

Unlike the linear queue, we've now filled slots 0 and 1 that were previously freed by dequeue. The circular queue reuses all available space. This is exactly the behavior we wanted—O(1) enqueue with perfect space utilization.

Implementing Circular Dequeue

The dequeue operation removes and returns the front element, then advances the front pointer using the same modular arithmetic.

Algorithm:

Check if the queue is empty (reject if so)
Retrieve the element at the front position
Clear the slot (optional, for garbage collection)
Advance front using modular arithmetic: front = (front + 1) % capacity
Decrement the count
Return the retrieved element

circular-dequeue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Dequeue: O(1) - Remove and return front element with circular wraparound
dequeue(): T {
    if (this.isEmpty()) {
        throw new Error("Queue Underflow: Cannot dequeue from an empty queue");
    }
    
    // Retrieve element at front
    const element = this.data[this.front] as T;
    
    // Clear the slot (helps garbage collection in GC languages)
    this.data[this.front] = undefined;
    
    // Circular increment of front pointer
    this.front = (this.front + 1) % this.capacity;
    
    // Update count
    this.count--;
    
    return element;
}
 
/* Example walkthrough:
 
State: front=2, rear=1, count=5 (FULL, wrapped)
       [F] [G] [C] [D] [E]
            ↑   ↑
          rear front
       
Logical order: C → D → E → F → G
 
dequeue() → returns 'C':
  element = data[2] = 'C'
  data[2] = undefined
  front = (2 + 1) % 5 = 3
  count = 4
       [F] [G] [_] [D] [E]
            ↑       ↑
          rear    front
       
dequeue() → returns 'D':
  front = (3 + 1) % 5 = 4
  count = 3
       [F] [G] [_] [_] [E]
            ↑           ↑
          rear        front
 
dequeue() → returns 'E':
  front = (4 + 1) % 5 = 0   // WRAPAROUND!
  count = 2
       [F] [G] [_] [_] [_]
        ↑   ↑
      front rear
 
Now logical order: F → G
*/

Front and Rear Dance Around the Ring:

Notice how both pointers move in the same circular direction:

Front advances clockwise when dequeuing
Rear advances clockwise when enqueuing
Front chases rear around the ring
When they meet (and count = 0), the queue is empty
When they meet (and count = capacity), the queue is full

Both pointers can be at any position, and either (or both) may wrap around during the queue's lifetime.

The Full vs Empty Ambiguity

When front = rear, how do we know if the queue is full or empty? With both states having the same pointer configuration, we need additional information—that's why we maintain the count variable. We'll explore this critical issue in detail in the next page on 'Full vs Empty Detection'.

Implementing Front (Peek)

The front (or peek) operation returns the element at the front without modifying the queue. Since the front pointer already points to this element, no modular arithmetic is needed.

circular-front.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Front/Peek: O(1) - View front element without removal
getFront(): T {
    if (this.isEmpty()) {
        throw new Error("Queue is empty: No front element");
    }
    
    return this.data[this.front] as T;
}
 
// Alternative: View rear element (sometimes useful)
getRear(): T {
    if (this.isEmpty()) {
        throw new Error("Queue is empty: No rear element");
    }
    
    return this.data[this.rear] as T;
}
 
// Peek at any position relative to front (0 = front, size-1 = rear)
peekAt(offset: number): T {
    if (offset < 0 || offset >= this.count) {
        throw new Error("Invalid offset: out of bounds");
    }
    
    // Calculate actual index with wraparound
    const actualIndex = (this.front + offset) % this.capacity;
    return this.data[actualIndex] as T;
}

The peekAt Operation:

While not part of the standard queue interface, peekAt demonstrates an important capability of circular queues: O(1) access to any position if you know the offset from the front.

State: front=3, count=4, capacity=5
       [E] [_] [_] [B] [C] [D]
        ↑           ↑
       rear       front
       
Logical order: B, C, D, E (indices 3, 4, 0, undefined at 1)

peekAt(0) → (3 + 0) % 5 = 3 → 'B' (front)
peekAt(1) → (3 + 1) % 5 = 4 → 'C'
peekAt(2) → (3 + 2) % 5 = 0 → 'D' (wrapped!)
peekAt(3) → (3 + 3) % 5 = 1 → 'E' (rear)

This random access (with logical indices) is a bonus feature of array-based queues not available in linked-list implementations.

Complete Circular Queue Implementation

Let's consolidate everything into a complete, production-ready circular queue implementation:

circular-queue-complete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/**
 * CircularQueue: A fixed-capacity queue using circular array indexing.
 * All operations are O(1) with perfect space utilization.
 */
class CircularQueue<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be a positive integer");
        }
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }
 
    /**
     * Check if queue is empty.
     * Time: O(1)
     */
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    /**
     * Check if queue is full.
     * Time: O(1)
     */
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Get current number of elements.
     * Time: O(1)
     */
    size(): number {
        return this.count;
    }
 
    /**
     * Get maximum capacity.
     * Time: O(1)
     */
    getCapacity(): number {
        return this.capacity;
    }
 
    /**
     * Add element to the rear of the queue.
     * Time: O(1)
     * @throws Error if queue is full
     */
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.rear = (this.rear + 1) % this.capacity;
        this.data[this.rear] = element;
        this.count++;
    }
 
    /**
     * Remove and return element from the front of the queue.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow");
        }
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        this.front = (this.front + 1) % this.capacity;
        this.count--;
        return element;
    }
 
    /**
     * View the front element without removing it.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
 
    /**
     * View the rear element without removing it.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    peekRear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.rear] as T;
    }
 
    /**
     * Clear all elements from the queue.
     * Time: O(n) - clears all slots for garbage collection
     */
    clear(): void {
        for (let i = 0; i < this.capacity; i++) {
            this.data[i] = undefined;
        }
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }
 
    /**
     * Convert queue to array (front to rear order).
     * Time: O(n)
     */
    toArray(): T[] {
        const result: T[] = [];
        let current = this.front;
        for (let i = 0; i < this.count; i++) {
            result.push(this.data[current] as T);
            current = (current + 1) % this.capacity;
        }
        return result;
    }
 
    /**
     * Display queue state for debugging.
     */
    display(): void {
        console.log(`Circular Queue [capacity=${this.capacity}, size=${this.count}]`);
        console.log(`  front=${this.front}, rear=${this.rear}`);
        console.log(`  data: [${this.data.map(e => e ?? '_').join(', ')}]`);
        console.log(`  logical order: [${this.toArray().join(' → ')}]`);
    }
}

Key Implementation Notes:

Generic Type <T>: The queue can hold any type
Explicit Count: Eliminates full/empty ambiguity
Slot Clearing: Setting removed slots to undefined helps garbage collection
toArray Method: Useful for debugging; iterates in logical order
Error Messages: Clear descriptions for underflow and overflow

Complexity Summary:

Operation	Time	Space
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
peek	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)
size	O(1)	O(1)
clear	O(n)	O(1)
toArray	O(n)	O(n)

Visual Trace Through Multiple Cycles

Let's trace a sequence of operations that demonstrates how the circular queue cycles through the array multiple times:

circular-queue-trace.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const queue = new CircularQueue<number>(4);
 
// Phase 1: Fill the queue
queue.enqueue(10);  // [10][__][__][__]  f=0,r=0,n=1
queue.enqueue(20);  // [10][20][__][__]  f=0,r=1,n=2
queue.enqueue(30);  // [10][20][30][__]  f=0,r=2,n=3
queue.enqueue(40);  // [10][20][30][40]  f=0,r=3,n=4 ← FULL
 
// Phase 2: Remove and add (first wraparound)
queue.dequeue();    // [__][20][30][40]  f=1,r=3,n=3  (returned 10)
queue.enqueue(50);  // [50][20][30][40]  f=1,r=0,n=4 ← rear wrapped!
 
queue.dequeue();    // [50][__][30][40]  f=2,r=0,n=3  (returned 20)
queue.enqueue(60);  // [50][60][30][40]  f=2,r=1,n=4 ← FULL again
 
// Phase 3: More cycles
queue.dequeue();    // [50][60][__][40]  f=3,r=1,n=3  (returned 30)
queue.dequeue();    // [50][60][__][__]  f=0,r=1,n=2  ← front wrapped! (returned 40)
 
// Current state: logical order is [50, 60]
// Physical: [50][60][__][__] with front=0, rear=1
 
queue.enqueue(70);  // [50][60][70][__]  f=0,r=2,n=3
queue.enqueue(80);  // [50][60][70][80]  f=0,r=3,n=4 ← FULL
 
// Drain the queue
queue.dequeue();    // [__][60][70][80]  f=1,r=3,n=3  (returned 50)
queue.dequeue();    // [__][__][70][80]  f=2,r=3,n=2  (returned 60)
queue.dequeue();    // [__][__][__][80]  f=3,r=3,n=1  (returned 70)
queue.dequeue();    // [__][__][__][__]  f=0,r=3,n=0  ← EMPTY (returned 80)
                    // front wrapped on becoming empty
 
/* Summary of wraparounds:
   - rear wrapped from 3→0 (enqueue 50)
   - front wrapped from 3→0 (dequeue 40)
   - rear completed another cycle
   - front completed another cycle
   
   The queue processed 8 elements using only 4 slots!
   In a linear queue, we would have been stuck after 4 enqueues.
*/

Unlimited Lifetime Operations

A circular queue with capacity n can process an unlimited number of elements over its lifetime, as long as no more than n are queued simultaneously. A linear queue with the same capacity could only ever process n elements total. This is the fundamental advantage of circular indexing.

Summary and Next Steps

This page established the mechanics of circular queue implementation, showing how modular arithmetic transforms arrays into efficient ring buffers.

Key Takeaways

•Circular queues treat arrays as rings, where the last index connects back to the first. This mental model enables slot reuse.
•Modular arithmetic ((index + 1) % capacity) is the key operation that enables wraparound. It works for both front and rear pointers.
•Both enqueue and dequeue remain O(1) while achieving perfect space utilization. We get the best of both worlds.
•An explicit count variable simplifies implementation by making full/empty detection trivial and providing instant size queries.
•Circular queues can process unlimited elements over their lifetime (within capacity constraints at any moment), unlike linear queues that exhaust after N operations.

What's Next:

The next page focuses on front and rear pointer management—different conventions for tracking queue boundaries and their implications. We'll explore:

Alternative pointer semantics (rear as next slot vs last element)
The mathematics of computing queue size from pointers
Edge cases and their handling

Following that, we'll tackle the critical full vs empty detection problem that challenges many circular queue implementations.

Page Complete

You now understand how circular queues work at a mechanical level. The modular arithmetic insight—treating linear indices as circular—is a powerful technique that appears in many systems programming contexts. Next, we'll examine pointer management strategies in greater depth.

Circular Queue: Wrapping Around the Array

From Line to Ring — The Elegant Solution

This page explores the mechanics of circular queues in detail, showing how a single mathematical operation—the modulus—transforms an impractical data structure into an elegant, efficient one.

What You Will Learn

The Ring Buffer Concept

Mental Model — From Line to Circle:

Consider an array of 5 elements. In the linear model:

Linear View:
[0] → [1] → [2] → [3] → [4] → (end, blocked)

In the circular model, we connect the end back to the beginning:

Circular View:
    [0]
   ↙   ↘
 [4]     [1]
   ↖   ↗
 [3] ← [2]

Now there's no "end"—just a continuous cycle of positions. After position 4 comes position 0, after 0 comes 1, and so on indefinitely.

Real-World Ring Buffers

Why "Circular" Works for Queues:

Recall the queue contract:

Enqueue: Add to the rear (rear advances)
Dequeue: Remove from the front (front advances)

In a linear queue, front chases rear through the array. Once rear hits the end, the chase is over—even if front has vacated early positions.

In a circular queue, rear can wrap around and start filling those vacated positions. Front continues chasing rear around the ring. The chase never ends (until the queue is truly full).

The Key Invariant:

Non-wrapped (elements in middle):
[ ] [ ] [A] [B] [C] [ ] [ ]
         ↑       ↑
       front    rear

Wrapped (elements span the boundary):
[D] [E] [ ] [ ] [ ] [A] [B] [C]
     ↑               ↑
    rear           front

In the wrapped case, the queue contains elements at indices 5, 6, 7, 0, 1 (in that logical order).

Modular Arithmetic — The Magic Behind Wraparound

The key to implementing circular queues is modular arithmetic—specifically, the modulus operator (%). This operator returns the remainder after division.

The Core Formula:

newIndex = (currentIndex + 1) % capacity

This single line handles all wraparound cases:

If currentIndex + 1 < capacity: returns currentIndex + 1 (normal increment)
If currentIndex + 1 == capacity: returns 0 (wraparound!)

Walkthrough with Capacity 5:

modular-arithmetic-demo.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const capacity = 5;
 
// Normal increments (no wraparound)
console.log((0 + 1) % 5);  // 1 → next index after 0
console.log((1 + 1) % 5);  // 2 → next index after 1
console.log((2 + 1) % 5);  // 3 → next index after 2
console.log((3 + 1) % 5);  // 4 → next index after 3
 
// Wraparound case
console.log((4 + 1) % 5);  // 0 → wraps from 4 back to 0!
 
// Continuing the cycle
console.log((0 + 1) % 5);  // 1 → cycle continues
console.log((1 + 1) % 5);  // 2 → and on forever
 
/* The sequence: 0 → 1 → 2 → 3 → 4 → 0 → 1 → 2 → 3 → 4 → 0 → ...
   This is exactly the behavior we need for circular indexing! */

Why Modulus Works:

The modulus operator a % b computes the remainder when a is divided by b. For non-negative integers:

5 % 5 = 0 (5 goes into 5 exactly once, remainder 0)
6 % 5 = 1 (5 goes into 6 once, remainder 1)
4 % 5 = 4 (5 goes into 4 zero times, remainder 4)

This means any calculation that overflows the array bounds automatically wraps to a valid index.

Generalizing to Any Offset:

You can advance by more than one position:

// Advance by k positions
newIndex = (currentIndex + k) % capacity

// Go backward by 1 (with care for negative numbers)
newIndex = (currentIndex - 1 + capacity) % capacity

The addition of capacity before the modulus handles the case where subtraction would yield a negative number (which JavaScript's % doesn't handle well).

Language-Specific Modulus Behavior

Circular Queue Structure and Initialization

Let's define the structure of a circular queue. The fundamental components are the same as a linear queue—array, front, rear, size, capacity—but their behavior differs due to wraparound.

Pointer Conventions:

There are two common conventions for what rear represents:

Rear points to the last element: rear is the index of the most recently added element
Rear points to the next empty slot: rear is where the next element will be placed

We'll use convention 1 (rear points to the last element) with a separate size counter. This makes the full/empty detection simpler.

circular-queue-structure.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class CircularQueue<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;  // Explicit size counter
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be positive");
        }
        
        this.capacity = capacity;
        this.data = new Array(capacity);
        
        // Initial state: queue is empty
        this.front = 0;
        this.rear = -1;  // No elements yet (will become valid on first enqueue)
        this.count = 0;
    }
 
    // isEmpty: O(1) - Queue has no elements
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    // isFull: O(1) - Queue has reached capacity
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    // size: O(1) - Current number of elements
    size(): number {
        return this.count;
    }
 
    // getCapacity: O(1) - Maximum possible elements
    getCapacity(): number {
        return this.capacity;
    }
}

Initial State Visualization:

Capacity: 5

           front
             ↓
Indices: [0]  [1]  [2]  [3]  [4]
Data:    [ ]  [ ]  [ ]  [ ]  [ ]
             ↑
           rear = -1 (no valid element yet)
           
count = 0, isEmpty() = true, isFull() = false

Why Use a Separate Count?

Using an explicit count variable simplifies the implementation significantly:

Easy Full/Empty Detection: count === 0 means empty; count === capacity means full
No Ambiguity: Without a counter, front === rear can mean both empty and full
O(1) Size Queries: Instantly know how many elements exist

Some implementations avoid the counter by sacrificing one slot (using only capacity - 1 elements), but the counter approach is cleaner.

Implementing Circular Enqueue

The enqueue operation in a circular queue is similar to the linear version, except we use modular arithmetic to wrap the rear pointer.

Algorithm:

Check if the queue is full (reject if so)
Advance rear using modular arithmetic: rear = (rear + 1) % capacity
Place the element at the new rear position
Increment the count

circular-enqueue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Enqueue: O(1) - Add element to rear with circular wraparound
enqueue(element: T): void {
    if (this.isFull()) {
        throw new Error("Queue Overflow: Cannot enqueue to a full queue");
    }
    
    // Circular increment: wraps from (capacity-1) to 0
    this.rear = (this.rear + 1) % this.capacity;
    
    // Place element at new rear position
    this.data[this.rear] = element;
    
    // Update count
    this.count++;
}
 
/* Example walkthrough with capacity 5:
 
Initial: front=0, rear=-1, count=0
         [_] [_] [_] [_] [_]
 
enqueue('A'):
  rear = (-1 + 1) % 5 = 0
  data[0] = 'A', count = 1
         [A] [_] [_] [_] [_]
          ↑ front/rear
 
enqueue('B'):
  rear = (0 + 1) % 5 = 1
  data[1] = 'B', count = 2
         [A] [B] [_] [_] [_]
          ↑   ↑
        front rear
 
enqueue('C'), enqueue('D'), enqueue('E'):
         [A] [B] [C] [D] [E]   count = 5 (FULL)
          ↑               ↑
        front            rear
*/

Handling the -1 Initial Rear

When rear starts at -1 and we compute (-1 + 1) % 5, we get 0. This correctly positions the first element at index 0. The modulus operation handles this edge case naturally.

The Wraparound in Action:

Now let's see what happens after some dequeues, when rear needs to wrap around:

wraparound-enqueue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* Continuing from a state after some operations:
 
State: front=2, rear=4, count=3
       [_] [_] [C] [D] [E]
                ↑       ↑
              front    rear
 
The queue has 3 elements (C, D, E) with 2 empty slots at the front.
 
enqueue('F'):
  rear = (4 + 1) % 5 = 0    // WRAPAROUND!
  data[0] = 'F', count = 4
       [F] [_] [C] [D] [E]
        ↑   ↑
       rear front
 
enqueue('G'):
  rear = (0 + 1) % 5 = 1
  data[1] = 'G', count = 5 (FULL)
       [F] [G] [C] [D] [E]
            ↑   ↑
          rear front
 
Now the logical queue order is: C, D, E, F, G
- front points to C (index 2)
- rear points to G (index 1)
- Elements "wrap around" from the end to the beginning!
*/

Space Reclaimed!

Implementing Circular Dequeue

The dequeue operation removes and returns the front element, then advances the front pointer using the same modular arithmetic.

Algorithm:

Check if the queue is empty (reject if so)
Retrieve the element at the front position
Clear the slot (optional, for garbage collection)
Advance front using modular arithmetic: front = (front + 1) % capacity
Decrement the count
Return the retrieved element

circular-dequeue.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Dequeue: O(1) - Remove and return front element with circular wraparound
dequeue(): T {
    if (this.isEmpty()) {
        throw new Error("Queue Underflow: Cannot dequeue from an empty queue");
    }
    
    // Retrieve element at front
    const element = this.data[this.front] as T;
    
    // Clear the slot (helps garbage collection in GC languages)
    this.data[this.front] = undefined;
    
    // Circular increment of front pointer
    this.front = (this.front + 1) % this.capacity;
    
    // Update count
    this.count--;
    
    return element;
}
 
/* Example walkthrough:
 
State: front=2, rear=1, count=5 (FULL, wrapped)
       [F] [G] [C] [D] [E]
            ↑   ↑
          rear front
       
Logical order: C → D → E → F → G
 
dequeue() → returns 'C':
  element = data[2] = 'C'
  data[2] = undefined
  front = (2 + 1) % 5 = 3
  count = 4
       [F] [G] [_] [D] [E]
            ↑       ↑
          rear    front
       
dequeue() → returns 'D':
  front = (3 + 1) % 5 = 4
  count = 3
       [F] [G] [_] [_] [E]
            ↑           ↑
          rear        front
 
dequeue() → returns 'E':
  front = (4 + 1) % 5 = 0   // WRAPAROUND!
  count = 2
       [F] [G] [_] [_] [_]
        ↑   ↑
      front rear
 
Now logical order: F → G
*/

Front and Rear Dance Around the Ring:

Notice how both pointers move in the same circular direction:

Front advances clockwise when dequeuing
Rear advances clockwise when enqueuing
Front chases rear around the ring
When they meet (and count = 0), the queue is empty
When they meet (and count = capacity), the queue is full

Both pointers can be at any position, and either (or both) may wrap around during the queue's lifetime.

The Full vs Empty Ambiguity

Implementing Front (Peek)

The front (or peek) operation returns the element at the front without modifying the queue. Since the front pointer already points to this element, no modular arithmetic is needed.

circular-front.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Front/Peek: O(1) - View front element without removal
getFront(): T {
    if (this.isEmpty()) {
        throw new Error("Queue is empty: No front element");
    }
    
    return this.data[this.front] as T;
}
 
// Alternative: View rear element (sometimes useful)
getRear(): T {
    if (this.isEmpty()) {
        throw new Error("Queue is empty: No rear element");
    }
    
    return this.data[this.rear] as T;
}
 
// Peek at any position relative to front (0 = front, size-1 = rear)
peekAt(offset: number): T {
    if (offset < 0 || offset >= this.count) {
        throw new Error("Invalid offset: out of bounds");
    }
    
    // Calculate actual index with wraparound
    const actualIndex = (this.front + offset) % this.capacity;
    return this.data[actualIndex] as T;
}

The peekAt Operation:

While not part of the standard queue interface, peekAt demonstrates an important capability of circular queues: O(1) access to any position if you know the offset from the front.

State: front=3, count=4, capacity=5
       [E] [_] [_] [B] [C] [D]
        ↑           ↑
       rear       front
       
Logical order: B, C, D, E (indices 3, 4, 0, undefined at 1)

peekAt(0) → (3 + 0) % 5 = 3 → 'B' (front)
peekAt(1) → (3 + 1) % 5 = 4 → 'C'
peekAt(2) → (3 + 2) % 5 = 0 → 'D' (wrapped!)
peekAt(3) → (3 + 3) % 5 = 1 → 'E' (rear)

This random access (with logical indices) is a bonus feature of array-based queues not available in linked-list implementations.

Complete Circular Queue Implementation

Let's consolidate everything into a complete, production-ready circular queue implementation:

circular-queue-complete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/**
 * CircularQueue: A fixed-capacity queue using circular array indexing.
 * All operations are O(1) with perfect space utilization.
 */
class CircularQueue<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        if (capacity <= 0) {
            throw new Error("Capacity must be a positive integer");
        }
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }
 
    /**
     * Check if queue is empty.
     * Time: O(1)
     */
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    /**
     * Check if queue is full.
     * Time: O(1)
     */
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Get current number of elements.
     * Time: O(1)
     */
    size(): number {
        return this.count;
    }
 
    /**
     * Get maximum capacity.
     * Time: O(1)
     */
    getCapacity(): number {
        return this.capacity;
    }
 
    /**
     * Add element to the rear of the queue.
     * Time: O(1)
     * @throws Error if queue is full
     */
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.rear = (this.rear + 1) % this.capacity;
        this.data[this.rear] = element;
        this.count++;
    }
 
    /**
     * Remove and return element from the front of the queue.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow");
        }
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        this.front = (this.front + 1) % this.capacity;
        this.count--;
        return element;
    }
 
    /**
     * View the front element without removing it.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
 
    /**
     * View the rear element without removing it.
     * Time: O(1)
     * @throws Error if queue is empty
     */
    peekRear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.rear] as T;
    }
 
    /**
     * Clear all elements from the queue.
     * Time: O(n) - clears all slots for garbage collection
     */
    clear(): void {
        for (let i = 0; i < this.capacity; i++) {
            this.data[i] = undefined;
        }
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }
 
    /**
     * Convert queue to array (front to rear order).
     * Time: O(n)
     */
    toArray(): T[] {
        const result: T[] = [];
        let current = this.front;
        for (let i = 0; i < this.count; i++) {
            result.push(this.data[current] as T);
            current = (current + 1) % this.capacity;
        }
        return result;
    }
 
    /**
     * Display queue state for debugging.
     */
    display(): void {
        console.log(`Circular Queue [capacity=${this.capacity}, size=${this.count}]`);
        console.log(`  front=${this.front}, rear=${this.rear}`);
        console.log(`  data: [${this.data.map(e => e ?? '_').join(', ')}]`);
        console.log(`  logical order: [${this.toArray().join(' → ')}]`);
    }
}

Key Implementation Notes:

Generic Type <T>: The queue can hold any type
Explicit Count: Eliminates full/empty ambiguity
Slot Clearing: Setting removed slots to undefined helps garbage collection
toArray Method: Useful for debugging; iterates in logical order
Error Messages: Clear descriptions for underflow and overflow

Complexity Summary:

Operation	Time	Space
enqueue	O(1)	O(1)
dequeue	O(1)	O(1)
peek	O(1)	O(1)
isEmpty	O(1)	O(1)
isFull	O(1)	O(1)
size	O(1)	O(1)
clear	O(n)	O(1)
toArray	O(n)	O(n)

Visual Trace Through Multiple Cycles

Let's trace a sequence of operations that demonstrates how the circular queue cycles through the array multiple times:

circular-queue-trace.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const queue = new CircularQueue<number>(4);
 
// Phase 1: Fill the queue
queue.enqueue(10);  // [10][__][__][__]  f=0,r=0,n=1
queue.enqueue(20);  // [10][20][__][__]  f=0,r=1,n=2
queue.enqueue(30);  // [10][20][30][__]  f=0,r=2,n=3
queue.enqueue(40);  // [10][20][30][40]  f=0,r=3,n=4 ← FULL
 
// Phase 2: Remove and add (first wraparound)
queue.dequeue();    // [__][20][30][40]  f=1,r=3,n=3  (returned 10)
queue.enqueue(50);  // [50][20][30][40]  f=1,r=0,n=4 ← rear wrapped!
 
queue.dequeue();    // [50][__][30][40]  f=2,r=0,n=3  (returned 20)
queue.enqueue(60);  // [50][60][30][40]  f=2,r=1,n=4 ← FULL again
 
// Phase 3: More cycles
queue.dequeue();    // [50][60][__][40]  f=3,r=1,n=3  (returned 30)
queue.dequeue();    // [50][60][__][__]  f=0,r=1,n=2  ← front wrapped! (returned 40)
 
// Current state: logical order is [50, 60]
// Physical: [50][60][__][__] with front=0, rear=1
 
queue.enqueue(70);  // [50][60][70][__]  f=0,r=2,n=3
queue.enqueue(80);  // [50][60][70][80]  f=0,r=3,n=4 ← FULL
 
// Drain the queue
queue.dequeue();    // [__][60][70][80]  f=1,r=3,n=3  (returned 50)
queue.dequeue();    // [__][__][70][80]  f=2,r=3,n=2  (returned 60)
queue.dequeue();    // [__][__][__][80]  f=3,r=3,n=1  (returned 70)
queue.dequeue();    // [__][__][__][__]  f=0,r=3,n=0  ← EMPTY (returned 80)
                    // front wrapped on becoming empty
 
/* Summary of wraparounds:
   - rear wrapped from 3→0 (enqueue 50)
   - front wrapped from 3→0 (dequeue 40)
   - rear completed another cycle
   - front completed another cycle
   
   The queue processed 8 elements using only 4 slots!
   In a linear queue, we would have been stuck after 4 enqueues.
*/

Unlimited Lifetime Operations

Summary and Next Steps

This page established the mechanics of circular queue implementation, showing how modular arithmetic transforms arrays into efficient ring buffers.

Key Takeaways

•Circular queues treat arrays as rings, where the last index connects back to the first. This mental model enables slot reuse.
•Modular arithmetic ((index + 1) % capacity) is the key operation that enables wraparound. It works for both front and rear pointers.
•Both enqueue and dequeue remain O(1) while achieving perfect space utilization. We get the best of both worlds.
•An explicit count variable simplifies implementation by making full/empty detection trivial and providing instant size queries.
•Circular queues can process unlimited elements over their lifetime (within capacity constraints at any moment), unlike linear queues that exhaust after N operations.

What's Next:

The next page focuses on front and rear pointer management—different conventions for tracking queue boundaries and their implications. We'll explore:

Alternative pointer semantics (rear as next slot vs last element)
The mathematics of computing queue size from pointers
Edge cases and their handling

Following that, we'll tackle the critical full vs empty detection problem that challenges many circular queue implementations.

Page Complete