Stacks & QueuesProblem 25 of 38
Implement a Circular queue
Problem Statement
Design a Circular Queue (Ring Buffer) with a fixed capacity. The circular queue should efficiently use space by wrapping around when the end of the array is reached. Implement the following operations:
enQueue(x): Add element x to the rear of the queuedeQueue(): Remove the front elementFront(): Get the front elementRear(): Get the rear elementisEmpty(): Check if the queue is emptyisFull(): Check if the queue is full
Example:
MyCircularQueue cq = new MyCircularQueue(3);
cq.enQueue(1); // returns true
cq.enQueue(2); // returns true
cq.enQueue(3); // returns true
cq.enQueue(4); // returns false (queue is full)
cq.Rear(); // returns 3
cq.isFull(); // returns true
cq.deQueue(); // returns true
cq.enQueue(4); // returns true (slot freed up)
cq.Rear(); // returns 4
Approach 1: Brute Force (Using Array with Shifting)
Intuition
Use a simple array where dequeue shifts all elements to the left. This wastes time but is simple to implement. This is NOT a true circular queue.
Algorithm
- Enqueue: Add element at the current size position
- Dequeue: Remove first element and shift all others left
- No wrap-around, just linear operations
java
import java.util.*;
class MyQueueBruteForce {
private List<Integer> arr;
private int capacity;
public MyQueueBruteForce(int k) {
arr = new ArrayList<>();
capacity = k;
}
// O(1)
public boolean enQueue(int value) {
if (isFull()) return false;
arr.add(value);
return true;
}
// O(n) - Shifting elements
public boolean deQueue() {
if (isEmpty()) return false;
arr.remove(0);
return true;
}
// O(1)
public int Front() {
if (isEmpty()) return -1;
return arr.get(0);
}
// O(1)
public int Rear() {
if (isEmpty()) return -1;
return arr.get(arr.size() - 1);
}
// O(1)
public boolean isEmpty() {
return arr.isEmpty();
}
// O(1)
public boolean isFull() {
return arr.size() == capacity;
}
}Complexity Analysis
- Time Complexity: O(n) for deQueue (shifting), O(1) for others
- Space Complexity: O(n) for storing elements
Approach 2: Optimal (Circular Array with Modulo)
Intuition
Use modulo arithmetic to wrap around the array. Maintain front and rear pointers. When they reach the end, they wrap to the beginning. Use a count or special conditions to differentiate between empty and full states.
Algorithm
- Initialize array of size k, front = 0, rear = -1, count = 0
- Enqueue: rear = (rear + 1) % k, store element, increment count
- Dequeue: front = (front + 1) % k, decrement count
- Empty: count == 0
- Full: count == k
java
class MyCircularQueue {
private int[] arr;
private int front;
private int rear;
private int count;
private int capacity;
public MyCircularQueue(int k) {
arr = new int[k];
capacity = k;
front = 0;
rear = -1;
count = 0;
}
// O(1)
public boolean enQueue(int value) {
if (isFull()) return false;
rear = (rear + 1) % capacity;
arr[rear] = value;
count++;
return true;
}
// O(1)
public boolean deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
count--;
return true;
}
// O(1)
public int Front() {
if (isEmpty()) return -1;
return arr[front];
}
// O(1)
public int Rear() {
if (isEmpty()) return -1;
return arr[rear];
}
// O(1)
public boolean isEmpty() {
return count == 0;
}
// O(1)
public boolean isFull() {
return count == capacity;
}
public static void main(String[] args) {
MyCircularQueue cq = new MyCircularQueue(3);
System.out.println("enQueue(1): " + cq.enQueue(1)); // true
System.out.println("enQueue(2): " + cq.enQueue(2)); // true
System.out.println("enQueue(3): " + cq.enQueue(3)); // true
System.out.println("enQueue(4): " + cq.enQueue(4)); // false
System.out.println("Rear: " + cq.Rear()); // 3
System.out.println("isFull: " + cq.isFull()); // true
System.out.println("deQueue: " + cq.deQueue()); // true
System.out.println("enQueue(4): " + cq.enQueue(4)); // true
System.out.println("Rear: " + cq.Rear()); // 4
System.out.println("Front: " + cq.Front()); // 2
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(k) for the circular array
Approach 3: Optimal Without Count Variable
Intuition
Differentiate between empty and full states without using a count variable. Reserve one slot: the queue is full when (rear + 1) % k == front, and empty when front == -1 or front == (rear + 1) % k after dequeue.
Algorithm
- Initialize front = -1, rear = -1
- Empty: front == -1
- Full: (rear + 1) % k == front
- Handle first element and last element removal specially
java
class MyCircularQueue {
private int[] arr;
private int front;
private int rear;
private int capacity;
public MyCircularQueue(int k) {
arr = new int[k];
capacity = k;
front = -1;
rear = -1;
}
// O(1)
public boolean enQueue(int value) {
if (isFull()) return false;
if (isEmpty()) {
front = 0;
}
rear = (rear + 1) % capacity;
arr[rear] = value;
return true;
}
// O(1)
public boolean deQueue() {
if (isEmpty()) return false;
if (front == rear) {
front = -1;
rear = -1;
} else {
front = (front + 1) % capacity;
}
return true;
}
// O(1)
public int Front() {
if (isEmpty()) return -1;
return arr[front];
}
// O(1)
public int Rear() {
if (isEmpty()) return -1;
return arr[rear];
}
// O(1)
public boolean isEmpty() {
return front == -1;
}
// O(1)
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(k) for the circular array
Key Takeaways
- Ring Buffer: Circular queue is also called ring buffer, widely used in OS and networking
- Modulo Arithmetic: Key technique for wrap-around behavior
- Empty vs Full: Can use count variable or reserve one slot to differentiate
- Fixed Size: Circular queue has fixed capacity, unlike dynamic queue
- This is LeetCode #622 - Design Circular Queue
- Real-world use: Producer-consumer problems, CPU scheduling, streaming buffers