Topic 43 of 78
Circular Queue
Overview
A standard Queue implemented with an array suffers from 'false full' conditions—when elements are dequeued from the front, the empty space cannot be reused because the `tail` pointer is at the end of the array. A Circular Queue solves this by wrapping the `tail` back to index 0 when it reaches the end, effectively treating the array as a continuous loop. It ensures maximum O(1) memory reuse without needing a dynamic LinkedList.
Syntax
The magic is `(index + 1) % capacity`. This instantly wraps the pointer back to 0 when it hits the array bounds.
Array-Based Circular Queue
java
public class CircularQueue {
int[] queue;
int front = -1, rear = -1, size = 0, capacity;
public CircularQueue(int k) {
capacity = k;
queue = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) return false;
if (isEmpty()) front = 0;
// Wrap around using modulo arithmetic
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
if (front == rear) { // Last element removed
front = -1; rear = -1;
} else {
// Wrap around using modulo arithmetic
front = (front + 1) % capacity;
}
size--;
return true;
}
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == capacity; }
}Common Pitfalls
- Off-by-one errors when checking if the queue is full. Using a dedicated `size` variable makes it much easier than doing complex `(rear + 1) % capacity == front` checks.
- Forgetting to handle the case where dequeuing leaves the queue completely empty (requiring pointers to be reset to -1).
Interview Tips
- The modulo operator `%` is the secret sauce. Moving forward is always `(pointer + 1) % length`.
Real-World Example
Traffic light systems and streaming media buffers (like YouTube buffering video chunks) use fixed-size Circular Queues to continuously recycle memory without allocating new objects.
example
java
public class VideoBuffer {
CircularQueue frames = new CircularQueue(60); // 60 FPS buffer
public void receiveFrame(int frameData) {
if (frames.isFull()) {
frames.deQueue(); // Drop oldest frame if network is too slow
}
frames.enQueue(frameData);
}
}