Circular Queue - Learning Module

Loading content...

0/276

Front and Rear Pointer Management

The Pointers That Define the Queue

In a circular queue, two pointers—front and rear—define the logical boundaries of the queue within the physical array. These pointers are the control mechanism that enables all queue operations to execute in O(1) time.

But there's more subtlety here than meets the eye. Different implementations use different conventions for what these pointers mean, how they're initialized, and how they relate to the queue's size. Understanding these variations is crucial for:

Reading and understanding existing queue implementations
Avoiding off-by-one errors when implementing your own
Choosing the right convention for specific use cases

This page explores pointer management in depth, demystifying the various approaches you'll encounter in textbooks, libraries, and production code.

What You Will Learn

By the end of this page, you will understand: (1) The two primary pointer conventions (rear-at-element vs rear-at-next-slot), (2) How to compute queue size from pointer positions, (3) Initialization strategies and their implications, and (4) Edge cases that can cause subtle bugs.

The Two Pointer Conventions

There are two fundamentally different conventions for what the rear pointer represents in a circular queue. Understanding both is essential because you'll encounter each in practice.

Convention 1: Rear Points to the Last Element

In this convention:

front is the index of the first element in the queue
rear is the index of the last element in the queue
Both pointers point to occupied slots

Convention 2: Rear Points to the Next Available Slot

In this convention:

front is the index of the first element in the queue
rear is the index where the next element will be placed
front points to an occupied slot; rear points to an empty slot

Convention 1: Rear at Last Element

•Enqueue: Advance rear, then place element
•Dequeue: Retrieve element, then advance front
•Initial state: rear = -1 (or rear = capacity - 1)
•Empty: Detected via size counter
•Intuition: Pointers bracket the occupied region

Convention 2: Rear at Next Slot

•Enqueue: Place element, then advance rear
•Dequeue: Retrieve element, then advance front
•Initial state: front = 0, rear = 0
•Empty: front == rear (with care)
•Intuition: Rear always ready for next insert

Visual Comparison:

Queue contains elements A, B, C at indices 2, 3, 4

Convention 1 (rear at last element):
[_] [_] [A] [B] [C] [_] [_]
         ↑       ↑
       front    rear
       
Convention 2 (rear at next slot):
[_] [_] [A] [B] [C] [_] [_]
         ↑           ↑
       front        rear

Notice that in Convention 2, rear points to index 5 (the empty slot after C), while in Convention 1, rear points to index 4 (where C resides).

Which Convention to Use?

Convention 2 (rear at next slot) is often considered more elegant because: (1) The initial state is clean (front = rear = 0), (2) The empty condition is simply front == rear, and (3) The enqueue operation 'place then advance' is slightly more intuitive. However, Convention 1 is equally valid and sometimes preferred for its symmetry (both pointers point to elements).

Convention 1 in Detail: Rear Points to Last Element

Let's examine Convention 1 thoroughly, including its initialization, operations, and edge case handling.

convention-1-implementation.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
/**
 * Convention 1: rear points to the last element
 * - front: index of first element
 * - rear: index of last element
 * - Requires explicit size counter for empty/full detection
 */
class CircularQueueConvention1<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = -1;  // Special value: no elements yet
        this.count = 0;
    }
 
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Enqueue: Advance rear FIRST, then place element
     */
    enqueue(element: T): void {
        if (this.isFull()) throw new Error("Overflow");
        
        // Step 1: Advance rear (with wraparound)
        this.rear = (this.rear + 1) % this.capacity;
        
        // Step 2: Place element at new rear position
        this.data[this.rear] = element;
        
        this.count++;
    }
 
    /**
     * Dequeue: Retrieve element at front, THEN advance front
     */
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Underflow");
        
        // Step 1: Get element at front
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        
        // Step 2: Advance front (with wraparound)
        this.front = (this.front + 1) % this.capacity;
        
        this.count--;
        return element;
    }
}
 
/* Trace with capacity 4:
 
Initial: front=0, rear=-1, count=0
         [_] [_] [_] [_]
 
enqueue(A): rear = (-1+1)%4 = 0, data[0]=A, count=1
            [A] [_] [_] [_]
             ↑
           f,r
 
enqueue(B): rear = (0+1)%4 = 1, data[1]=B, count=2
            [A] [B] [_] [_]
             ↑   ↑
             f   r
 
dequeue(): element=A, front = (0+1)%4 = 1, count=1
           [_] [B] [_] [_]
                ↑
              f,r
*/

Key Characteristics of Convention 1:

Order Matters: In enqueue, we advance rear before placing the element. In dequeue, we get the element before advancing front.
Initial Rear = -1: This special value indicates "no elements yet." The first enqueue advances to 0.
Size Counter Required: Without count, we cannot distinguish full from empty (both would have front == (rear + 1) % capacity).
Both Pointers Valid When Non-Empty: After any enqueue, both front and rear point to actual elements.

The -1 Initialization Quirk:

Starting with rear = -1 works mathematically because (-1 + 1) % capacity = 0, which is correct for the first element. However, this feels semantically awkward (what does index -1 mean?).

An alternative initialization uses rear = capacity - 1, which is the index "before" 0 in circular terms:

constructor(capacity: number) {
    this.front = 0;
    this.rear = capacity - 1;  // "Before" index 0 in circular sense
    this.count = 0;
}
// Now (capacity-1 + 1) % capacity = 0 ✓

Convention 2 in Detail: Rear Points to Next Slot

Now let's examine Convention 2, which many consider the more elegant approach:

convention-2-implementation.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
/**
 * Convention 2: rear points to the next available slot
 * - front: index of first element
 * - rear: index where next element will be placed
 * - Can detect empty via front == rear (with care regarding full)
 */
class CircularQueueConvention2<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;  // Same as front: next slot is at 0
        this.count = 0;
    }
 
    isEmpty(): boolean {
        // Option 1: Use count
        return this.count === 0;
        
        // Option 2: front == rear means empty (if we don't use count)
        // return this.front === this.rear;  // But this also true when full!
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Enqueue: Place element at rear, THEN advance rear
     */
    enqueue(element: T): void {
        if (this.isFull()) throw new Error("Overflow");
        
        // Step 1: Place element at current rear
        this.data[this.rear] = element;
        
        // Step 2: Advance rear (with wraparound)
        this.rear = (this.rear + 1) % this.capacity;
        
        this.count++;
    }
 
    /**
     * Dequeue: Retrieve element at front, THEN advance front
     */
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Underflow");
        
        // Step 1: Get element at front
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        
        // Step 2: Advance front (with wraparound)
        this.front = (this.front + 1) % this.capacity;
        
        this.count--;
        return element;
    }
}
 
/* Trace with capacity 4:
 
Initial: front=0, rear=0, count=0
         [_] [_] [_] [_]
          ↑
         f,r
 
enqueue(A): data[0]=A, rear = (0+1)%4 = 1, count=1
            [A] [_] [_] [_]
             ↑   ↑
             f   r
 
enqueue(B): data[1]=B, rear = (1+1)%4 = 2, count=2
            [A] [B] [_] [_]
             ↑       ↑
             f       r
 
dequeue(): element=A, front = (0+1)%4 = 1, count=1
           [_] [B] [_] [_]
                ↑   ↑
                f   r
*/

Key Characteristics of Convention 2:

Order Matters (Reversed): In enqueue, we place the element before advancing rear. This is the opposite of Convention 1.
Clean Initialization: front = rear = 0 is intuitive: both point to where operations will happen.
Empty Detection: front == rear naturally indicates an empty queue, but this creates ambiguity with full queues.
Rear Points Ahead: The rear pointer always indicates where the next element will go, not where the last element is.

The Full vs Empty Ambiguity

In Convention 2 without a count variable, both empty and full states can have front == rear! When empty: no elements. When full: rear has wrapped around and caught up to front. We'll address this critical issue in the next section on full/empty detection.

Computing Queue Size from Pointers

While using an explicit count variable is the simplest approach, it's valuable to understand how to compute the queue size directly from the front and rear pointers. This becomes necessary if you're memory-constrained or working with legacy code that doesn't track size.

Formula for Convention 2 (rear = next slot):

When rear points to the next available slot:

size = (rear - front + capacity) % capacity

The + capacity handles the case where rear has wrapped around and is now "before" front in the array.

compute-size.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
// Convention 2: rear = next available slot
function computeSizeConvention2(front: number, rear: number, capacity: number): number {
    return (rear - front + capacity) % capacity;
}
 
/* Examples with capacity 5:
 
Case 1: No wraparound
  front = 1, rear = 4
  size = (4 - 1 + 5) % 5 = 8 % 5 = 3 ✓
  
  [_] [A] [B] [C] [_]
       ↑           ↑
       f           r
 
Case 2: Rear wrapped around
  front = 3, rear = 1
  size = (1 - 3 + 5) % 5 = 3 % 5 = 3 ✓
  
  [D] [_] [_] [A] [B] [C]
       ↑       ↑
       r       f
  Elements: A(3), B(4), C(0), D(0)... wait, that's wrong visualization
  
Correct for capacity 5, front=3, rear=1:
  [C] [_] [_] [A] [B]
       ↑       ↑
       r       f
  Elements: A(3), B(4), C(0) → size = 3 ✓
 
Case 3: Empty (front == rear)
  front = 2, rear = 2
  size = (2 - 2 + 5) % 5 = 5 % 5 = 0 ✓
  
Case 4: Full (front == rear after wraparound) ← PROBLEM!
  If front = 2, rear = 2 (after filling all slots)
  size = (2 - 2 + 5) % 5 = 0 ← WRONG! Should be 5!
*/
 
// This is why we can't use pointer arithmetic alone for full detection!

Formula for Convention 1 (rear = last element):

When rear points to the last element:

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

The + 1 accounts for the fact that both front and rear point to elements (inclusive range).

However, this fails for empty queues where rear might be at an invalid position. Convention 1 typically requires a count variable.

Why Not Just Use the Formula?

The formulas work for computing the number of elements, but they fail to distinguish empty from full when both give the same pointer configuration. That's why production implementations almost always use either: (1) An explicit count variable, or (2) A sacrificed slot (using only n-1 of n slots) to ensure front == rear means only empty, never full.

Pointer States and Transitions

Understanding how pointers transition through different states helps prevent bugs. Let's map out the state space for Convention 2:

State Table (Convention 2, Capacity 4):

Pointer States Through Queue Operations
State	Front	Rear	Count	Array Visual	Notes
Empty (initial)	0	0	0	[][][][]	front == rear, empty
1 element	0	1	1	[A][][][_]	rear ahead of front
2 elements	0	2	2	[A][B][][]	normal progression
3 elements	0	3	3	[A][B][C][_]	one slot left
Full	0	0	4	[A][B][C][D]	front == rear, FULL!
After 1 dequeue	1	0	3	[_][B][C][D]	rear wrapped
After 1 enqueue	1	1	4	[E][B][C][D]	front == rear again

Critical Observations:

front == rear occurs in two scenarios: empty (count=0) and full (count=capacity)
Rear catches up to front when the queue fills
Front catches up to rear when the queue empties
After wraparound, rear can be numerically less than front

Invariants to Maintain:

At all times, these invariants must hold:

// Convention 2 invariants
0 <= front < capacity
0 <= rear < capacity
0 <= count <= capacity

// Valid elements are at indices:
// front, (front+1)%cap, (front+2)%cap, ..., (front+count-1)%cap

// rear is always at:
// (front + count) % capacity

Violating any invariant indicates a bug in the implementation.

Debugging Circular Queues

When debugging circular queue issues, always verify the invariants. Print front, rear, count, and the array contents. Check that (front + count) % capacity == rear. If this equality fails, there's an inconsistency in your enqueue/dequeue logic.

Edge Cases and Pitfalls

Circular queue implementations are prone to subtle bugs, especially around edge cases. Here are the most common pitfalls:

Pitfall 1: Off-by-One in Capacity

pitfall-off-by-one.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// WRONG: Creates array of capacity elements but only uses capacity-1
class BuggyQueue {
    constructor(capacity: number) {
        this.data = new Array(capacity);
        this.capacity = capacity - 1;  // BUG: user expects 'capacity' elements!
    }
}
 
// CORRECT: If sacrificing a slot, document it clearly
class CorrectQueue {
    constructor(requestedCapacity: number) {
        // Allocate one extra slot for full/empty detection
        this.data = new Array(requestedCapacity + 1);
        this.actualCapacity = requestedCapacity + 1;
        this.usableCapacity = requestedCapacity;  // What user can actually use
    }
}

Pitfall 2: Forgetting Modulus on One Pointer

pitfall-missing-modulus.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
// WRONG: Only rear uses modulus, front can overflow!
dequeue(): T {
    const element = this.data[this.front];
    this.front++;  // BUG: front can exceed capacity!
    return element;
}
 
// CORRECT: Both pointers must use modulus
dequeue(): T {
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;  // ✓ Wraps correctly
    return element;
}

Pitfall 3: Empty Check After Dequeue

pitfall-empty-check.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// WRONG: Checking empty after modifying count
dequeue(): T {
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.count--;
    
    if (this.isEmpty()) {  // BUG: check is too late, already modified state!
        throw new Error("Underflow");
    }
    return element;
}
 
// CORRECT: Check BEFORE modifying state
dequeue(): T {
    if (this.isEmpty()) {  // ✓ Check first
        throw new Error("Underflow");
    }
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.count--;
    return element;
}

Pitfall 4: Incorrect Pointer Initialization for Convention 1

pitfall-initialization.ts
1
2
3
4
5
6
7
8
9
10
11
12
// WRONG: Using 0 for rear in Convention 1
constructor(capacity: number) {
    this.front = 0;
    this.rear = 0;  // BUG: first enqueue will put element at index 1!
}
 
// CORRECT: rear = -1 (or capacity - 1) for Convention 1
constructor(capacity: number) {
    this.front = 0;
    this.rear = -1;  // ✓ First enqueue advances to 0
    // OR: this.rear = capacity - 1;  // ✓ Also works
}

The Silent Corruption Bug

The most dangerous bugs don't throw errors—they silently corrupt data. A queue that overwrites elements or returns stale data can cause cascading failures in systems. Always write comprehensive tests that verify queue contents after sequences of mixed operations, including wraparound scenarios.

Pointer Arithmetic for Random Access

While queues are typically accessed only at the front and rear, array-based implementations can support O(1) random access to any element by offset. This is useful for debugging, visualization, and specialized algorithms.

Accessing by Logical Index:

Given a logical index i (0 = front, size-1 = rear element), the physical index is:

physicalIndex = (front + i) % capacity

This formula works regardless of wraparound.

random-access.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
class CircularQueueWithRandomAccess<T> {
    // ... (standard fields and methods)
 
    /**
     * Access element at logical index (0 = front, size-1 = rear)
     * Time: O(1)
     */
    at(logicalIndex: number): T {
        if (logicalIndex < 0 || logicalIndex >= this.count) {
            throw new Error(`Index ${logicalIndex} out of bounds [0, ${this.count})`);
        }
        
        const physicalIndex = (this.front + logicalIndex) % this.capacity;
        return this.data[physicalIndex] as T;
    }
 
    /**
     * Get physical index from logical index
     * Useful for debugging
     */
    getPhysicalIndex(logicalIndex: number): number {
        if (logicalIndex < 0 || logicalIndex >= this.count) {
            throw new Error("Invalid logical index");
        }
        return (this.front + logicalIndex) % this.capacity;
    }
 
    /**
     * Iterate over all elements in queue order
     * Without creating a new array
     */
    *[Symbol.iterator](): Iterator<T> {
        for (let i = 0; i < this.count; i++) {
            yield this.at(i);
        }
    }
}
 
/* Example:
Queue state: capacity=5, front=3, rear=1, count=4
 
Physical array: [D] [E] [_] [A] [B] [C]
                 ↑   ↑       ↑
                    rear   front
 
Logical order: A(0), B(1), C(2), D(3), E(4)... 
Wait, only count=4 elements: A, B, C, D
 
at(0) → (3 + 0) % 5 = 3 → A
at(1) → (3 + 1) % 5 = 4 → B  
at(2) → (3 + 2) % 5 = 0 → C (wrapped!)
at(3) → (3 + 3) % 5 = 1 → D
*/

Use Cases for Random Access:

Debugging: Inspect any position without dequeueing
Sliding Windows: Some algorithms need to access the kth element from front
Priority Adjustments: Though a deque would be better for this
Visualization: Display queue contents in order

Limitations:

Random access breaks the queue abstraction. If you frequently need to access elements by index, consider whether an array or deque is a better fit than a queue.

Choosing Between Conventions

Given the two conventions, how do you decide which to use? Here's a decision framework:

Convention Decision Matrix
Criterion	Convention 1 (rear = last)	Convention 2 (rear = next)
Initialization clarity	Awkward (rear = -1)	Clean (front = rear = 0)
Empty detection	Requires count	front == rear (but ambiguous)
Enqueue intuition	Advance, then place	Place, then advance
Both pointers at elements	Yes (when non-empty)	Only front
Code symmetry	Higher	Lower
Common in textbooks	More common	Less common
Production usage	Varies	Varies

Recommendation:

For most implementations, Convention 2 with an explicit count variable offers the best balance:

Clean initialization (front = rear = 0)
No ambiguity (count handles full/empty)
Intuitive enqueue (place, then advance)

If memory is extremely constrained and you cannot afford a count variable, use Convention 2 with N-1 usable slots to distinguish empty from full.

Whatever convention you choose, document it clearly and be consistent throughout the implementation.

Reading Others' Code

When reading an unfamiliar circular queue implementation, first identify the convention: Does rear point to the last element or the next slot? Is there a count variable? Answering these questions will help you understand the code's logic.

Summary and Key Takeaways

This page provided an in-depth exploration of pointer management in circular queues—a topic that often trips up even experienced developers.

Key Takeaways

•Two conventions exist: Rear points to the last element (Convention 1) or to the next available slot (Convention 2). Both are valid; choose one and be consistent.
•Enqueue order differs: Convention 1 advances then places; Convention 2 places then advances. Getting this wrong causes off-by-one bugs.
•Size can be computed from pointers using (rear - front + capacity) % capacity, but this formula cannot distinguish full from empty.
•Invariants are essential: Always verify that (front + count) % capacity == rear. Violations indicate bugs.
•Common pitfalls include missing modulus on one pointer, wrong initialization, and checking conditions after modifying state.
•Random access is possible in O(1) using the formula physicalIndex = (front + logicalIndex) % capacity.

What's Next:

The next page tackles the critical challenge of Full vs Empty Detection. We'll explore:

Why front == rear is ambiguous
The sacrificed-slot technique (use n-1 of n slots)
The count variable approach (our recommended method)
Other strategies like wrapper flags

This is one of the most important topics for getting circular queues right in practice.

Page Complete

You now have a deep understanding of pointer semantics in circular queues. The conventions we explored may seem like minor details, but they're the foundation for correct implementations. Next, we'll solve the full-vs-empty detection problem that makes circular queues tricky to implement without bugs.

Front and Rear Pointer Management

The Pointers That Define the Queue

Reading and understanding existing queue implementations
Avoiding off-by-one errors when implementing your own
Choosing the right convention for specific use cases

This page explores pointer management in depth, demystifying the various approaches you'll encounter in textbooks, libraries, and production code.

What You Will Learn

The Two Pointer Conventions

There are two fundamentally different conventions for what the rear pointer represents in a circular queue. Understanding both is essential because you'll encounter each in practice.

Convention 1: Rear Points to the Last Element

In this convention:

front is the index of the first element in the queue
rear is the index of the last element in the queue
Both pointers point to occupied slots

Convention 2: Rear Points to the Next Available Slot

In this convention:

front is the index of the first element in the queue
rear is the index where the next element will be placed
front points to an occupied slot; rear points to an empty slot

Convention 1: Rear at Last Element

•Enqueue: Advance rear, then place element
•Dequeue: Retrieve element, then advance front
•Initial state: rear = -1 (or rear = capacity - 1)
•Empty: Detected via size counter
•Intuition: Pointers bracket the occupied region

Convention 2: Rear at Next Slot

•Enqueue: Place element, then advance rear
•Dequeue: Retrieve element, then advance front
•Initial state: front = 0, rear = 0
•Empty: front == rear (with care)
•Intuition: Rear always ready for next insert

Visual Comparison:

Queue contains elements A, B, C at indices 2, 3, 4

Convention 1 (rear at last element):
[_] [_] [A] [B] [C] [_] [_]
         ↑       ↑
       front    rear
       
Convention 2 (rear at next slot):
[_] [_] [A] [B] [C] [_] [_]
         ↑           ↑
       front        rear

Notice that in Convention 2, rear points to index 5 (the empty slot after C), while in Convention 1, rear points to index 4 (where C resides).

Which Convention to Use?

Convention 1 in Detail: Rear Points to Last Element

Let's examine Convention 1 thoroughly, including its initialization, operations, and edge case handling.

convention-1-implementation.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
/**
 * Convention 1: rear points to the last element
 * - front: index of first element
 * - rear: index of last element
 * - Requires explicit size counter for empty/full detection
 */
class CircularQueueConvention1<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = -1;  // Special value: no elements yet
        this.count = 0;
    }
 
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Enqueue: Advance rear FIRST, then place element
     */
    enqueue(element: T): void {
        if (this.isFull()) throw new Error("Overflow");
        
        // Step 1: Advance rear (with wraparound)
        this.rear = (this.rear + 1) % this.capacity;
        
        // Step 2: Place element at new rear position
        this.data[this.rear] = element;
        
        this.count++;
    }
 
    /**
     * Dequeue: Retrieve element at front, THEN advance front
     */
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Underflow");
        
        // Step 1: Get element at front
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        
        // Step 2: Advance front (with wraparound)
        this.front = (this.front + 1) % this.capacity;
        
        this.count--;
        return element;
    }
}
 
/* Trace with capacity 4:
 
Initial: front=0, rear=-1, count=0
         [_] [_] [_] [_]
 
enqueue(A): rear = (-1+1)%4 = 0, data[0]=A, count=1
            [A] [_] [_] [_]
             ↑
           f,r
 
enqueue(B): rear = (0+1)%4 = 1, data[1]=B, count=2
            [A] [B] [_] [_]
             ↑   ↑
             f   r
 
dequeue(): element=A, front = (0+1)%4 = 1, count=1
           [_] [B] [_] [_]
                ↑
              f,r
*/

Key Characteristics of Convention 1:

Order Matters: In enqueue, we advance rear before placing the element. In dequeue, we get the element before advancing front.
Initial Rear = -1: This special value indicates "no elements yet." The first enqueue advances to 0.
Size Counter Required: Without count, we cannot distinguish full from empty (both would have front == (rear + 1) % capacity).
Both Pointers Valid When Non-Empty: After any enqueue, both front and rear point to actual elements.

The -1 Initialization Quirk:

Starting with rear = -1 works mathematically because (-1 + 1) % capacity = 0, which is correct for the first element. However, this feels semantically awkward (what does index -1 mean?).

An alternative initialization uses rear = capacity - 1, which is the index "before" 0 in circular terms:

constructor(capacity: number) {
    this.front = 0;
    this.rear = capacity - 1;  // "Before" index 0 in circular sense
    this.count = 0;
}
// Now (capacity-1 + 1) % capacity = 0 ✓

Convention 2 in Detail: Rear Points to Next Slot

Now let's examine Convention 2, which many consider the more elegant approach:

convention-2-implementation.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
/**
 * Convention 2: rear points to the next available slot
 * - front: index of first element
 * - rear: index where next element will be placed
 * - Can detect empty via front == rear (with care regarding full)
 */
class CircularQueueConvention2<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;  // Same as front: next slot is at 0
        this.count = 0;
    }
 
    isEmpty(): boolean {
        // Option 1: Use count
        return this.count === 0;
        
        // Option 2: front == rear means empty (if we don't use count)
        // return this.front === this.rear;  // But this also true when full!
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Enqueue: Place element at rear, THEN advance rear
     */
    enqueue(element: T): void {
        if (this.isFull()) throw new Error("Overflow");
        
        // Step 1: Place element at current rear
        this.data[this.rear] = element;
        
        // Step 2: Advance rear (with wraparound)
        this.rear = (this.rear + 1) % this.capacity;
        
        this.count++;
    }
 
    /**
     * Dequeue: Retrieve element at front, THEN advance front
     */
    dequeue(): T {
        if (this.isEmpty()) throw new Error("Underflow");
        
        // Step 1: Get element at front
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;
        
        // Step 2: Advance front (with wraparound)
        this.front = (this.front + 1) % this.capacity;
        
        this.count--;
        return element;
    }
}
 
/* Trace with capacity 4:
 
Initial: front=0, rear=0, count=0
         [_] [_] [_] [_]
          ↑
         f,r
 
enqueue(A): data[0]=A, rear = (0+1)%4 = 1, count=1
            [A] [_] [_] [_]
             ↑   ↑
             f   r
 
enqueue(B): data[1]=B, rear = (1+1)%4 = 2, count=2
            [A] [B] [_] [_]
             ↑       ↑
             f       r
 
dequeue(): element=A, front = (0+1)%4 = 1, count=1
           [_] [B] [_] [_]
                ↑   ↑
                f   r
*/

Key Characteristics of Convention 2:

Order Matters (Reversed): In enqueue, we place the element before advancing rear. This is the opposite of Convention 1.
Clean Initialization: front = rear = 0 is intuitive: both point to where operations will happen.
Empty Detection: front == rear naturally indicates an empty queue, but this creates ambiguity with full queues.
Rear Points Ahead: The rear pointer always indicates where the next element will go, not where the last element is.

The Full vs Empty Ambiguity

Computing Queue Size from Pointers

Formula for Convention 2 (rear = next slot):

When rear points to the next available slot:

size = (rear - front + capacity) % capacity

The + capacity handles the case where rear has wrapped around and is now "before" front in the array.

compute-size.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
// Convention 2: rear = next available slot
function computeSizeConvention2(front: number, rear: number, capacity: number): number {
    return (rear - front + capacity) % capacity;
}
 
/* Examples with capacity 5:
 
Case 1: No wraparound
  front = 1, rear = 4
  size = (4 - 1 + 5) % 5 = 8 % 5 = 3 ✓
  
  [_] [A] [B] [C] [_]
       ↑           ↑
       f           r
 
Case 2: Rear wrapped around
  front = 3, rear = 1
  size = (1 - 3 + 5) % 5 = 3 % 5 = 3 ✓
  
  [D] [_] [_] [A] [B] [C]
       ↑       ↑
       r       f
  Elements: A(3), B(4), C(0), D(0)... wait, that's wrong visualization
  
Correct for capacity 5, front=3, rear=1:
  [C] [_] [_] [A] [B]
       ↑       ↑
       r       f
  Elements: A(3), B(4), C(0) → size = 3 ✓
 
Case 3: Empty (front == rear)
  front = 2, rear = 2
  size = (2 - 2 + 5) % 5 = 5 % 5 = 0 ✓
  
Case 4: Full (front == rear after wraparound) ← PROBLEM!
  If front = 2, rear = 2 (after filling all slots)
  size = (2 - 2 + 5) % 5 = 0 ← WRONG! Should be 5!
*/
 
// This is why we can't use pointer arithmetic alone for full detection!

Formula for Convention 1 (rear = last element):

When rear points to the last element:

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

The + 1 accounts for the fact that both front and rear point to elements (inclusive range).

However, this fails for empty queues where rear might be at an invalid position. Convention 1 typically requires a count variable.

Why Not Just Use the Formula?

Pointer States and Transitions

Understanding how pointers transition through different states helps prevent bugs. Let's map out the state space for Convention 2:

State Table (Convention 2, Capacity 4):

Pointer States Through Queue Operations
State	Front	Rear	Count	Array Visual	Notes
Empty (initial)	0	0	0	[][][][]	front == rear, empty
1 element	0	1	1	[A][][][_]	rear ahead of front
2 elements	0	2	2	[A][B][][]	normal progression
3 elements	0	3	3	[A][B][C][_]	one slot left
Full	0	0	4	[A][B][C][D]	front == rear, FULL!
After 1 dequeue	1	0	3	[_][B][C][D]	rear wrapped
After 1 enqueue	1	1	4	[E][B][C][D]	front == rear again

Critical Observations:

front == rear occurs in two scenarios: empty (count=0) and full (count=capacity)
Rear catches up to front when the queue fills
Front catches up to rear when the queue empties
After wraparound, rear can be numerically less than front

Invariants to Maintain:

At all times, these invariants must hold:

// Convention 2 invariants
0 <= front < capacity
0 <= rear < capacity
0 <= count <= capacity

// Valid elements are at indices:
// front, (front+1)%cap, (front+2)%cap, ..., (front+count-1)%cap

// rear is always at:
// (front + count) % capacity

Violating any invariant indicates a bug in the implementation.

Debugging Circular Queues

Edge Cases and Pitfalls

Circular queue implementations are prone to subtle bugs, especially around edge cases. Here are the most common pitfalls:

Pitfall 1: Off-by-One in Capacity

pitfall-off-by-one.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// WRONG: Creates array of capacity elements but only uses capacity-1
class BuggyQueue {
    constructor(capacity: number) {
        this.data = new Array(capacity);
        this.capacity = capacity - 1;  // BUG: user expects 'capacity' elements!
    }
}
 
// CORRECT: If sacrificing a slot, document it clearly
class CorrectQueue {
    constructor(requestedCapacity: number) {
        // Allocate one extra slot for full/empty detection
        this.data = new Array(requestedCapacity + 1);
        this.actualCapacity = requestedCapacity + 1;
        this.usableCapacity = requestedCapacity;  // What user can actually use
    }
}

Pitfall 2: Forgetting Modulus on One Pointer

pitfall-missing-modulus.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
// WRONG: Only rear uses modulus, front can overflow!
dequeue(): T {
    const element = this.data[this.front];
    this.front++;  // BUG: front can exceed capacity!
    return element;
}
 
// CORRECT: Both pointers must use modulus
dequeue(): T {
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;  // ✓ Wraps correctly
    return element;
}

Pitfall 3: Empty Check After Dequeue

pitfall-empty-check.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// WRONG: Checking empty after modifying count
dequeue(): T {
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.count--;
    
    if (this.isEmpty()) {  // BUG: check is too late, already modified state!
        throw new Error("Underflow");
    }
    return element;
}
 
// CORRECT: Check BEFORE modifying state
dequeue(): T {
    if (this.isEmpty()) {  // ✓ Check first
        throw new Error("Underflow");
    }
    const element = this.data[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.count--;
    return element;
}

Pitfall 4: Incorrect Pointer Initialization for Convention 1

pitfall-initialization.ts
1
2
3
4
5
6
7
8
9
10
11
12
// WRONG: Using 0 for rear in Convention 1
constructor(capacity: number) {
    this.front = 0;
    this.rear = 0;  // BUG: first enqueue will put element at index 1!
}
 
// CORRECT: rear = -1 (or capacity - 1) for Convention 1
constructor(capacity: number) {
    this.front = 0;
    this.rear = -1;  // ✓ First enqueue advances to 0
    // OR: this.rear = capacity - 1;  // ✓ Also works
}

The Silent Corruption Bug

Pointer Arithmetic for Random Access

Accessing by Logical Index:

Given a logical index i (0 = front, size-1 = rear element), the physical index is:

physicalIndex = (front + i) % capacity

This formula works regardless of wraparound.

random-access.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
class CircularQueueWithRandomAccess<T> {
    // ... (standard fields and methods)
 
    /**
     * Access element at logical index (0 = front, size-1 = rear)
     * Time: O(1)
     */
    at(logicalIndex: number): T {
        if (logicalIndex < 0 || logicalIndex >= this.count) {
            throw new Error(`Index ${logicalIndex} out of bounds [0, ${this.count})`);
        }
        
        const physicalIndex = (this.front + logicalIndex) % this.capacity;
        return this.data[physicalIndex] as T;
    }
 
    /**
     * Get physical index from logical index
     * Useful for debugging
     */
    getPhysicalIndex(logicalIndex: number): number {
        if (logicalIndex < 0 || logicalIndex >= this.count) {
            throw new Error("Invalid logical index");
        }
        return (this.front + logicalIndex) % this.capacity;
    }
 
    /**
     * Iterate over all elements in queue order
     * Without creating a new array
     */
    *[Symbol.iterator](): Iterator<T> {
        for (let i = 0; i < this.count; i++) {
            yield this.at(i);
        }
    }
}
 
/* Example:
Queue state: capacity=5, front=3, rear=1, count=4
 
Physical array: [D] [E] [_] [A] [B] [C]
                 ↑   ↑       ↑
                    rear   front
 
Logical order: A(0), B(1), C(2), D(3), E(4)... 
Wait, only count=4 elements: A, B, C, D
 
at(0) → (3 + 0) % 5 = 3 → A
at(1) → (3 + 1) % 5 = 4 → B  
at(2) → (3 + 2) % 5 = 0 → C (wrapped!)
at(3) → (3 + 3) % 5 = 1 → D
*/

Use Cases for Random Access:

Debugging: Inspect any position without dequeueing
Sliding Windows: Some algorithms need to access the kth element from front
Priority Adjustments: Though a deque would be better for this
Visualization: Display queue contents in order

Limitations:

Random access breaks the queue abstraction. If you frequently need to access elements by index, consider whether an array or deque is a better fit than a queue.

Choosing Between Conventions

Given the two conventions, how do you decide which to use? Here's a decision framework:

Convention Decision Matrix
Criterion	Convention 1 (rear = last)	Convention 2 (rear = next)
Initialization clarity	Awkward (rear = -1)	Clean (front = rear = 0)
Empty detection	Requires count	front == rear (but ambiguous)
Enqueue intuition	Advance, then place	Place, then advance
Both pointers at elements	Yes (when non-empty)	Only front
Code symmetry	Higher	Lower
Common in textbooks	More common	Less common
Production usage	Varies	Varies

Recommendation:

For most implementations, Convention 2 with an explicit count variable offers the best balance:

Clean initialization (front = rear = 0)
No ambiguity (count handles full/empty)
Intuitive enqueue (place, then advance)

If memory is extremely constrained and you cannot afford a count variable, use Convention 2 with N-1 usable slots to distinguish empty from full.

Whatever convention you choose, document it clearly and be consistent throughout the implementation.

Reading Others' Code

Summary and Key Takeaways

This page provided an in-depth exploration of pointer management in circular queues—a topic that often trips up even experienced developers.

Key Takeaways

•Two conventions exist: Rear points to the last element (Convention 1) or to the next available slot (Convention 2). Both are valid; choose one and be consistent.
•Enqueue order differs: Convention 1 advances then places; Convention 2 places then advances. Getting this wrong causes off-by-one bugs.
•Size can be computed from pointers using (rear - front + capacity) % capacity, but this formula cannot distinguish full from empty.
•Invariants are essential: Always verify that (front + count) % capacity == rear. Violations indicate bugs.
•Common pitfalls include missing modulus on one pointer, wrong initialization, and checking conditions after modifying state.
•Random access is possible in O(1) using the formula physicalIndex = (front + logicalIndex) % capacity.

What's Next:

The next page tackles the critical challenge of Full vs Empty Detection. We'll explore:

Why front == rear is ambiguous
The sacrificed-slot technique (use n-1 of n slots)
The count variable approach (our recommended method)
Other strategies like wrapper flags

This is one of the most important topics for getting circular queues right in practice.

Page Complete