Design Circular Queue

LeetCode 622: Design Circular Queue Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a fixed-size array combined with modulo arithmetic to wrap indices, allowing O(1) enqueue and dequeue operations without shifting elements.

The Design Circular Queue problem requires implementing a specific type of queue known as a Ring Buffer. Unlike a standard linear queue, where removing elements from the front creates unusable void space, a circular queue connects the last position back to the first. This structure allows us to reuse space efficiently.

We must implement the MyCircularQueue class to support initialization with size k, adding elements (enQueue), removing elements (deQueue), retrieving front/rear elements, and checking the queue's state (isEmpty, isFull). This is a popular interview question that tests your ability to manage pointers and array indices under specific constraints.

Brute Force Approach for Design Circular Queue

A naive approach to implementing a queue often involves using a dynamic array (like a standard ArrayList or vector).

In this brute force method:

1. Enqueue: Append the element to the end of the array.
2. Dequeue: Remove the element at index 0.
3. Maintenance: When an element is removed from index 0, all subsequent elements must be shifted left by one position to fill the gap.

Pseudo-code:

function enQueue(value):
    if size == k: return False
    array.append(value)
    return True

function deQueue():
    if size == 0: return False
    array.remove_at_index(0) // Requires shifting
    return True

Why it fails: While functionally correct as a FIFO structure, this approach fails the efficiency requirements of a circular queue. The deQueue operation becomes O(N) because removing the first element requires shifting all remaining $N-1$ elements. Additionally, if we implemented it using a fixed array and just moved a head pointer forward without wrapping around, we would eventually run out of array bounds even if the queue effectively had space, failing the "circular" requirement.

Algorithm Strategy: Design Patterns

We will design the class using a fixed-size array and integer variables to track the state.

1. Initialization:

   • Create an array of size k.
   • Initialize head to 0.
   • Initialize count (current size) to 0.
   • Store capacity as k.

2. enQueue(value):

   • First, check if the queue is full (count == capacity). If so, return False.
   • Calculate the insertion index. The tail position is conceptually (head + count) % capacity.
   • Store value at this calculated index.
   • Increment count.
   • Return True.

3. deQueue():

   • Check if the queue is empty (count == 0). If so, return False.
   • Move the head pointer forward circularly: head = (head + 1) % capacity.
   • Decrement count.
   • Return True.

4. Front() / Rear():

   • If empty, return -1.
   • Front returns data[head].
   • Rear returns data[(head + count - 1) % capacity]. Note the -1 because head + count points to the next available slot, so the actual last element is one slot before that.

5. isEmpty() / isFull():

   • isEmpty: Return count == 0.
   • isFull: Return count == capacity.

Execution Flow

Let's trace the algorithm with k = 3.

1. Initialize: data = [_, _, _], head = 0, count = 0, k = 3.
2. enQueue(1):
   • Not full.
   • Tail index = (0 + 0) % 3 = 0.
   • data[0] = 1. Array: [1, _, _].
   • count becomes 1.
3. enQueue(2):
   • Not full.
   • Tail index = (0 + 1) % 3 = 1.
   • data[1] = 2. Array: [1, 2, _].
   • count becomes 2.
4. enQueue(3):
   • Not full.
   • Tail index = (0 + 2) % 3 = 2.
   • data[2] = 3. Array: [1, 2, 3].
   • count becomes 3.
5. enQueue(4):
   • Check full: count == 3 (True). Return False.
6. deQueue():
   • Not empty.
   • head moves: (0 + 1) % 3 = 1.
   • count becomes 2.
   • Logically, the queue is now 2, 3 (stored at indices 1 and 2). Index 0 is considered "free" space.
7. enQueue(4):
   • Not full (count is 2).
   • Tail index = (1 + 2) % 3 = 0. (Wraps around!).
   • data[0] = 4. Array: [4, 2, 3].
   • count becomes 3.

Proof of Correctness

The correctness relies on the invariant that the active elements of the queue are always located in the range [head, head + count - 1] (modulo capacity).

• Safety: The count variable strictly prevents Buffer Overflow (writing beyond capacity) and Buffer Underflow (reading from empty).
• Circularity: The modulo operator % capacity ensures that any index calculation maps strictly to the valid range [0, k-1].
• FIFO: New elements are always added at the calculated tail, and removed from the head, preserving the First-In-First-Out order.

Pattern Reuse Notes

The Design pattern and the concept of managing state constraints apply to several other popular interview questions:

• LeetCode 146: LRU Cache - Requires designing a data structure that combines a Hash Map and a Doubly Linked List to manage capacity and access order.
• LeetCode 155: Min Stack - Requires modifying a standard stack design to retrieve the minimum element in O(1) time.
• LeetCode 225: Implement Stack using Queues - Manipulates standard queues to mimic LIFO behavior.
• LeetCode 232: Implement Queue using Stacks - Manipulates standard stacks to mimic FIFO behavior.

These problems all share the requirement of wrapping logic around primitive structures to satisfy specific API contracts.

Reference Implementation

C++ Solution for LeetCode 622

1class MyCircularQueue {
2private:
3    vector<int> data;
4    int head;
5    int count;
6    int capacity;
7
8public:
9    MyCircularQueue(int k) {
10        capacity = k;
11        data.resize(k);
12        head = 0;
13        count = 0;
14    }
15    
16    bool enQueue(int value) {
17        if (isFull()) return false;
18        // Calculate the position for the new element
19        // The tail is (head + count) % capacity
20        int tail = (head + count) % capacity;
21        data[tail] = value;
22        count++;
23        return true;
24    }
25    
26    bool deQueue() {
27        if (isEmpty()) return false;
28        // Move head forward circularly
29        head = (head + 1) % capacity;
30        count--;
31        return true;
32    }
33    
34    int Front() {
35        if (isEmpty()) return -1;
36        return data[head];
37    }
38    
39    int Rear() {
40        if (isEmpty()) return -1;
41        // The last element is at (head + count - 1) % capacity
42        // We add capacity before modulo to handle potential negative result logic 
43        // though strictly head + count - 1 >= 0 here if not empty.
44        int tail = (head + count - 1) % capacity;
45        return data[tail];
46    }
47    
48    bool isEmpty() {
49        return count == 0;
50    }
51    
52    bool isFull() {
53        return count == capacity;
54    }
55};

Java Solution for LeetCode 622

1class MyCircularQueue {
2    private int[] data;
3    private int head;
4    private int count;
5    private int capacity;
6
7    public MyCircularQueue(int k) {
8        this.capacity = k;
9        this.data = new int[k];
10        this.head = 0;
11        this.count = 0;
12    }
13    
14    public boolean enQueue(int value) {
15        if (isFull()) {
16            return false;
17        }
18        // Calculate the index for the new element
19        int tail = (head + count) % capacity;
20        data[tail] = value;
21        count++;
22        return true;
23    }
24    
25    public boolean deQueue() {
26        if (isEmpty()) {
27            return false;
28        }
29        // Move head pointer forward, wrapping around if necessary
30        head = (head + 1) % capacity;
31        count--;
32        return true;
33    }
34    
35    public int Front() {
36        if (isEmpty()) {
37            return -1;
38        }
39        return data[head];
40    }
41    
42    public int Rear() {
43        if (isEmpty()) {
44            return -1;
45        }
46        // Calculate the index of the last element added
47        int tail = (head + count - 1) % capacity;
48        return data[tail];
49    }
50    
51    public boolean isEmpty() {
52        return count == 0;
53    }
54    
55    public boolean isFull() {
56        return count == capacity;
57    }
58}

Python Solution for LeetCode 622

1class MyCircularQueue:
2
3    def __init__(self, k: int):
4        self.capacity = k
5        self.data = [0] * k
6        self.head = 0
7        self.count = 0
8
9    def enQueue(self, value: int) -> bool:
10        if self.isFull():
11            return False
12        
13        # Calculate insert position
14        tail = (self.head + self.count) % self.capacity
15        self.data[tail] = value
16        self.count += 1
17        return True
18
19    def deQueue(self) -> bool:
20        if self.isEmpty():
21            return False
22        
23        # Move head forward
24        self.head = (self.head + 1) % self.capacity
25        self.count -= 1
26        return True
27
28    def Front(self) -> int:
29        if self.isEmpty():
30            return -1
31        return self.data[self.head]
32
33    def Rear(self) -> int:
34        if self.isEmpty():
35            return -1
36        # Calculate last element position
37        tail = (self.head + self.count - 1) % self.capacity
38        return self.data[tail]
39
40    def isEmpty(self) -> bool:
41        return self.count == 0
42
43    def isFull(self) -> bool:
44        return self.count == self.capacity