Circular Queue Implementation Details
You'll learn: How to implement enqueue and dequeue operations in a circular queue while correctly detecting when it's full or empty.
The Core Challenge
In a circular queue using an array, both front and rear pointers wrap around to the beginning when they reach the array's end. The tricky part? Determining whether the queue is full or empty, since both conditions can look identical when front == rear.
Handling Full and Empty Conditions
There are two common approaches:
1. Sacrifice One Slot
Keep one array slot permanently unused. The queue is:
- Empty when
front == rear - Full when
(rear + 1) % capacity == front
This wastes one slot but makes the logic simple.
2. Use a Counter
Track the number of elements separately. The queue is:
- Empty when
count == 0 - Full when
count == capacity
Implementing Enqueue
To add an element:
- Check if the queue is full
- Insert the element at
rear - Move
rearforward usingrear = (rear + 1) % capacity - If using a counter, increment
count
Implementing Dequeue
To remove an element:
- Check if the queue is empty
- Retrieve the element at
front - Move
frontforward usingfront = (front + 1) % capacity - If using a counter, decrement
count
The Modulo Magic
The % capacity operation is what makes it circular—when a pointer reaches the end (index capacity - 1), adding 1 and taking modulo wraps it back to 0.
Key Takeaway: Circular queues use modulo arithmetic to wrap pointers and require special logic (sacrificed slot or counter) to distinguish between full and empty states.