Language Selection
Choose your preferred programming language
Showing: Python
Design Circular Queue
Problem Statement
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.
One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
Examples
Example 1:
Input:
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output:
[null, true, true, true, false, 3, true, true, true, 4]
Explanation:
MyCircularQueue circularQueue = new MyCircularQueue(3);
circularQueue.enQueue(1); // return true
circularQueue.enQueue(2); // return true
circularQueue.enQueue(3); // return true
circularQueue.enQueue(4); // return false, the queue is full
circularQueue.Rear(); // return 3
circularQueue.isFull(); // return true
circularQueue.deQueue(); // return true
circularQueue.enQueue(4); // return true
circularQueue.Rear(); // return 4
Constraints
1 <= k <= 10000 <= value <= 1000- At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull
Approach 1: Array with Head and Tail Pointers
Algorithm
Use a fixed-size array with head and tail pointers to implement a circular queue.
Steps:
- Use a fixed-size array to store elements
- Use head pointer to track the front of the queue
- Use tail pointer to track the next available position
- Use count to track the number of elements
- Implement circular behavior using modulo arithmetic
Implementation
Python:
class MyCircularQueue:
"""
Circular queue implementation using array
Time: O(1) for all operations
Space: O(k) where k is the capacity
"""
def __init__(self, k: int):
self.capacity = k
self.queue = [0] * k
self.head = 0
self.tail = 0
self.count = 0
def enQueue(self, value: int) -> bool:
"""Insert an element into the circular queue"""
if self.isFull():
return False
self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.count += 1
return True
def deQueue(self) -> bool:
"""Delete an element from the circular queue"""
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
self.count -= 1
return True
def Front(self) -> int:
"""Get the front item from the queue"""
if self.isEmpty():
return -1
return self.queue[self.head]
def Rear(self) -> int:
"""Get the last item from the queue"""
if self.isEmpty():
return -1
return self.queue[(self.tail - 1 + self.capacity) % self.capacity]
def isEmpty(self) -> bool:
"""Check whether the circular queue is empty"""
return self.count == 0
def isFull(self) -> bool:
"""Check whether the circular queue is full"""
return self.count == self.capacity
Java:
class MyCircularQueue {
/**
* Circular queue implementation using array
* Time: O(1) for all operations
* Space: O(k) where k is the capacity
*/
private int[] queue;
private int head;
private int tail;
private int count;
private int capacity;
public MyCircularQueue(int k) {
this.capacity = k;
this.queue = new int[k];
this.head = 0;
this.tail = 0;
this.count = 0;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
queue[tail] = value;
tail = (tail + 1) % capacity;
count++;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
head = (head + 1) % capacity;
count--;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return queue[head];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
return queue[(tail - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == capacity;
}
}
Go:
type MyCircularQueue struct {
queue []int
head int
tail int
count int
capacity int
}
// Constructor - Initialize circular queue
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{
queue: make([]int, k),
head: 0,
tail: 0,
count: 0,
capacity: k,
}
}
// EnQueue - Insert an element into the circular queue
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
this.queue[this.tail] = value
this.tail = (this.tail + 1) % this.capacity
this.count++
return true
}
// DeQueue - Delete an element from the circular queue
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
this.head = (this.head + 1) % this.capacity
this.count--
return true
}
// Front - Get the front item from the queue
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.queue[this.head]
}
// Rear - Get the last item from the queue
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
return this.queue[(this.tail-1+this.capacity)%this.capacity]
}
// IsEmpty - Check whether the circular queue is empty
func (this *MyCircularQueue) IsEmpty() bool {
return this.count == 0
}
// IsFull - Check whether the circular queue is full
func (this *MyCircularQueue) IsFull() bool {
return this.count == this.capacity
}
JavaScript:
/**
* Circular queue implementation using array
* Time: O(1) for all operations
* Space: O(k) where k is the capacity
*/
class MyCircularQueue {
constructor(k) {
this.capacity = k;
this.queue = new Array(k);
this.head = 0;
this.tail = 0;
this.count = 0;
}
enQueue(value) {
if (this.isFull()) {
return false;
}
this.queue[this.tail] = value;
this.tail = (this.tail + 1) % this.capacity;
this.count++;
return true;
}
deQueue() {
if (this.isEmpty()) {
return false;
}
this.head = (this.head + 1) % this.capacity;
this.count--;
return true;
}
Front() {
if (this.isEmpty()) {
return -1;
}
return this.queue[this.head];
}
Rear() {
if (this.isEmpty()) {
return -1;
}
return this.queue[(this.tail - 1 + this.capacity) % this.capacity];
}
isEmpty() {
return this.count === 0;
}
isFull() {
return this.count === this.capacity;
}
}
C#:
public class MyCircularQueue {
/// <summary>
/// Circular queue implementation using array
/// Time: O(1) for all operations
/// Space: O(k) where k is the capacity
/// </summary>
private int[] queue;
private int head;
private int tail;
private int count;
private int capacity;
public MyCircularQueue(int k) {
this.capacity = k;
this.queue = new int[k];
this.head = 0;
this.tail = 0;
this.count = 0;
}
public bool EnQueue(int value) {
if (IsFull()) {
return false;
}
queue[tail] = value;
tail = (tail + 1) % capacity;
count++;
return true;
}
public bool DeQueue() {
if (IsEmpty()) {
return false;
}
head = (head + 1) % capacity;
count--;
return true;
}
public int Front() {
if (IsEmpty()) {
return -1;
}
return queue[head];
}
public int Rear() {
if (IsEmpty()) {
return -1;
}
return queue[(tail - 1 + capacity) % capacity];
}
public bool IsEmpty() {
return count == 0;
}
public bool IsFull() {
return count == capacity;
}
}
Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(k) where k is the capacity
Key Insights
- Circular Buffer: Use modulo arithmetic to wrap around the array
- Head and Tail Pointers: Track front and back of the queue
- Count Variable: Efficiently determine if queue is empty or full
- Space Efficiency: Reuse space after dequeue operations
- Fixed Size: Pre-allocate array for predictable memory usage
Edge Cases
- Empty Queue: All operations return false or -1
- Full Queue: Enqueue returns false
- Single Element: Queue with one element
- Capacity 1: Queue with capacity 1
- Wrap Around: Head and tail pointers wrap around
Follow-up Questions
- Dynamic Size: What if the queue size can grow dynamically?
- Thread Safety: How would you make it thread-safe?
- Memory Management: How would you handle memory allocation?
- Performance: How would you optimize for high-frequency operations?
Common Mistakes
- Modulo Arithmetic: Incorrect calculation of head/tail positions
- Empty/Full Check: Wrong logic for determining queue state
- Index Bounds: Not handling array bounds properly
- Pointer Management: Incorrect head/tail pointer updates
Interview Tips
- Clarify Requirements: Ask about capacity limits and operation requirements
- Discuss Approaches: Mention both head-tail and tail-only approaches
- Handle Edge Cases: Discuss empty, full, and single-element scenarios
- Explain Algorithm: Walk through the circular buffer concept
- Optimize Space: Consider space-time tradeoffs