Circular Queue
Overview
A standard Queue implemented with an array suffers from 'memory drift'. If you enqueue 5 items and dequeue 5 items, the front and rear pointers have drifted to the end of the array. The array is technically empty, but you can't add any more items without an expensive O(N) shift operation.
A Circular Queue solves this by connecting the end of the array back to the beginning using modulo arithmetic ((index + 1) % capacity). When the rear pointer reaches the end of the array, it seamlessly wraps around to index 0, reusing the empty spaces left behind by dequeued elements.
This guarantees strict O(1) performance for both enqueue and dequeue operations with zero memory waste and zero shifting, making it the standard implementation for bounded (fixed-size) queues in operating systems and hardware buffers.
Syntax
public class CircularQueue {
private int[] array;
private int front;
private int rear;
private int size;
private int capacity;
public CircularQueue(int k) {
capacity = k;
array = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public boolean enqueue(int value) {
if (isFull()) return false;
// Modulo wrap-around! If rear was at capacity-1, it becomes 0
rear = (rear + 1) % capacity;
array[rear] = value;
size++;
return true;
}
public boolean dequeue() {
if (isEmpty()) return false;
// Modulo wrap-around for the front pointer
front = (front + 1) % capacity;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : array[front];
}
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == capacity; }
}Common Pitfalls
- Miscalculating the modulo arithmetic.
(rear + 1) % capacityis correct. Doingrear % capacity + 1is wrong and will throw an ArrayIndexOutOfBoundsException. - Failing to track
sizecorrectly. Differentiating between a full queue and an empty queue based purely onfrontandrearpointers is complex (they often overlap in both states). Maintaining a dedicatedsizeinteger makesisFull()andisEmpty()trivial and bug-free. - Not handling concurrent access. In real-world systems, circular queues (ring buffers) are highly concurrent. Modifying
front,rear, andsizefrom different threads will corrupt the queue without proper synchronization or volatile variables.
Interview Questions
A standard array-based queue suffers from 'false full' conditions. As items are dequeued, empty space is left at the front of the array. Once the rear pointer hits the array's end, you cannot enqueue more items, even if the array is mostly empty, unless you shift all elements left (O(N)). A circular queue reuses the front spaces via modulo wrap-around, maintaining strict O(1) operations.
A Ring Buffer is simply another name for a Circular Queue. The term is most commonly used in operating system design, hardware drivers, and low-level networking where a fixed-size contiguous memory block is used to buffer data streams continuously.
Real-World Example
Video and audio streaming software (like YouTube or Spotify clients) use Circular Queues (Ring Buffers). The network thread downloads video frames and enqueues them. The video player thread dequeues them and paints them to the screen. The buffer is a fixed size (e.g., 5 seconds of video) to prevent the application from consuming all available RAM.
// A Ring Buffer for Audio Streaming
class AudioStreamBuffer {
CircularQueue buffer = new CircularQueue(4096); // 4KB bounded buffer
// Network thread calls this
public void onDataReceived(byte[] data) {
for (byte b : data) {
// If full, we might drop packets or block the thread
buffer.enqueue(b);
}
}
// Audio hardware thread calls this
public byte[] getNextAudioChunk(int size) {
byte[] chunk = new byte[size];
for (int i = 0; i < size; i++) {
chunk[i] = (byte) buffer.Front();
buffer.dequeue();
}
return chunk;
}
}Check Your Knowledge
Test your understanding of Circular Queue with these quick questions.