Design Circular Queue — Ring Buffer with O(1) Enqueue and Dequeue

Problem Statement#

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called a "Ring Buffer."

Implement the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with size k.
• int Front() Gets the front item from the queue. Returns -1 if the queue is empty.
• int Rear() Gets the last item from the queue. Returns -1 if the queue is empty.
• boolean enQueue(int value) Inserts an element. Returns true if successful.
• boolean deQueue() Deletes an element. Returns true if successful.
• boolean isEmpty() Checks whether the circular queue is empty.
• boolean isFull() Checks whether the circular queue is full.

You must solve the problem without using the built-in queue data structure. Each operation must run in O(1) time.

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls in total.

Input:  ["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"]
        [[3],[1],[2],[3],[4],[],[],[],[4],[]]
Output: [null,true,true,true,false,3,true,true,true,4]

Input:  ["MyCircularQueue","isEmpty","enQueue","Front","deQueue","isEmpty"]
        [[2],[],[10],[],[],[]]
Output: [null,true,true,10,true,true]

Why This Problem Matters#

LeetCode 622 Design Circular Queue is the canonical "implement a primitive data structure" question and shows up at Amazon, Google, Meta, and Apple. Ring buffers are everywhere in production:

• Producer-consumer queues between threads (lock-free single-producer single-consumer ring buffers).
• Audio and video frame buffers in real-time pipelines.
• Network packet rings (DPDK, kernel sk_buff rings).
• Streaming windows with bounded memory.
• Logging frameworks (circular log buffers like dmesg).

Acing this problem demonstrates that you understand index arithmetic, modular wrap-around, and the difference between FIFO and LIFO data structures.

The Core Insight#

A circular queue uses a fixed-size array plus two indices:

• head (or front): index of the next element to dequeue.
• tail (or rear): index after the last element (one past the rear) — or sometimes the index of the rear itself, depending on convention.

Wrap-around uses modulo arithmetic: idx = (idx + 1) % k.

The classic "is it empty or full?" ambiguity arises because head == tail could mean either. Two common fixes:

1. Track count separately. isEmpty() returns count == 0; isFull() returns count == k. Cleanest and most common in interviews.
2. Sacrifice one slot (so capacity is k - 1) and use (tail + 1) % k == head as "full." Saves one integer but loses one slot.

I will use approach 1 because it is clearer, uses all k slots, and matches the LeetCode constraints exactly.

Visual Dry Run#

Capacity k = 3. Operations: enQueue(1), enQueue(2), enQueue(3), deQueue(), enQueue(4).

Solution (Optimal)#

# Python — fixed-size array with head/tail indices and count, all O(1)
class MyCircularQueue:
    def __init__(self, k: int):
        self.data = [0] * k
        self.head = 0
        self.tail = 0
        self.count = 0
        self.capacity = k
 
    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.tail] = value
        self.tail = (self.tail + 1) % self.capacity
        self.count += 1
        return True
 
    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return True
 
    def Front(self) -> int:
        return -1 if self.isEmpty() else self.data[self.head]
 
    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.tail - 1 + self.capacity) % self.capacity]
 
    def isEmpty(self) -> bool:
        return self.count == 0
 
    def isFull(self) -> bool:
        return self.count == self.capacity

// JavaScript — circular queue with array + head/tail + count, all O(1)
class MyCircularQueue {
    constructor(k) {
        this.data = new Array(k);
        this.head = 0;
        this.tail = 0;
        this.count = 0;
        this.capacity = k;
    }
 
    enQueue(value) {
        if (this.isFull()) return false;
        this.data[this.tail] = value;
        this.tail = (this.tail + 1) % this.capacity;
        this.count++;
        return true;
    }
 
    deQueue() {
        if (this.isEmpty()) return false;
        this.head = (this.head + 1) % this.capacity;
        this.count--;
        return true;
    }
 
    Front() {
        return this.isEmpty() ? -1 : this.data[this.head];
    }
 
    Rear() {
        if (this.isEmpty()) return -1;
        return this.data[(this.tail - 1 + this.capacity) % this.capacity];
    }
 
    isEmpty() { return this.count === 0; }
    isFull()  { return this.count === this.capacity; }
}

Complexity:

Common Mistakes#

1. Using head == tail for both empty and full. Without a counter or wasted slot, the two conditions become indistinguishable.

2. Forgetting wrap-around for Rear(). When tail == 0, the rear element is at index capacity - 1. Compute as (tail - 1 + capacity) % capacity.

3. Not validating before operations. enQueue on a full queue must return false, not silently overwrite. Same for deQueue on an empty queue.

4. Confusing tail-as-rear vs tail-as-next-slot conventions. Pick one and stick with it. Mixing them causes off-by-one bugs everywhere.

5. Using a linked list when the constraint says O(1) per operation. A linked list also gives O(1) but has higher constant factors and cache misses. The array variant is preferred unless dynamic resizing is required.

Interview Tips#

• Open by asking: "Should the queue resize, or is the capacity strictly fixed?" The problem says fixed, but verifying shows attention to detail.
• Discuss both "count" and "wasted-slot" approaches. Pick "count" and justify.
• Walk through the wrap-around example on paper. Many candidates write code that works for the linear case but breaks at the wrap.
• For the linked-list alternative: "It also gives O(1), but has worse cache locality. For a fixed-size queue, the array variant is faster in practice."

Follow-up Questions#

1. Design Circular Deque (LC 641). Add insertFront and deleteLast; same template with both ends modular.
2. Lock-free single-producer single-consumer ring buffer. Use atomic head/tail and avoid count by using power-of-two capacity.
3. Resize on overflow. Allocate 2x array, copy in linear order, reset head=0 and tail=count.
4. Bounded blocking queue. Add producer-consumer condition variables for thread safety.
5. Priority queue with circular slots. Different problem — priority queues are not FIFO and need a heap.

Key Takeaways#

• A circular queue is a fixed-size array with head and tail pointers that wrap via modulo arithmetic.
• Track a separate count to disambiguate empty vs full while using all k slots.
• All operations — enQueue, deQueue, Front, Rear, isEmpty, isFull — run in O(1) time.
• The wrap-around for Rear() requires (tail - 1 + capacity) % capacity to handle the case where tail is at index 0.
• Ring buffers are foundational for producer-consumer queues, audio buffers, network packet rings, and bounded streaming windows.
• Mention the "wasted slot" alternative to demonstrate awareness of low-level implementations like lock-free SPSC queues.