DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Design Circular Queue

mediumStack and queue Must-do

Problem statement

Design a fixed-capacity FIFO queue, MyCircularQueue, that reuses its storage in a ring instead of growing. The constructor takes the capacity k. Support:

  • enQueue(value): add to the back; return true on success, false if the queue is full.
  • deQueue(): remove from the front; return true on success, false if it is empty.
  • Front() and Rear(): return the front or back value, or -1 if the queue is empty.
  • isEmpty() and isFull().

Do not use a built-in queue type. Every operation should run in constant time.

Examples

Example 1

Input: MyCircularQueue(2) enQueue(10), enQueue(20), enQueue(30), isFull(), deQueue(), enQueue(30), Front(), Rear()

Output: true, true, false, true, true, true, 20, 30

Explanation: The third enQueue fails because the queue is full. After removing 10 there is room, so 30 goes in and the ring wraps around.

Example 2

Input: MyCircularQueue(3) Front(), Rear(), deQueue(), enQueue(5), Rear(), deQueue(), isEmpty()

Output: -1, -1, false, true, 5, true, true

Explanation: Reading or removing from an empty queue returns -1 or false instead of failing.

Hints

Approach

Use a ring buffer: one array of size k, allocated once, plus two numbers.

  1. head is the index of the front element; size is how many elements are stored.
  2. enQueue: if not full, write to (head + size) % k and increase size.
  3. deQueue: if not empty, move head to (head + 1) % k and decrease size. The old value is simply overwritten later.
  4. Front is buf[head]; Rear is buf[(head + size - 1) % k].
  5. Empty means size == 0; full means size == k.

The modulo makes indices wrap from the end of the array back to the start, so no element is ever moved.

ComplexityTime O(1) for every operationSpace O(k)
Python
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)

Follow-up questions

  • Make it overwrite the oldest element when full instead of rejecting, as a "keep the last N log lines" buffer does.
  • Make it safe for one producer thread and one consumer thread at the same time.

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.

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.

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.