Circular Queue
A circular queue (or ring buffer) is a queue where the last position is connected back to the first position. This eliminates the wasted space that occurs in a simple array queue after dequeue operations. It's efficient for fixed-size buffers.
The array-based queue implementation shown earlier is actually a circular queue because we used modulo arithmetic to wrap around. Let's highlight the circular logic.
Key points of circular queue:
- Maintain front and rear indices that wrap around using modulus.
- Use a size counter to distinguish between full and empty.
- When enqueuing: `rear = (rear + 1) % capacity`.
- When dequeuing: `front = (front + 1) % capacity`.
- Full condition: `size == capacity`.
- Empty condition: `size == 0`.
This design reuses the array positions and is commonly used in systems like IO buffers, task queues, etc.
Two Minute Drill
- Circular queue wraps around to reuse space.
- Uses modulo arithmetic for index updates.
- Distinguish empty/full by maintaining size (or using one empty slot).
- Both enqueue and dequeue are O(1).
- Used in fixed-size buffer applications.
Need more clarification?
Drop us an email at career@quipoinfotech.com