Design a Circular Queue
- mosesg1123
- May 5
- 4 min read
Circular queues (ring buffers) come up in real‑world systems like streaming data buffers, IO scheduling, and task schedulers. They let you use fixed memory while wrapping around seamlessly, making enqueue and dequeue both O(1).
Problem Statement
Design your own circular queue implementation with the following operations:
MyCircularQueue(k): Constructor, set the capacity to k.
enQueue(value): Insert an element into the circular queue. Return true if successful.
deQueue(): Delete an element from the circular queue. Return true if successful.
Front(): Get the front item. Return -1 if the queue is empty.
Rear(): Get the last item. Return -1 if the queue is empty.
isEmpty(): Check whether the queue is empty.
isFull(): Check whether the queue is full.
All operations should run in O(1) time and use O(k) space.
1. Clarify Requirements Before Jumping Into Code
I need to confirm details:
When the queue is full, further enQueue should return false.
When empty, deQueue returns false, and Front/Rear return -1.
Capacity k will be > 0.
We cannot grow the buffer—fixed size.
Head and tail must wrap around (modulo arithmetic).
2. Identify the Category of the Question
This is a data structure design problem focusing on array-based ring buffer. Common patterns include:
Array with head/tail pointers and modulo wrap
Linked list with manual pointer reset (less common here)
Fixed-size buffer for streaming or scheduling
Two-pointer techniques for sliding windows
Recognizing enqueue/dequeue at opposite ends suggests head/tail indices and modulo arithmetic.
3. Consider a Brute‑Force Approach to Understand the Problem
A naive way: use a dynamic array (e.g., ArrayList):
enQueue(x): list.add(x) if size < k.
deQueue(): list.remove(0) shifting all elements left.
That gives correct FIFO behavior but:
Time: enQueue O(1), deQueue O(n) for remove(0).
Space: O(k).
Drawback: deQueue is O(n), not O(1).
This brute-force confirms behavior but fails performance.
4. Brainstorm More Solutions
Linked List with Count:Maintain head and tail pointers and a count.
Pros: deQueue O(1), enQueue O(1)
Cons: Extra node objects, no fixed cap guard built‑in
Two Stacks (Queue on Stacks):Use two stacks to simulate queue.
Pros: Amortized O(1) ops
Cons: Uses two stacks, not fixed-size array, hard to enforce capacity
Ring Buffer (Optimal):Use a fixed-size array, track head, tail, and count.
enQueue: if count==capacity false; else write at tail, tail = (tail+1)%capacity, count++.
deQueue: if empty false; else head = (head+1)%capacity, count--.
Front: read at head if not empty.
Rear: read at (tail-1+capacity)%capacity if not empty.
Pros: All operations O(1), uses exactly O(k) space
Cons: Must handle modulo carefully
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Dynamic array (remove0) | enQ O(1), deQ O(n) | O(k) | Simple to code | deQueue too slow |
Linked list + count | O(1) each | O(k) nodes | True O(1) all ops | Extra node allocation, no array |
Two stacks | Amortized O(1) | O(k) stacks | Shows stack vs queue trick | No fixed cap enforcement easily |
Ring buffer (head/tail) | O(1) each | O(k) array | Fixed array, O(1) all ops, capacity | Modulo logic needs care |
The ring buffer best meets O(1) time, O(k) space, and fixed capacity.
6. Write Pseudocode to Structure Your Thoughts
function MyCircularQueue(k):
array = new int[k]
head = 0; tail = 0; count = 0; capacity = k
function enQueue(x):
if count == capacity: return false
array[tail] = x
tail = (tail + 1) mod capacity
count += 1
return true
function deQueue():
if count == 0: return false
head = (head + 1) mod capacity
count -= 1
return true
function Front():
return (count == 0) ? -1 : array[head]
function Rear():
return (count == 0) ? -1 : array[(tail - 1 + capacity) mod capacity]
function isEmpty():
return count == 0
function isFull():
return count == capacity
7. Consider Edge Cases
Capacity = 1: enQueue then deQueue then enQueue again.
Fill then empty then fill: pointers wrap correctly.
Multiple wrap‑arounds: many enqueue/dequeue pairs to exercise modulo.
Front/Rear on empty: return −1.
Front/Rear on full: return correct first/last elements.
8. Write Full Code Syntax (in Python)
class MyCircularQueue:
def __init__(self, k):
self.capacity = k
self.data = [0]*k
self.head = 0
self.tail = 0
self.count = 0
def enQueue(self, value):
if self.count == self.capacity:
return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.count += 1
return True
def deQueue(self):
if self.count == 0:
return False
self.head = (self.head + 1) % self.capacity
self.count -= 1
return True
def Front(self):
return -1 if self.count == 0 else self.data[self.head]
def Rear(self):
return -1 if self.count == 0 else self.data[(self.tail - 1) % self.capacity]
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.capacity
9. Test Your Code
q = MyCircularQueue(3)
assert q.enQueue(1) == True
assert q.enQueue(2) == True
assert q.enQueue(3) == True
assert q.enQueue(4) == False # full
assert q.Rear() == 3
assert q.isFull() == True
assert q.deQueue() == True
assert q.enQueue(4) == True # 4 wraps around
assert q.Rear() == 4
assert q.Front() == 2
# wrap multiple times
assert q.deQueue() == True # removes 2
assert q.deQueue() == True # removes 3
assert q.deQueue() == True # removes 4
assert q.isEmpty() == True
assert q.deQueue() == False # empty
assert q.Front() == -1
assert q.Rear() == -1
print("All tests passed!") # should output if all asserts succeed
10. Key Lessons to Remember for Future Questions
Ring buffer pattern: head and tail indices with modulo wrap.
Always track size separately to distinguish full vs empty.
Pseudocode-first helps prevent off-by-one modulo errors.
Testing capacity=1 and multiple wrap‑around cycles ensures robustness.
Comparing brute‑force and optimal approaches demonstrates depth of thought.
Fixed-size structures are common in systems code—master modulo indexing.
Good Luck and Happy Coding!
Comments