Design Circular Queue — Solution in Python, Java & C++
Design Circular Queue solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Design Circular Queue is a medium coding problem on arrays and queue, asked in Amazon, Microsoft, Meta and Apple interviews.
- Difficulty: Medium
- Topics: Arrays, Queue
- Asked at: Amazon, Microsoft, Meta, Apple
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Implement a circular queue (ring buffer): a FIFO queue of fixed capacity stored in an array whose last slot wraps around to the first, so the space freed at the front can be reused. Do not use a built-in queue. Write the class MyCircularQueue:
MyCircularQueue(int k)creates a queue that holds at mostkelements.boolean enQueue(int value)addsvalueat the rear; returnstrueon success,falseif the queue is full.boolean deQueue()removes the front element; returnstrueon success,falseif the queue is empty.int Front()returns the front element, or-1if the queue is empty.int Rear()returns the last element, or-1if the queue is empty.boolean isEmpty()/boolean isFull()report whether the queue is empty / full.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
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: Capacity 3: the fourth enQueue fails. After one deQueue there is room again, and 4 becomes the rear — stored in the slot 1 used to occupy.
Example 2
Input: ["MyCircularQueue","Front","deQueue","enQueue","Front","Rear","deQueue","isEmpty"]
[[1],[],[],[7],[],[],[],[]]
Output: [null,-1,false,true,7,7,true,true]
Explanation: On an empty queue Front is -1 and deQueue fails. With capacity 1, 7 is both front and rear.
Constraints
1 <= k <= 10000 <= value <= 1000At most 3000 calls are made to enQueue, deQueue, Front, Rear, isEmpty and isFull
Hints for Design Circular Queue
Hint 1
Use an array of size
kand never shift elements — move indices instead.Hint 2
Keep the index of the front element and the number of elements; the rear is then
(front + count - 1) % k.Hint 3
enQueue writes at
(front + count) % k; deQueue just advancesfront = (front + 1) % k. With an explicit count, "empty" and "full" are never ambiguous.
How to solve Design Circular Queue
A fixed array plus two numbers — where the front is and how many elements there are — describes the whole queue. Positions are taken modulo k, so the queue wraps around the end of the array and reuses freed slots without moving anything.
Approach
- Store
bufof sizek,head = 0,count = 0. enQueue(v): ifcount == kreturn false; setbuf[(head + count) % k] = v, incrementcount.deQueue(): ifcount == 0return false;head = (head + 1) % k, decrementcount.Front()isbuf[head]andRear()isbuf[(head + count - 1) % k], or-1when empty.isEmpty()iscount == 0;isFull()iscount == k.
Why it works
The elements always occupy the count slots starting at head and wrapping around. enQueue fills the next slot after the last one, deQueue releases the first, and neither touches the others, so the FIFO order is preserved and every slot is reused once it is freed.
Complexity
- Time —
O(1) per operation - Space —
O(k)
Pitfalls
- With only a head and a tail index,
head == tailmeans both empty and full — keep a count (or leave one slot unused). - Front and Rear must return -1 on an empty queue rather than a stale slot.
Reference solution
Python
class MyCircularQueue:
def __init__(self, k: int):
self.buf = [0] * k
self.head = 0
self.count = 0
def enQueue(self, value: int) -> bool:
if self.count == len(self.buf):
return False
self.buf[(self.head + self.count) % len(self.buf)] = value
self.count += 1
return True
def deQueue(self) -> bool:
if self.count == 0:
return False
self.head = (self.head + 1) % len(self.buf)
self.count -= 1
return True
def Front(self) -> int:
return self.buf[self.head] if self.count else -1
def Rear(self) -> int:
return self.buf[(self.head + self.count - 1) % len(self.buf)] if self.count else -1
def isEmpty(self) -> bool:
return self.count == 0
def isFull(self) -> bool:
return self.count == len(self.buf)Java
class MyCircularQueue {
private int[] buf;
private int head = 0, count = 0;
public MyCircularQueue(int k) {
buf = new int[k];
}
public boolean enQueue(int value) {
if (count == buf.length) return false;
buf[(head + count) % buf.length] = value;
count++;
return true;
}
public boolean deQueue() {
if (count == 0) return false;
head = (head + 1) % buf.length;
count--;
return true;
}
public int Front() {
return count == 0 ? -1 : buf[head];
}
public int Rear() {
return count == 0 ? -1 : buf[(head + count - 1) % buf.length];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == buf.length;
}
}C++
class MyCircularQueue {
vector<int> buf;
int head = 0, count = 0;
public:
MyCircularQueue(int k) : buf(k) {}
bool enQueue(int value) {
if (count == (int)buf.size()) return false;
buf[(head + count) % buf.size()] = value;
count++;
return true;
}
bool deQueue() {
if (count == 0) return false;
head = (head + 1) % buf.size();
count--;
return true;
}
int Front() {
return count == 0 ? -1 : buf[head];
}
int Rear() {
return count == 0 ? -1 : buf[(head + count - 1) % buf.size()];
}
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == (int)buf.size();
}
};JavaScript
var MyCircularQueue = function(k) {
this.k = k;
this.buf = [];
this.head = 0;
this.count = 0;
};
MyCircularQueue.prototype.enQueue = function(value) {
if (this.count === this.k) return false;
this.buf[(this.head + this.count) % this.k] = value;
this.count++;
return true;
};
MyCircularQueue.prototype.deQueue = function() {
if (this.count === 0) return false;
this.head = (this.head + 1) % this.k;
this.count--;
return true;
};
MyCircularQueue.prototype.Front = function() {
return this.count === 0 ? -1 : this.buf[this.head];
};
MyCircularQueue.prototype.Rear = function() {
return this.count === 0 ? -1 : this.buf[(this.head + this.count - 1) % this.k];
};
MyCircularQueue.prototype.isEmpty = function() {
return this.count === 0;
};
MyCircularQueue.prototype.isFull = function() {
return this.count === this.k;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Queues and Deques