Skip to main content
DSA patterns

Design Circular Queue

mediumStack and queue Must-do

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): add value at the back. Return true if it was added, or false if the queue is full.
  • deQueue(): remove the front value. Return true if one was removed, or false if the queue is empty.
  • Front() and Rear(): return the front or the back value, or -1 if the queue is empty.
  • isEmpty() and isFull(): report whether the queue holds no values, or k values.

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

Hint 1: A growable list works, but removing from its front shifts every other value. Think about whether you can avoid moving data at all.

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

  1. Allocate buf with k slots, set head = 0 and size = 0.
  2. enQueue: if full, return false. Otherwise write the value to buf[(head + size) % k], add 1 to size and return true.
  3. deQueue: if empty, return false. Otherwise set head = (head + 1) % k, subtract 1 from size and return true.
  4. Front is buf[head]. Rear is buf[(head + size - 1) % k]. Both return -1 when the queue is empty.
  5. Empty means size == 0. Full means size == 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 head index and a size; 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 as head. Then move head forward by one and leave size at k. The oldest value is overwritten and the new one becomes the rear. enQueue now 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 size counter, because both threads would write it. Let only the producer write tail and only the consumer write head, and allocate k + 1 slots 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 new tail, and the consumer must read tail before it reads the value. That needs volatile or AtomicInteger in Java, and std::atomic with 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.