Data Structures & AlgorithmsArray-Based Queue & Circular Queue Implementation

Array-Based Queue & Circular Queue Implementation

LevelIntermediate

Duration75 mins

TopicArray-Based Queue & Circular Queue Implementation

4 / 4

Full vs Empty Detection

The Classic Circular Queue Puzzle

Here's a puzzle that has confused countless programmers implementing circular queues for the first time:

Consider a circular queue with capacity 4. In what state are the pointers when the queue is empty? And when it's full?

If you've been following along, you might answer:

Empty: front = rear (both at the same position, no elements between them)
Full: front = rear (rear has wrapped around and caught up to front)

Wait—both states have the same pointer configuration? How can we tell them apart?

This is the full vs empty detection problem, and it's the central challenge of circular queue implementation. This page explores multiple solutions, each with distinct trade-offs.

What You Will Learn

By the end of this page, you will understand: (1) Why the full/empty ambiguity exists, (2) Three distinct solutions (count variable, sacrificed slot, wrap flag), (3) Trade-offs between memory, performance, and complexity, and (4) How to implement each approach correctly.

Understanding the Ambiguity

Let's trace through operations to see exactly when and why the ambiguity arises.

Setup: Circular queue with capacity 4, using Convention 2 (rear points to next slot).

Initial State (Empty):

front = 0, rear = 0
[_] [_] [_] [_]
 ↑
f,r

Condition: front == rear → EMPTY

After 4 Enqueues (Full):

enqueue(A): rear = 1 → [A] [_] [_] [_]
enqueue(B): rear = 2 → [A] [B] [_] [_]
enqueue(C): rear = 3 → [A] [B] [C] [_]
enqueue(D): rear = 0 → [A] [B] [C] [D]  (rear wrapped!)

front = 0, rear = 0
[A] [B] [C] [D]
 ↑
f,r

Condition: front == rear → FULL

The Paradox:

Both empty and full have front == rear! The pointers alone cannot distinguish these states.

The Fundamental Problem

With only two pointer variables, we can represent capacity + 1 distinct states (0 elements, 1 element, ..., capacity elements). But two indices can only uniquely identify capacity × capacity configurations, and capacity of those configurations are used for regular states, leaving no unique configuration for 'full' vs 'empty'. We need additional information.

Mathematical Perspective:

For a queue of capacity N:

Number of possible states: N + 1 (sizes 0 through N)
Unique pointer configurations: N (front can be at any of N positions; rear is determined by size)

We have N + 1 states but only N configurations. By the pigeonhole principle, at least two states must share a configuration. In circular queues, these are the empty (size = 0) and full (size = N) states.

Three Solutions:

Count Variable: Track size explicitly
Sacrificed Slot: Use only N-1 of N slots
Wrap Flag: Track whether rear has wrapped

Solution 1: The Count Variable Approach

The most straightforward solution is to maintain an explicit counter that tracks the number of elements in the queue. This completely eliminates the ambiguity.

How It Works:

Add a count variable initialized to 0
Increment count on each enqueue
Decrement count on each dequeue
Empty when count == 0; Full when count == capacity

count-variable-approach.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
/**
 * Circular Queue with Count Variable
 * The cleanest and most intuitive solution
 */
class CircularQueueWithCount<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;  // ← The key addition
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    // Empty and Full are now unambiguous
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    size(): number {
        return this.count;  // O(1) size query as a bonus!
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        this.count++;  // ← Track addition
    }
 
    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--;  // ← Track removal
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

Advantages

•Clean logic: Empty and full are trivially different
•O(1) size(): Know element count instantly
•Full capacity: All N slots are usable
•Simple implementation: Hard to get wrong
•Works with any convention: No pointer quirks

Disadvantages

•Extra memory: One additional integer
•Extra operations: Increment/decrement on each operation
•Potential inconsistency: Count and pointers can desync if buggy

Recommended Approach

The count variable approach is our recommended solution for most use cases. The 'extra memory' of one integer is trivial (4-8 bytes), and the 'extra operations' are single cycle instructions. The clarity and robustness it provides far outweigh these minimal costs.

Solution 2: The Sacrificed Slot Approach

The sacrificed slot approach solves the ambiguity without additional variables by intentionally leaving one slot always empty. This ensures that full and empty states have different pointer configurations.

How It Works:

Allocate an array of size N
Only use N-1 slots for actual elements
Full: (rear + 1) % capacity == front (next enqueue would reach front)
Empty: rear == front

Since we never fill the last slot, rear == front can only mean empty.

sacrificed-slot-approach.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
/**
 * Circular Queue with Sacrificed Slot
 * Uses N-1 of N slots to distinguish empty from full
 */
class CircularQueueSacrificedSlot<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;  // Total array size
 
    constructor(usableCapacity: number) {
        // Allocate one extra slot that will always remain empty
        this.capacity = usableCapacity + 1;
        this.data = new Array(this.capacity);
        this.front = 0;
        this.rear = 0;
    }
 
    // Empty: front and rear are at the same position
    isEmpty(): boolean {
        return this.front === this.rear;
    }
 
    // Full: rear is exactly one position behind front (circularly)
    // Adding another element would make rear == front (ambiguous!)
    isFull(): boolean {
        return (this.rear + 1) % this.capacity === this.front;
    }
 
    // Size must be computed from pointers
    size(): number {
        return (this.rear - this.front + this.capacity) % this.capacity;
    }
 
    // Maximum usable elements (not the array size)
    maxSize(): number {
        return this.capacity - 1;
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
    }
 
    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;
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

Visual Explanation:

Capacity = 5 (usable = 4)

Empty:     front = rear = 0
           [_] [_] [_] [_] [_]
            ↑
           f,r

1 element: front = 0, rear = 1
           [A] [_] [_] [_] [_]
            ↑   ↑
            f   r

4 elements (FULL): front = 0, rear = 4
           [A] [B] [C] [D] [_]
            ↑               ↑
            f               r
           
           isFull(): (4 + 1) % 5 = 0 == front ✓
           
           The slot at index 4 is kept empty!
           If we tried to enqueue, rear would
           become 0, matching front (ambiguous).

By never allowing rear to catch up to front, we preserve the distinction: front == rear always means empty, never full.

Advantages

•No count variable: Saves one integer of memory
•Pure pointer logic: Detection uses only front and rear
•Lower operation overhead: No count increment/decrement
•Common in hardware: Often used in FIFO buffers

Disadvantages

•Wasted slot: Lose 1/N of capacity
•O(n) size for large N: Size computation required
•Confusing capacity: Array size ≠ usable capacity
•Off-by-one traps: Easy to miscalculate boundaries

When to Use Sacrificed Slot

The sacrificed slot approach is ideal when: (1) Memory is extremely constrained (no room for count), (2) You rarely need size queries, (3) You're interfacing with hardware that expects this convention, or (4) N is large so losing one slot is negligible.

Solution 3: The Wrap Flag Approach

The wrap flag approach uses a boolean to track whether the rear pointer has 'wrapped around' and caught up to the front. This provides full capacity usage with minimal additional memory.

How It Works:

Add a wrapped boolean flag, initially false
Set wrapped = true when rear wraps and reaches front
Set wrapped = false when front advances past where rear was
Empty: front == rear && !wrapped
Full: front == rear && wrapped

wrap-flag-approach.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
/**
 * Circular Queue with Wrap Flag
 * Uses a boolean to track full/empty distinction
 */
class CircularQueueWithWrapFlag<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private wrapped: boolean;  // True if rear has caught up to front
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.wrapped = false;
    }
 
    isEmpty(): boolean {
        return this.front === this.rear && !this.wrapped;
    }
 
    isFull(): boolean {
        return this.front === this.rear && this.wrapped;
    }
 
    size(): number {
        if (this.wrapped) {
            return this.capacity;  // Full
        }
        return (this.rear - this.front + this.capacity) % this.capacity;
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        
        // If rear caught up to front, we're now full
        if (this.rear === this.front) {
            this.wrapped = true;
        }
    }
 
    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;
        
        // After removing, we're definitely not full anymore
        this.wrapped = false;
        
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

State Transitions:

Initial (Empty):
  front=0, rear=0, wrapped=false
  isEmpty: front==rear && !wrapped ✓
  
After filling all 4 slots:
  front=0, rear=0, wrapped=true
  isFull: front==rear && wrapped ✓
  
After one dequeue:
  front=1, rear=0, wrapped=false
  (wrapped cleared on dequeue)
  
After one more enqueue:
  front=1, rear=1, wrapped=true
  (rear caught front again)

The wrapped flag acts as a 'tie-breaker' when pointers are equal.

Advantages

•Full capacity: All N slots are usable
•Minimal memory: Just one boolean (1 byte)
•Clear semantics: Wrapped means 'rear caught front'

Disadvantages

•Complex logic: Must manage flag transitions carefully
•No O(1) size: Must compute from pointers + flag
•Easy to mishandle: Wrong flag update = corruption
•Less common: Many developers unfamiliar with it

Flag Management Is Tricky

The wrap flag must be managed precisely. Setting it too early or clearing it at the wrong time causes incorrect full/empty detection. This approach is less forgiving of bugs than the count variable method.

Comparison of All Three Approaches

Let's systematically compare the three solutions across key dimensions:

Full/Empty Detection Strategies Compared
Criterion	Count Variable	Sacrificed Slot	Wrap Flag
Extra Memory	1 integer (4-8 bytes)	None	1 boolean (1 byte)
Usable Capacity	N (full)	N-1 (lose one)	N (full)
isEmpty()	O(1), trivial	O(1), pointer comparison	O(1), pointer + flag
isFull()	O(1), trivial	O(1), modular comparison	O(1), pointer + flag
size()	O(1), return count	O(1), pointer arithmetic	O(1), but complex
Implementation Complexity	Low	Medium	High
Bug Risk	Low	Medium (off-by-one)	High (flag sync)
Common Use Case	General purpose	Hardware, embedded	Rare, specialized

Decision Framework:

For most applications: Use the count variable approach. The minimal memory cost is negligible, and the implementation clarity prevents bugs.
For embedded/hardware with byte-level constraints: Use the sacrificed slot approach. The lost capacity is often acceptable when N is large.
For specialized low-level systems: Consider the wrap flag approach only if you need full capacity AND cannot afford an integer counter.
When in doubt: Choose count variable. It's the industry standard for software implementations.

Real-World Observation

Most production queue implementations (Java's ArrayDeque, C++ STL queue, Python's deque, etc.) use either the count variable or sacrificed slot approach. The wrap flag is mainly seen in hardware FIFO implementations and academic exercises.

Edge Case Analysis

Regardless of which approach you choose, certain edge cases require careful handling. Let's examine each:

Edge Case 1: Queue of Capacity 1

edge-case-capacity-1.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Capacity 1 is a degenerate case for sacrificed slot!
const queue = new CircularQueueSacrificedSlot(1);
 
// Actually allocates: capacity = 1 + 1 = 2
// Usable: 1 element (array has 2 slots, one always empty)
 
// For count variable approach: works fine, can hold 1 element
 
// For wrap flag: works, but the flag flips on every enqueue/dequeue
 
// Test thoroughly!
queue.enqueue("only");
console.log(queue.isFull());  // Should be true
console.log(queue.dequeue()); // "only"
console.log(queue.isEmpty()); // Should be true

Edge Case 2: Repeated Fill-Empty Cycles

edge-case-cycles.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Test that multiple fill/empty cycles work correctly
const queue = new CircularQueue(3);
 
for (let cycle = 0; cycle < 100; cycle++) {
    // Fill completely
    for (let i = 0; i < 3; i++) {
        queue.enqueue(`cycle${cycle}-item${i}`);
    }
    if (!queue.isFull()) {
        throw new Error(`Should be full at cycle ${cycle}`);
    }
    
    // Empty completely
    for (let i = 0; i < 3; i++) {
        queue.dequeue();
    }
    if (!queue.isEmpty()) {
        throw new Error(`Should be empty at cycle ${cycle}`);
    }
}
console.log("100 cycles completed successfully");

Edge Case 3: Alternating Operations

edge-case-alternating.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Alternating enqueue/dequeue stresses pointer management
const queue = new CircularQueue(4);
 
// Add 2, remove 1, repeatedly
for (let i = 0; i < 20; i++) {
    queue.enqueue(`item-${i * 2}`);
    queue.enqueue(`item-${i * 2 + 1}`);
    
    const removed = queue.dequeue();
    console.log(`Removed: ${removed}, Size: ${queue.size()}`);
    
    // Queue should never overflow (we add 2, remove 1, net +1)
    // But it will eventually fill up!
    if (queue.isFull()) {
        console.log("Queue filled, draining...");
        while (!queue.isEmpty()) {
            queue.dequeue();
        }
    }
}

Edge Case 4: Operations on Empty/Full Queue

edge-case-boundary-operations.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
// Verify error handling at boundaries
const queue = new CircularQueue(2);
 
// Operations on empty queue
try {
    queue.dequeue();
    throw new Error("Should have thrown Underflow");
} catch (e) {
    console.log("✓ Dequeue on empty throws correctly");
}
 
try {
    queue.peek();
    throw new Error("Should have thrown Empty error");
} catch (e) {
    console.log("✓ Peek on empty throws correctly");
}
 
// Fill the queue
queue.enqueue("A");
queue.enqueue("B");
 
// Operations on full queue
try {
    queue.enqueue("C");
    throw new Error("Should have thrown Overflow");
} catch (e) {
    console.log("✓ Enqueue on full throws correctly");
}
 
// Verify queue still works after failed operations
console.log(queue.peek());   // Should be "A"
console.log(queue.size());   // Should be 2

Test Your Implementation

Always test these edge cases when implementing a circular queue. Many subtle bugs only manifest under specific sequences of operations. Automated tests with random operation sequences can help catch rare bugs.

Production-Ready Implementation

Here's a comprehensive, production-ready circular queue implementation using the recommended count variable approach, with all edge cases handled and thorough documentation:

production-circular-queue.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
 * A generic circular queue (ring buffer) implementation.
 * Uses a count variable for unambiguous full/empty detection.
 * All operations are O(1) time complexity.
 * 
 * @template T The type of elements stored in the queue
 */
class CircularQueue<T> {
    private readonly data: (T | undefined)[];
    private front: number;
    private rear: number;
    private readonly capacity: number;
    private count: number;
 
    /**
     * Creates a new circular queue with the specified capacity.
     * 
     * @param capacity Maximum number of elements the queue can hold
     * @throws Error if capacity is not a positive integer
     */
    constructor(capacity: number) {
        if (!Number.isInteger(capacity) || capacity <= 0) {
            throw new Error("Capacity must be a positive integer");
        }
        
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    /**
     * Returns true if the queue contains no elements.
     * Time: O(1)
     */
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    /**
     * Returns true if the queue is at maximum capacity.
     * Time: O(1)
     */
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Returns the number of elements currently in the queue.
     * Time: O(1)
     */
    size(): number {
        return this.count;
    }
 
    /**
     * Returns the maximum capacity of the queue.
     * Time: O(1)
     */
    getCapacity(): number {
        return this.capacity;
    }
 
    /**
     * Adds an element to the rear of the queue.
     * Time: O(1)
     * 
     * @param element The element to add
     * @throws Error if the queue is full
     */
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow: Cannot enqueue to a full queue");
        }
        
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        this.count++;
    }
 
    /**
     * Removes and returns the element at the front of the queue.
     * Time: O(1)
     * 
     * @returns The element that was at the front
     * @throws Error if the queue is empty
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow: Cannot dequeue from an empty queue");
        }
        
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;  // Help garbage collection
        this.front = (this.front + 1) % this.capacity;
        this.count--;
        
        return element;
    }
 
    /**
     * Returns the element at the front without removing it.
     * Time: O(1)
     * 
     * @returns The element at the front
     * @throws Error if the queue is empty
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Empty: No element to peek");
        }
        return this.data[this.front] as T;
    }
 
    /**
     * Returns the element at the rear without removing it.
     * Time: O(1)
     * 
     * @returns The element at the rear
     * @throws Error if the queue is empty
     */
    peekRear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Empty: No element to peek");
        }
        // Rear points to next empty slot, so go back one position
        const rearIndex = (this.rear - 1 + this.capacity) % this.capacity;
        return this.data[rearIndex] as T;
    }
 
    /**
     * Removes all elements from the queue.
     * Time: O(n)
     */
    clear(): void {
        // Clear references for garbage collection
        for (let i = 0; i < this.capacity; i++) {
            this.data[i] = undefined;
        }
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    /**
     * Returns the queue contents as an array in front-to-rear order.
     * Time: O(n)
     * 
     * @returns A new array containing all queue elements
     */
    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;
    }
 
    /**
     * Creates an iterator over queue elements (front to rear).
     * Allows use in for...of loops.
     */
    *[Symbol.iterator](): Iterator<T> {
        let current = this.front;
        for (let i = 0; i < this.count; i++) {
            yield this.data[current] as T;
            current = (current + 1) % this.capacity;
        }
    }
 
    /**
     * Returns a string representation of the queue for debugging.
     */
    toString(): string {
        return `CircularQueue(size=${this.count}, capacity=${this.capacity}): [${this.toArray().join(', ')}]`;
    }
}
 
// Export for use as a module
export { CircularQueue };

Production-Ready Features

This implementation includes: input validation in constructor, proper error messages, garbage collection hints (clearing slots), iterator support for for...of loops, toString for debugging, and comprehensive JSDoc documentation.

Summary and Key Takeaways

This page addressed the critical full vs empty detection problem that challenges circular queue implementations.

Key Takeaways

•The ambiguity exists because pointer configurations cannot uniquely identify N+1 states (sizes 0 through N) using only two pointer values.
•Count variable is the simplest and most robust solution—use it unless you have specific constraints that prevent it.
•Sacrificed slot uses N-1 of N slots to ensure front==rear means only empty, used in embedded/hardware systems.
•Wrap flag uses a boolean to track full state, but is complex and error-prone.
•Edge cases matter: Test capacity-1 queues, repeated cycles, alternating operations, and boundary conditions.
•Production implementations should include input validation, proper errors, GC hints, and iterator support.

Module Complete:

You have now completed Module 4: Array-Based Queue & Circular Queue Implementation. You understand:

Why linear array queues fail (wasted space problem)
How circular queues use modular arithmetic for wraparound
Different pointer conventions and their trade-offs
Multiple strategies for full/empty detection

This knowledge equips you to implement efficient, correct queue data structures and understand existing implementations in libraries and codebases.

Module Complete

Congratulations! You've mastered the circular queue—one of the most elegant examples of how a simple insight (treating arrays as rings) transforms an impractical data structure into an efficient one. This pattern of using modular arithmetic for cyclic behaviors appears throughout computer science: in hash tables, caches, scheduling algorithms, and network buffers.

4 / 4

Loading learning content...

Data Structures & AlgorithmsArray-Based Queue & Circular Queue Implementation

Array-Based Queue & Circular Queue Implementation

LevelIntermediate

Duration75 mins

TopicArray-Based Queue & Circular Queue Implementation

4 / 4

Full vs Empty Detection

The Classic Circular Queue Puzzle

Here's a puzzle that has confused countless programmers implementing circular queues for the first time:

Consider a circular queue with capacity 4. In what state are the pointers when the queue is empty? And when it's full?

If you've been following along, you might answer:

Empty: front = rear (both at the same position, no elements between them)
Full: front = rear (rear has wrapped around and caught up to front)

Wait—both states have the same pointer configuration? How can we tell them apart?

This is the full vs empty detection problem, and it's the central challenge of circular queue implementation. This page explores multiple solutions, each with distinct trade-offs.

What You Will Learn

Understanding the Ambiguity

Let's trace through operations to see exactly when and why the ambiguity arises.

Setup: Circular queue with capacity 4, using Convention 2 (rear points to next slot).

Initial State (Empty):

front = 0, rear = 0
[_] [_] [_] [_]
 ↑
f,r

Condition: front == rear → EMPTY

After 4 Enqueues (Full):

enqueue(A): rear = 1 → [A] [_] [_] [_]
enqueue(B): rear = 2 → [A] [B] [_] [_]
enqueue(C): rear = 3 → [A] [B] [C] [_]
enqueue(D): rear = 0 → [A] [B] [C] [D]  (rear wrapped!)

front = 0, rear = 0
[A] [B] [C] [D]
 ↑
f,r

Condition: front == rear → FULL

The Paradox:

Both empty and full have front == rear! The pointers alone cannot distinguish these states.

The Fundamental Problem

Mathematical Perspective:

For a queue of capacity N:

Number of possible states: N + 1 (sizes 0 through N)
Unique pointer configurations: N (front can be at any of N positions; rear is determined by size)

Three Solutions:

Count Variable: Track size explicitly
Sacrificed Slot: Use only N-1 of N slots
Wrap Flag: Track whether rear has wrapped

Solution 1: The Count Variable Approach

The most straightforward solution is to maintain an explicit counter that tracks the number of elements in the queue. This completely eliminates the ambiguity.

How It Works:

Add a count variable initialized to 0
Increment count on each enqueue
Decrement count on each dequeue
Empty when count == 0; Full when count == capacity

count-variable-approach.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
/**
 * Circular Queue with Count Variable
 * The cleanest and most intuitive solution
 */
class CircularQueueWithCount<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private count: number;  // ← The key addition
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    // Empty and Full are now unambiguous
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    size(): number {
        return this.count;  // O(1) size query as a bonus!
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        this.count++;  // ← Track addition
    }
 
    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--;  // ← Track removal
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

Advantages

•Clean logic: Empty and full are trivially different
•O(1) size(): Know element count instantly
•Full capacity: All N slots are usable
•Simple implementation: Hard to get wrong
•Works with any convention: No pointer quirks

Disadvantages

•Extra memory: One additional integer
•Extra operations: Increment/decrement on each operation
•Potential inconsistency: Count and pointers can desync if buggy

Recommended Approach

Solution 2: The Sacrificed Slot Approach

How It Works:

Allocate an array of size N
Only use N-1 slots for actual elements
Full: (rear + 1) % capacity == front (next enqueue would reach front)
Empty: rear == front

Since we never fill the last slot, rear == front can only mean empty.

sacrificed-slot-approach.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
/**
 * Circular Queue with Sacrificed Slot
 * Uses N-1 of N slots to distinguish empty from full
 */
class CircularQueueSacrificedSlot<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;  // Total array size
 
    constructor(usableCapacity: number) {
        // Allocate one extra slot that will always remain empty
        this.capacity = usableCapacity + 1;
        this.data = new Array(this.capacity);
        this.front = 0;
        this.rear = 0;
    }
 
    // Empty: front and rear are at the same position
    isEmpty(): boolean {
        return this.front === this.rear;
    }
 
    // Full: rear is exactly one position behind front (circularly)
    // Adding another element would make rear == front (ambiguous!)
    isFull(): boolean {
        return (this.rear + 1) % this.capacity === this.front;
    }
 
    // Size must be computed from pointers
    size(): number {
        return (this.rear - this.front + this.capacity) % this.capacity;
    }
 
    // Maximum usable elements (not the array size)
    maxSize(): number {
        return this.capacity - 1;
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
    }
 
    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;
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

Visual Explanation:

Capacity = 5 (usable = 4)

Empty:     front = rear = 0
           [_] [_] [_] [_] [_]
            ↑
           f,r

1 element: front = 0, rear = 1
           [A] [_] [_] [_] [_]
            ↑   ↑
            f   r

4 elements (FULL): front = 0, rear = 4
           [A] [B] [C] [D] [_]
            ↑               ↑
            f               r
           
           isFull(): (4 + 1) % 5 = 0 == front ✓
           
           The slot at index 4 is kept empty!
           If we tried to enqueue, rear would
           become 0, matching front (ambiguous).

By never allowing rear to catch up to front, we preserve the distinction: front == rear always means empty, never full.

Advantages

•No count variable: Saves one integer of memory
•Pure pointer logic: Detection uses only front and rear
•Lower operation overhead: No count increment/decrement
•Common in hardware: Often used in FIFO buffers

Disadvantages

•Wasted slot: Lose 1/N of capacity
•O(n) size for large N: Size computation required
•Confusing capacity: Array size ≠ usable capacity
•Off-by-one traps: Easy to miscalculate boundaries

When to Use Sacrificed Slot

Solution 3: The Wrap Flag Approach

The wrap flag approach uses a boolean to track whether the rear pointer has 'wrapped around' and caught up to the front. This provides full capacity usage with minimal additional memory.

How It Works:

Add a wrapped boolean flag, initially false
Set wrapped = true when rear wraps and reaches front
Set wrapped = false when front advances past where rear was
Empty: front == rear && !wrapped
Full: front == rear && wrapped

wrap-flag-approach.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
/**
 * Circular Queue with Wrap Flag
 * Uses a boolean to track full/empty distinction
 */
class CircularQueueWithWrapFlag<T> {
    private data: (T | undefined)[];
    private front: number;
    private rear: number;
    private capacity: number;
    private wrapped: boolean;  // True if rear has caught up to front
 
    constructor(capacity: number) {
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.wrapped = false;
    }
 
    isEmpty(): boolean {
        return this.front === this.rear && !this.wrapped;
    }
 
    isFull(): boolean {
        return this.front === this.rear && this.wrapped;
    }
 
    size(): number {
        if (this.wrapped) {
            return this.capacity;  // Full
        }
        return (this.rear - this.front + this.capacity) % this.capacity;
    }
 
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow");
        }
        
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        
        // If rear caught up to front, we're now full
        if (this.rear === this.front) {
            this.wrapped = true;
        }
    }
 
    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;
        
        // After removing, we're definitely not full anymore
        this.wrapped = false;
        
        return element;
    }
 
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue is empty");
        }
        return this.data[this.front] as T;
    }
}

State Transitions:

Initial (Empty):
  front=0, rear=0, wrapped=false
  isEmpty: front==rear && !wrapped ✓
  
After filling all 4 slots:
  front=0, rear=0, wrapped=true
  isFull: front==rear && wrapped ✓
  
After one dequeue:
  front=1, rear=0, wrapped=false
  (wrapped cleared on dequeue)
  
After one more enqueue:
  front=1, rear=1, wrapped=true
  (rear caught front again)

The wrapped flag acts as a 'tie-breaker' when pointers are equal.

Advantages

•Full capacity: All N slots are usable
•Minimal memory: Just one boolean (1 byte)
•Clear semantics: Wrapped means 'rear caught front'

Disadvantages

•Complex logic: Must manage flag transitions carefully
•No O(1) size: Must compute from pointers + flag
•Easy to mishandle: Wrong flag update = corruption
•Less common: Many developers unfamiliar with it

Flag Management Is Tricky

Comparison of All Three Approaches

Let's systematically compare the three solutions across key dimensions:

Full/Empty Detection Strategies Compared
Criterion	Count Variable	Sacrificed Slot	Wrap Flag
Extra Memory	1 integer (4-8 bytes)	None	1 boolean (1 byte)
Usable Capacity	N (full)	N-1 (lose one)	N (full)
isEmpty()	O(1), trivial	O(1), pointer comparison	O(1), pointer + flag
isFull()	O(1), trivial	O(1), modular comparison	O(1), pointer + flag
size()	O(1), return count	O(1), pointer arithmetic	O(1), but complex
Implementation Complexity	Low	Medium	High
Bug Risk	Low	Medium (off-by-one)	High (flag sync)
Common Use Case	General purpose	Hardware, embedded	Rare, specialized

Decision Framework:

For most applications: Use the count variable approach. The minimal memory cost is negligible, and the implementation clarity prevents bugs.
For embedded/hardware with byte-level constraints: Use the sacrificed slot approach. The lost capacity is often acceptable when N is large.
For specialized low-level systems: Consider the wrap flag approach only if you need full capacity AND cannot afford an integer counter.
When in doubt: Choose count variable. It's the industry standard for software implementations.

Real-World Observation

Edge Case Analysis

Regardless of which approach you choose, certain edge cases require careful handling. Let's examine each:

Edge Case 1: Queue of Capacity 1

edge-case-capacity-1.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Capacity 1 is a degenerate case for sacrificed slot!
const queue = new CircularQueueSacrificedSlot(1);
 
// Actually allocates: capacity = 1 + 1 = 2
// Usable: 1 element (array has 2 slots, one always empty)
 
// For count variable approach: works fine, can hold 1 element
 
// For wrap flag: works, but the flag flips on every enqueue/dequeue
 
// Test thoroughly!
queue.enqueue("only");
console.log(queue.isFull());  // Should be true
console.log(queue.dequeue()); // "only"
console.log(queue.isEmpty()); // Should be true

Edge Case 2: Repeated Fill-Empty Cycles

edge-case-cycles.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Test that multiple fill/empty cycles work correctly
const queue = new CircularQueue(3);
 
for (let cycle = 0; cycle < 100; cycle++) {
    // Fill completely
    for (let i = 0; i < 3; i++) {
        queue.enqueue(`cycle${cycle}-item${i}`);
    }
    if (!queue.isFull()) {
        throw new Error(`Should be full at cycle ${cycle}`);
    }
    
    // Empty completely
    for (let i = 0; i < 3; i++) {
        queue.dequeue();
    }
    if (!queue.isEmpty()) {
        throw new Error(`Should be empty at cycle ${cycle}`);
    }
}
console.log("100 cycles completed successfully");

Edge Case 3: Alternating Operations

edge-case-alternating.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Alternating enqueue/dequeue stresses pointer management
const queue = new CircularQueue(4);
 
// Add 2, remove 1, repeatedly
for (let i = 0; i < 20; i++) {
    queue.enqueue(`item-${i * 2}`);
    queue.enqueue(`item-${i * 2 + 1}`);
    
    const removed = queue.dequeue();
    console.log(`Removed: ${removed}, Size: ${queue.size()}`);
    
    // Queue should never overflow (we add 2, remove 1, net +1)
    // But it will eventually fill up!
    if (queue.isFull()) {
        console.log("Queue filled, draining...");
        while (!queue.isEmpty()) {
            queue.dequeue();
        }
    }
}

Edge Case 4: Operations on Empty/Full Queue

edge-case-boundary-operations.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
// Verify error handling at boundaries
const queue = new CircularQueue(2);
 
// Operations on empty queue
try {
    queue.dequeue();
    throw new Error("Should have thrown Underflow");
} catch (e) {
    console.log("✓ Dequeue on empty throws correctly");
}
 
try {
    queue.peek();
    throw new Error("Should have thrown Empty error");
} catch (e) {
    console.log("✓ Peek on empty throws correctly");
}
 
// Fill the queue
queue.enqueue("A");
queue.enqueue("B");
 
// Operations on full queue
try {
    queue.enqueue("C");
    throw new Error("Should have thrown Overflow");
} catch (e) {
    console.log("✓ Enqueue on full throws correctly");
}
 
// Verify queue still works after failed operations
console.log(queue.peek());   // Should be "A"
console.log(queue.size());   // Should be 2

Test Your Implementation

Production-Ready Implementation

Here's a comprehensive, production-ready circular queue implementation using the recommended count variable approach, with all edge cases handled and thorough documentation:

production-circular-queue.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
 * A generic circular queue (ring buffer) implementation.
 * Uses a count variable for unambiguous full/empty detection.
 * All operations are O(1) time complexity.
 * 
 * @template T The type of elements stored in the queue
 */
class CircularQueue<T> {
    private readonly data: (T | undefined)[];
    private front: number;
    private rear: number;
    private readonly capacity: number;
    private count: number;
 
    /**
     * Creates a new circular queue with the specified capacity.
     * 
     * @param capacity Maximum number of elements the queue can hold
     * @throws Error if capacity is not a positive integer
     */
    constructor(capacity: number) {
        if (!Number.isInteger(capacity) || capacity <= 0) {
            throw new Error("Capacity must be a positive integer");
        }
        
        this.capacity = capacity;
        this.data = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    /**
     * Returns true if the queue contains no elements.
     * Time: O(1)
     */
    isEmpty(): boolean {
        return this.count === 0;
    }
 
    /**
     * Returns true if the queue is at maximum capacity.
     * Time: O(1)
     */
    isFull(): boolean {
        return this.count === this.capacity;
    }
 
    /**
     * Returns the number of elements currently in the queue.
     * Time: O(1)
     */
    size(): number {
        return this.count;
    }
 
    /**
     * Returns the maximum capacity of the queue.
     * Time: O(1)
     */
    getCapacity(): number {
        return this.capacity;
    }
 
    /**
     * Adds an element to the rear of the queue.
     * Time: O(1)
     * 
     * @param element The element to add
     * @throws Error if the queue is full
     */
    enqueue(element: T): void {
        if (this.isFull()) {
            throw new Error("Queue Overflow: Cannot enqueue to a full queue");
        }
        
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        this.count++;
    }
 
    /**
     * Removes and returns the element at the front of the queue.
     * Time: O(1)
     * 
     * @returns The element that was at the front
     * @throws Error if the queue is empty
     */
    dequeue(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Underflow: Cannot dequeue from an empty queue");
        }
        
        const element = this.data[this.front] as T;
        this.data[this.front] = undefined;  // Help garbage collection
        this.front = (this.front + 1) % this.capacity;
        this.count--;
        
        return element;
    }
 
    /**
     * Returns the element at the front without removing it.
     * Time: O(1)
     * 
     * @returns The element at the front
     * @throws Error if the queue is empty
     */
    peek(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Empty: No element to peek");
        }
        return this.data[this.front] as T;
    }
 
    /**
     * Returns the element at the rear without removing it.
     * Time: O(1)
     * 
     * @returns The element at the rear
     * @throws Error if the queue is empty
     */
    peekRear(): T {
        if (this.isEmpty()) {
            throw new Error("Queue Empty: No element to peek");
        }
        // Rear points to next empty slot, so go back one position
        const rearIndex = (this.rear - 1 + this.capacity) % this.capacity;
        return this.data[rearIndex] as T;
    }
 
    /**
     * Removes all elements from the queue.
     * Time: O(n)
     */
    clear(): void {
        // Clear references for garbage collection
        for (let i = 0; i < this.capacity; i++) {
            this.data[i] = undefined;
        }
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }
 
    /**
     * Returns the queue contents as an array in front-to-rear order.
     * Time: O(n)
     * 
     * @returns A new array containing all queue elements
     */
    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;
    }
 
    /**
     * Creates an iterator over queue elements (front to rear).
     * Allows use in for...of loops.
     */
    *[Symbol.iterator](): Iterator<T> {
        let current = this.front;
        for (let i = 0; i < this.count; i++) {
            yield this.data[current] as T;
            current = (current + 1) % this.capacity;
        }
    }
 
    /**
     * Returns a string representation of the queue for debugging.
     */
    toString(): string {
        return `CircularQueue(size=${this.count}, capacity=${this.capacity}): [${this.toArray().join(', ')}]`;
    }
}
 
// Export for use as a module
export { CircularQueue };

Production-Ready Features

Summary and Key Takeaways

This page addressed the critical full vs empty detection problem that challenges circular queue implementations.

Key Takeaways

•The ambiguity exists because pointer configurations cannot uniquely identify N+1 states (sizes 0 through N) using only two pointer values.
•Count variable is the simplest and most robust solution—use it unless you have specific constraints that prevent it.
•Sacrificed slot uses N-1 of N slots to ensure front==rear means only empty, used in embedded/hardware systems.
•Wrap flag uses a boolean to track full state, but is complex and error-prone.
•Edge cases matter: Test capacity-1 queues, repeated cycles, alternating operations, and boundary conditions.
•Production implementations should include input validation, proper errors, GC hints, and iterator support.

Module Complete:

You have now completed Module 4: Array-Based Queue & Circular Queue Implementation. You understand:

Why linear array queues fail (wasted space problem)
How circular queues use modular arithmetic for wraparound
Different pointer conventions and their trade-offs
Multiple strategies for full/empty detection

This knowledge equips you to implement efficient, correct queue data structures and understand existing implementations in libraries and codebases.

Module Complete

4 / 4