Design Circular Queue
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Design a fixed-size queue that reuses freed space: enQueue, deQueue, Front, Rear, isEmpty, isFull.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How do you find the seat just after the last person?
- Hint 2What two numbers describe the whole queue?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A round table with k chairs. People join the queue by sitting in the next free chair after the last person, and the person at the front leaves from their chair. When you reach the last chair you simply continue at chair 0 because the table is a circle. You only need to remember where the front person sits and how many people are seated.
- The obvious way
A normal list with pop(0) shifts every item: O(n) per dequeue.
- The key insight
Keep an array of k seats, the index of the front seat and the number of people. enQueue writes at (front + count) mod k; deQueue moves the front seat forward by one (mod k) and reduces the count; Rear is the seat at (front + count - 1) mod k. Full means count == k; empty means count == 0.
- The algorithm
- Seats array, front = 0, count = 0.
- enQueue: if full, False; else write at (front + count) mod k, count + 1.
- deQueue: if empty, False; else front = (front + 1) mod k, count - 1.
- Front / Rear read the right seats.
Watch it run
Examplek = 3: enQueue 1, 2, 3, 4; Rear; isFull; deQueue; enQueue 4; Rear
enQueue 1, 2, 3 fill seats 0, 1, 2: all True. enQueue 4: the table is full, False.
seats: 1, 2, 3
Where people slip
- Track the count separately; front and rear indexes alone cannot tell a full ring from an empty one.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class MyCircularQueue:
def __init__(self, k):
self.seats = [0] * k
self.front_seat = 0 # where the first person sits
self.count = 0 # how many people are seated
def enQueue(self, value):
if self.isFull():
return False
self.seats[(self.front_seat + self.count) % len(self.seats)] = value # next free seat, wrapping round
self.count += 1
return True
def deQueue(self):
if self.isEmpty():
return False
self.front_seat = (self.front_seat + 1) % len(self.seats)
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.seats[self.front_seat]
def Rear(self):
if self.isEmpty():
return -1
return self.seats[(self.front_seat + self.count - 1) % len(self.seats)]
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == len(self.seats)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.