Design Circular Queue
Problem statement
Build a first-in, first-out queue called MyCircularQueue that has a fixed capacity k and reuses its storage in a ring instead of growing. The constructor takes k. The class must support these operations:
enQueue(value): addvalueat the back. Returntrueif it was added, orfalseif the queue is full.deQueue(): remove the front value. Returntrueif one was removed, orfalseif the queue is empty.Front()andRear(): return the front or the back value, or-1if the queue is empty.isEmpty()andisFull(): report whether the queue holds no values, orkvalues.
Do not use a built-in queue type. Every operation should take constant time.
Examples
Example 1
Input: MyCircularQueue(3)
enQueue(1), enQueue(2), enQueue(3), enQueue(4), Rear(), isFull(), deQueue(), enQueue(4), Rear()
Output: [null, true, true, true, false, 3, true, true, true, 4]
Explanation: The constructor returns nothing (null). The first three enQueue calls fill the queue. The fourth enQueue(4) fails because the queue is full, so it returns false, and Rear() is still 3. After deQueue() removes 1, there is room again, so enQueue(4) works and the new Rear() is 4.
Hints
Approach
Optimal: Ring buffer
Intuition
Picture the array bent into a ring, so the slot after the last one is the first one again. Instead of moving values, move two markers: head is the index of the front value, and size says how many values are stored. A value is added just after the last stored one, at (head + size) % k. A value is removed by moving head one step forward, and the old value is simply overwritten later. The % makes an index that runs off the end wrap back to 0. This is faster than the list because no value is ever moved.
Steps
- Allocate
bufwithkslots, sethead = 0andsize = 0. enQueue: if full, returnfalse. Otherwise write the value tobuf[(head + size) % k], add 1 tosizeand returntrue.deQueue: if empty, returnfalse. Otherwise sethead = (head + 1) % k, subtract 1 fromsizeand returntrue.Frontisbuf[head].Rearisbuf[(head + size - 1) % k]. Both return-1when the queue is empty.- Empty means
size == 0. Full meanssize == k.
Dry run
Capacity 3, same calls as Example 1.
| call | slot written | head | size | buf after | result |
|---|---|---|---|---|---|
| enQueue(1) | (0 + 0) % 3 = 0 | 0 | 1 | [1, _, _] | true |
| enQueue(2) | (0 + 1) % 3 = 1 | 0 | 2 | [1, 2, _] | true |
| enQueue(3) | (0 + 2) % 3 = 2 | 0 | 3 | [1, 2, 3] | true |
| enQueue(4) | none, full | 0 | 3 | [1, 2, 3] | false |
| Rear() | reads (0 + 3 - 1) % 3 = 2 | 0 | 3 | [1, 2, 3] | 3 |
| deQueue() | head = (0 + 1) % 3 = 1 | 1 | 2 | [1, 2, 3] | true |
| enQueue(4) | (1 + 2) % 3 = 0 | 1 | 3 | [4, 2, 3] | true |
| Rear() | reads (1 + 3 - 1) % 3 = 0 | 1 | 3 | [4, 2, 3] | 4 |
The last enQueue wrapped around to slot 0. That is what makes the queue circular.
Edge cases: an empty queue returns -1 from Front and Rear, and false from deQueue. A capacity of 1 works because (head + 1) % 1 is always 0.
Complexity
Time O(1) - for every operation - Each call does a fixed number of steps: one comparison, one modulo and one or two assignments. No loop and no shifting happens. The cost does not depend on k or on how many values are stored.
Space O(k) - One array of size k is allocated once and never grows or shrinks. Besides it, only two integers are kept, `head` and `size`. Freed slots are reused, so memory stays fixed.
class MyCircularQueue:
def __init__(self, k: int):
self.buf = [0] * k # fixed storage, allocated once
self.head = 0 # index of the front element
self.size = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
tail = (self.head + self.size) % len(self.buf) # wrap around the end
self.buf[tail] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % len(self.buf)
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.buf[self.head]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.buf[(self.head + self.size - 1) % len(self.buf)]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == len(self.buf)
if __name__ == "__main__":
q = MyCircularQueue(3)
out = ["null"]
for r in (q.enQueue(1), q.enQueue(2), q.enQueue(3), q.enQueue(4), q.Rear(),
q.isFull(), q.deQueue(), q.enQueue(4), q.Rear()):
out.append(str(r).lower())
print("[" + ", ".join(out) + "]")RecapThe whole problem in a few lines, for the night before
- Spot it: a fixed-size queue that reuses freed slots
- Idea: an array with a
headindex and asize; the next free slot is(head + size) % k - Cost: O(1) per operation, O(k) space
- Trap: a full queue and an empty queue can look the same if you only compare head and tail; track
size
Interview follow-ups
Make it overwrite the oldest value when full instead of rejecting, as a "keep the last N log lines" buffer does.
In
enQueue, when the queue is full, write the new value at the slot(head + size) % k, which is the same slot ashead. Then moveheadforward by one and leavesizeatk. The oldest value is overwritten and the new one becomes the rear.enQueuenow always succeeds, and every operation is still O(1).Make it safe for one producer thread and one consumer thread at the same time.
Drop the shared
sizecounter, because both threads would write it. Let only the producer writetailand only the consumer writehead, and allocatek + 1slots so empty (head == tail) and full ((tail + 1) % (k + 1) == head) can be told apart. The producer must write the value before it publishes the newtail, and the consumer must readtailbefore it reads the value. That needsvolatileorAtomicIntegerin Java, andstd::atomicwith release and acquire ordering in C++. This is lock-free and O(1). With several producers or consumers you need a lock or compare-and-swap.
Frequently asked questions
With only head and tail, an empty queue and a full queue both have head == tail. You then need an extra flag or a wasted slot to tell them apart. A size counter removes the ambiguity, and it also gives isEmpty and isFull in one comparison.
The next free slot is head + size, so the last filled slot is one before it. The modulo handles the case where that slot has wrapped to the start of the array. Without the % k, Rear would read past the end of the array after the queue wraps.
No. It only moves head forward and lowers size, so the old value stays in the array until a later enQueue overwrites it. This is safe because Front, Rear and the size checks never look at slots outside the live range. For plain integers nothing more is needed. For objects you may want to clear the slot so it can be freed.
Everywhere memory must stay bounded: the kernel's dmesg log buffer, network card receive and transmit rings, fixed-size in-memory log and metric buffers that keep only the latest N samples, and producer and consumer queues between threads.
