Circular Queue Concept
What you'll learn: How to use modular arithmetic to wrap array indices around, allowing a queue to reuse freed space efficiently.
The Problem with Linear Array Queues
In a simple array-based queue, you enqueue at the rear and dequeue from the front. As you dequeue elements, the front index moves forward, leaving unused space at the beginning of the array. Eventually, even though those early slots are empty, rear reaches the end of the array and you can't enqueue anymore—wasteful!
The Circular Solution
A circular queue treats the array as if it wraps around: when you reach the last index, the next position loops back to index 0. This creates a circular, "ring buffer" effect.
How Modular Arithmetic Enables Wrapping
The key is the modulo operator (%). When you increment an index, you apply mod size:
nextIndex = (currentIndex + 1) % arraySize
Example: If arraySize = 5 and currentIndex = 4, then (4 + 1) % 5 = 0. You've wrapped around to the beginning!
This same technique applies to both front and rear:
- Enqueue:
rear = (rear + 1) % size - Dequeue:
front = (front + 1) % size
Analogy
Imagine a circular dining table with 5 chairs. When the 5th person sits, the next person wraps around to chair 1. No chair is ever "abandoned"—everyone just keeps moving clockwise, reusing seats as people leave.
Benefits
- No wasted space: Empty slots at the front become available again.
- Fixed memory: The array size stays constant.
- Efficient: Enqueue and dequeue remain O(1).
Key Takeaway: Circular queues use modular arithmetic to wrap indices, transforming a linear array into a reusable ring that eliminates wasted space.