Design Circular Queue
Design Circular Queue is a medium design data structures problem solved with the queue / circular buffer pattern.
The best approach, optimal (ring buffer with head and count), runs in O(1) for every operation time and O(k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (shifting list) up.
Problem
Implement MyCircularQueue, a FIFO queue with a fixed capacity k that reuses the slots freed at the front (a ring buffer), so it never needs to shift elements.
enQueue(value) adds value at the rear and returns true, or returns false if the queue is full. deQueue() removes the front element and returns true, or returns false if the queue is empty. Front() and Rear() return the first and last element, or -1 when the queue is empty. isEmpty() and isFull() report whether the queue holds 0 or k elements.
Examples
Example 1
- Input
MyCircularQueue(2), enQueue(4), enQueue(9), enQueue(1), Rear(), isFull(), deQueue(), enQueue(1), Front(), Rear()- Output
true, true, false, 9, true, true, true, 9, 1- Why
- The third enQueue fails because the queue already holds 2 items. After removing 4, there is room for 1, which wraps around to the freed slot.
Example 2
- Input
MyCircularQueue(1), Front(), deQueue(), isEmpty(), enQueue(6), Front(), Rear(), isEmpty()- Output
-1, false, true, true, 6, 6, false- Why
- On an empty queue Front returns -1 and deQueue fails. With one item, it is both the front and the rear.
Constraints
1 <= k <= 10000 <= value <= 1000- At most
3000calls in total toenQueue,deQueue,Front,Rear,isEmptyandisFull.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (shifting list) | O(k) for deQueue, O(1) otherwise | O(k) |
| Optimal (ring buffer with head and count) | O(1) for every operation | O(k) |
1Brute force (shifting list)
O(k) for deQueue, O(1) otherwiseRemoving the first element moves up to k - 1 elements.O(k)At most k elements are stored.Store the elements in a dynamic list in queue order and refuse to grow past k. Removing from the front shifts every remaining element one step left.
- enQueue: if size == k return false, else append and return true.
- deQueue: if empty return false, else remove index 0 and return true.
- Front / Rear: first / last element, or -1 if empty.
- isEmpty / isFull: compare size with 0 and k.
class MyCircularQueue {
private final List<Integer> items = new ArrayList<>();
private final int capacity;
public MyCircularQueue(int k) {
capacity = k;
}
public boolean enQueue(int value) {
if (items.size() == capacity) return false;
items.add(value);
return true;
}
public boolean deQueue() {
if (items.isEmpty()) return false;
items.remove(0);
return true;
}
public int Front() {
return items.isEmpty() ? -1 : items.get(0);
}
public int Rear() {
return items.isEmpty() ? -1 : items.get(items.size() - 1);
}
public boolean isEmpty() {
return items.isEmpty();
}
public boolean isFull() {
return items.size() == capacity;
}
}class MyCircularQueue:
def __init__(self, k: int):
self.items = []
self.capacity = k
def enQueue(self, value: int) -> bool:
if len(self.items) == self.capacity:
return False
self.items.append(value)
return True
def deQueue(self) -> bool:
if not self.items:
return False
self.items.pop(0)
return True
def Front(self) -> int:
return self.items[0] if self.items else -1
def Rear(self) -> int:
return self.items[-1] if self.items else -1
def isEmpty(self) -> bool:
return not self.items
def isFull(self) -> bool:
return len(self.items) == self.capacityclass MyCircularQueue {
vector<int> items;
int capacity;
public:
MyCircularQueue(int k) : capacity(k) {}
bool enQueue(int value) {
if ((int)items.size() == capacity) return false;
items.push_back(value);
return true;
}
bool deQueue() {
if (items.empty()) return false;
items.erase(items.begin());
return true;
}
int Front() {
return items.empty() ? -1 : items.front();
}
int Rear() {
return items.empty() ? -1 : items.back();
}
bool isEmpty() {
return items.empty();
}
bool isFull() {
return (int)items.size() == capacity;
}
};class MyCircularQueue {
constructor(k) {
this.items = [];
this.capacity = k;
}
enQueue(value) {
if (this.items.length === this.capacity) return false;
this.items.push(value);
return true;
}
deQueue() {
if (this.items.length === 0) return false;
this.items.shift();
return true;
}
Front() {
return this.items.length === 0 ? -1 : this.items[0];
}
Rear() {
return this.items.length === 0 ? -1 : this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
isFull() {
return this.items.length === this.capacity;
}
}2Optimal (ring buffer with head and count)
O(1) for every operationEach operation is a little index arithmetic and one array access.O(k)The array has exactly k slots.Allocate an array of exactly k slots. Track head (index of the front element) and count (how many elements are stored). Indices wrap with % k, so freed slots at the start are reused without moving anything. Keeping count separately makes full (count == k) and empty (count == 0) unambiguous.
- enQueue: if full return false; write the value at
(head + count) % k, increment count. - deQueue: if empty return false; move head to
(head + 1) % k, decrement count. - Front:
data[head]; Rear:data[(head + count - 1) % k]; both -1 when empty. - isEmpty:
count == 0; isFull:count == k.
class MyCircularQueue {
private final int[] data;
private int head = 0, count = 0;
public MyCircularQueue(int k) {
data = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) return false;
data[(head + count) % data.length] = value;
count++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
head = (head + 1) % data.length;
count--;
return true;
}
public int Front() {
return isEmpty() ? -1 : data[head];
}
public int Rear() {
return isEmpty() ? -1 : data[(head + count - 1) % data.length];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == data.length;
}
}class MyCircularQueue:
def __init__(self, k: int):
self.data = [0] * k
self.head = 0
self.count = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.data[(self.head + self.count) % len(self.data)] = value
self.count += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % len(self.data)
self.count -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.data[(self.head + self.count - 1) % len(self.data)]
def isEmpty(self) -> bool:
return self.count == 0
def isFull(self) -> bool:
return self.count == len(self.data)class MyCircularQueue {
vector<int> data;
int head = 0, count = 0;
public:
MyCircularQueue(int k) : data(k) {}
bool enQueue(int value) {
if (isFull()) return false;
data[(head + count) % data.size()] = value;
count++;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
head = (head + 1) % data.size();
count--;
return true;
}
int Front() {
return isEmpty() ? -1 : data[head];
}
int Rear() {
return isEmpty() ? -1 : data[(head + count - 1) % data.size()];
}
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == (int)data.size();
}
};class MyCircularQueue {
constructor(k) {
this.data = new Array(k).fill(0);
this.head = 0;
this.count = 0;
}
enQueue(value) {
if (this.isFull()) return false;
this.data[(this.head + this.count) % this.data.length] = value;
this.count++;
return true;
}
deQueue() {
if (this.isEmpty()) return false;
this.head = (this.head + 1) % this.data.length;
this.count--;
return true;
}
Front() {
return this.isEmpty() ? -1 : this.data[this.head];
}
Rear() {
return this.isEmpty() ? -1 : this.data[(this.head + this.count - 1) % this.data.length];
}
isEmpty() {
return this.count === 0;
}
isFull() {
return this.count === this.data.length;
}
}Edge cases to test
- Capacity 1: the same slot is both front and rear
Front/Rear/deQueueon an empty queueenQueueon a full queue must fail and change nothing- Many wrap-arounds: filling and emptying the queue repeatedly
- Telling full and empty apart when the head and tail indices coincide
Hints
Hint 1
A plain list where you remove from the front works, but removing from the front shifts every element.
Hint 2
Use a fixed array of size k with a head index and a count. The tail slot is (head + count) % k, and the rear element is at (head + count - 1) % k.
FAQ
What is the best time complexity for Design Circular Queue?
Optimal (ring buffer with head and count) runs in O(1) for every operation time and O(k) extra space. Each operation is a little index arithmetic and one array access.
Which pattern does Design Circular Queue use?
It is a design data structures problem that uses the queue / circular buffer pattern. Other problems with the same pattern: Design Hit Counter, First Unique Number, Design Snake Game.
Is there a brute force solution for Design Circular Queue?
Yes. Brute force (shifting list) takes O(k) for deQueue, O(1) otherwise time and O(k) space. Store the elements in a dynamic list in queue order and refuse to grow past k.
Which edge cases should I test for Design Circular Queue?
Capacity 1: the same slot is both front and rear; Front/Rear/deQueue on an empty queue; enQueue on a full queue must fail and change nothing; Many wrap-arounds: filling and emptying the queue repeatedly; Telling full and empty apart when the head and tail indices coincide.