Design Circular Queue (LeetCode 622)

The problem

Design a circular queue with a fixed capacity k. Support:

• enQueue(v): add v at the rear; return True, or False if the queue is full;
• deQueue(): remove the front element; return True, or False if the queue is empty;
• Front() and Rear(): return the front or rear element, or −1 if empty;
• isEmpty() and isFull().

“Circular” means freed space at the front of the array can be reused for new elements at the back.

k = 3
enQueue(1), enQueue(2), enQueue(3) -> True, True, True
enQueue(4) -> False      (full)
Rear()     -> 3
isFull()   -> True
deQueue()  -> True       (removes 1)
enQueue(4) -> True       (reuses the freed slot)
Rear()     -> 4

How to think about it

Start with brute force. Use a Python list: append at the back, pop(0) at the front. pop(0) shifts every remaining element left, so dequeue is O(n). It also ignores the point of the exercise: a fixed block of memory that is reused.

A second attempt: an array with head and tail pointers that only move forward. Dequeue is now O(1) (just advance head), but once tail reaches the end of the array you are stuck, even if the front has empty slots.

The key insight: let the indices wrap around. Treat the array as a ring. Index i is followed by (i + 1) % k, so after the last slot comes slot 0 again. Keep two numbers: head (where the front element is) and count (how many elements are stored). Everything else follows:

• the rear element is at (head + count - 1) % k;
• the next free slot is at (head + count) % k;
• empty means count == 0, full means count == k.

Why count and not a tail pointer. With only head and tail, “empty” and “full” both look like head == tail, and you need an extra slot or a flag to tell them apart. Storing count makes both checks trivial. The tell for this pattern is “fixed-size buffer, reuse freed space”: a ring buffer with modular indices.

Approach

1. Allocate q = [0] * k, and set head = 0, count = 0, cap = k.
2. enQueue(v): if full, return False. Write v at (head + count) % cap, increase count, return True.
3. deQueue(): if empty, return False. Move head to (head + 1) % cap, decrease count, return True. (The old value can stay; it will be overwritten later.)
4. Front(): q[head] if not empty. Rear(): q[(head + count - 1) % cap] if not empty.
5. isEmpty() is count == 0; isFull() is count == cap.

Solution

class MyCircularQueue:
    def __init__(self, k): self.q = [0]*k; self.head = 0; self.count = 0; self.cap = k
    def enQueue(self, v):
        if self.count == self.cap: return False
        self.q[(self.head + self.count) % self.cap] = v; self.count += 1; return True   # next free slot, wrapped
    def deQueue(self):
        if self.count == 0: return False
        self.head = (self.head + 1) % self.cap; self.count -= 1; return True          # just move head
    def Front(self): return -1 if self.count == 0 else self.q[self.head]
    def Rear(self): return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.cap]
    def isEmpty(self): return self.count == 0
    def isFull(self): return self.count == self.cap
# k=3: enQueue(1,2,3)->True, enQueue(4)->False, Rear()->3, isFull()->True, deQueue()->True, enQueue(4)->True, Rear()->4

Dry run

With k = 3:

The second enQueue(4) writes to (1 + 2) % 3 = 0, wrapping round to the slot that 1 used to occupy.

Complexity

• Time: O(1) per operation. Each one is a few arithmetic steps and at most one array write.
• Space: O(k). The fixed array; nothing grows.

Edge cases and pitfalls

• Empty vs full ambiguity with head/tail only. Tracking count removes it.
• Rear() index is head + count - 1, not head + count. Off by one here returns the next free slot.
• Forgetting the modulo on any index walks off the end of the array.
• Front/Rear on an empty queue must return −1, not a stale value left in the array.
• Thread safety follow-up: a real ring buffer shared by producers and consumers needs locking or atomic indices.

Related problems

• Min Stack (LeetCode 155): another classic container you implement with a small, fixed set of fields.
• Design HashMap (LeetCode 706): a fixed array indexed with %, used for hashing instead of wrapping.
• LRU Cache (LeetCode 146): a bounded-capacity structure that decides what to drop when full.