Design Circular Queue

🎯

Design Circular Queue

mediumSTACKAmazonGoogleMicrosoft

Imagine a ticketing system at a busy amusement park where visitors form a line that loops back to the start when full, ensuring no space is wasted.

💡 This problem involves designing a queue data structure that uses a fixed-size array in a circular manner. Beginners often struggle with managing the wrap-around logic and distinguishing between full and empty states without wasting space. Think of it like a circular track where runners keep moving forward and wrap around to the start when they reach the end.

📋

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 supports the following operations: MyCircularQueue(k): Constructor, set the size of the queue to be k. Front: Get the front item from the queue. Rear: Get the last item from the queue. enQueue(value): Insert an element into the circular queue. Return true if the operation is successful. deQueue(): Delete an element from the circular queue. Return true if the operation is successful. isEmpty(): Checks whether the circular queue is empty or not. isFull(): Checks whether the circular queue is full or not.

1 ≤ k ≤ 10^50 ≤ value ≤ 1000At most 10^5 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

💡

Example

Input"MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3\ncircularQueue.enQueue(1); // return true\ncircularQueue.enQueue(2); // return true\ncircularQueue.enQueue(3); // return true\ncircularQueue.enQueue(4); // return false, the queue is full\ncircularQueue.Rear(); // return 3\ncircularQueue.isFull(); // return true\ncircularQueue.deQueue(); // return true\ncircularQueue.enQueue(4); // return true\ncircularQueue.Rear(); // return 4"

Output[true, true, true, false, 3, true, true, true, 4]

We create a circular queue of size 3. We enqueue 1, 2, 3 successfully. The fourth enqueue fails because the queue is full. Rear returns 3. isFull returns true. We dequeue one element (1). Then enqueue 4 successfully. Rear now returns 4.

• Enqueue on full queue → should return false
• Dequeue on empty queue → should return false
• Front and Rear on empty queue → should return -1
• Single element enqueue and dequeue → queue should become empty

⚠️

Common Mistakes

Confusing full and empty states when head == tail

Queue appears always full or always empty, causing incorrect enQueue/deQueue results

✅ Use a size variable or reserve one slot to distinguish full vs empty

Not using modulo operation for pointer wrap-around

Pointers go out of array bounds causing runtime errors or incorrect behavior

✅ Always use modulo capacity when incrementing head or tail

Shifting elements on dequeue in array-based implementation

Leads to O(n) dequeue time causing TLE on large inputs

✅ Use head and tail pointers instead of shifting

Returning wrong values for Front or Rear when queue is empty

Returns garbage or causes exceptions

✅ Check if queue is empty and return -1 accordingly

Incorrectly updating head and tail pointers after enqueue or dequeue

Queue state becomes inconsistent, leading to lost or duplicated elements

✅ Carefully update pointers with modulo arithmetic and size adjustments

🧠

Brute Force (Using Dynamic Array with Shifting)

💡 This approach uses a simple dynamic array and shifts elements on dequeue to simulate queue behavior. It is intuitive but inefficient, helping beginners understand the basic queue operations before optimizing. Think of it as a line of people where removing the first person causes everyone else to move forward one step.

Intuition

Use a list to store elements. Enqueue appends to the end. Dequeue removes from the front by shifting all elements left by one.

Algorithm

1. Initialize an empty list to store queue elements.
2. For enQueue, append the element if size limit not reached.
3. For deQueue, remove the first element by shifting all others left.
4. For Front and Rear, return the first and last elements respectively, or -1 if empty.

💡 The main difficulty is realizing that shifting elements on dequeue is costly and leads to poor performance.

</>

Code

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = []
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if len(self.queue) == self.capacity:
            return False
        self.queue.append(value)
        return True

    def deQueue(self) -> bool:
        if not self.queue:
            return False
        self.queue.pop(0)  # shifting elements
        return True

    def Front(self) -> int:
        if not self.queue:
            return -1
        return self.queue[0]

    def Rear(self) -> int:
        if not self.queue:
            return -1
        return self.queue[-1]

    def isEmpty(self) -> bool:
        return len(self.queue) == 0

    def isFull(self) -> bool:
        return len(self.queue) == self.capacity

# Driver code
if __name__ == '__main__':
    cq = MyCircularQueue(3)
    print(cq.enQueue(1))  # True
    print(cq.enQueue(2))  # True
    print(cq.enQueue(3))  # True
    print(cq.enQueue(4))  # False
    print(cq.Rear())      # 3
    print(cq.isFull())    # True
    print(cq.deQueue())   # True
    print(cq.enQueue(4))  # True
    print(cq.Rear())      # 4

Line Notes

self.queue = []Initialize an empty list to hold queue elements for dynamic storage

if len(self.queue) == self.capacity:Check if queue is full before enqueue to prevent overflow

self.queue.append(value)Add new element at the end of the list to maintain FIFO order

self.queue.pop(0)Remove first element, shifting all others left which is costly

if not self.queue:Check if queue is empty before accessing elements to avoid errors

return len(self.queue) == 0Check if queue is empty by verifying list length

return len(self.queue) == self.capacityCheck if queue is full by comparing length to capacity

import java.util.*;

class MyCircularQueue {
    private List<Integer> queue;
    private int capacity;

    public MyCircularQueue(int k) {
        queue = new ArrayList<>();
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (queue.size() == capacity) return false;
        queue.add(value);
        return true;
    }

    public boolean deQueue() {
        if (queue.isEmpty()) return false;
        queue.remove(0); // shifting elements
        return true;
    }

    public int Front() {
        if (queue.isEmpty()) return -1;
        return queue.get(0);
    }

    public int Rear() {
        if (queue.isEmpty()) return -1;
        return queue.get(queue.size() - 1);
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public boolean isFull() {
        return queue.size() == capacity;
    }

    public static void main(String[] args) {
        MyCircularQueue cq = new MyCircularQueue(3);
        System.out.println(cq.enQueue(1)); // true
        System.out.println(cq.enQueue(2)); // true
        System.out.println(cq.enQueue(3)); // true
        System.out.println(cq.enQueue(4)); // false
        System.out.println(cq.Rear());     // 3
        System.out.println(cq.isFull());   // true
        System.out.println(cq.deQueue());  // true
        System.out.println(cq.enQueue(4)); // true
        System.out.println(cq.Rear());     // 4
    }
}

Line Notes

queue = new ArrayList<>()Initialize dynamic array to hold queue elements

if (queue.size() == capacity) return false;Check if queue is full before enqueue to avoid overflow

queue.add(value)Add element at the end to maintain FIFO order

queue.remove(0)Remove first element, shifting all others left which is inefficient

if (queue.isEmpty())Check if queue is empty before accessing elements

return queue.isEmpty()Check if queue is empty by verifying list size

return queue.size() == capacityCheck if queue is full by comparing size to capacity

#include <iostream>
#include <vector>
using namespace std;

class MyCircularQueue {
    vector<int> queue;
    int capacity;
public:
    MyCircularQueue(int k) {
        capacity = k;
    }

    bool enQueue(int value) {
        if ((int)queue.size() == capacity) return false;
        queue.push_back(value);
        return true;
    }

    bool deQueue() {
        if (queue.empty()) return false;
        queue.erase(queue.begin()); // shifting elements
        return true;
    }

    int Front() {
        if (queue.empty()) return -1;
        return queue.front();
    }

    int Rear() {
        if (queue.empty()) return -1;
        return queue.back();
    }

    bool isEmpty() {
        return queue.empty();
    }

    bool isFull() {
        return (int)queue.size() == capacity;
    }
};

int main() {
    MyCircularQueue cq(3);
    cout << boolalpha;
    cout << cq.enQueue(1) << endl; // true
    cout << cq.enQueue(2) << endl; // true
    cout << cq.enQueue(3) << endl; // true
    cout << cq.enQueue(4) << endl; // false
    cout << cq.Rear() << endl;     // 3
    cout << cq.isFull() << endl;   // true
    cout << cq.deQueue() << endl;  // true
    cout << cq.enQueue(4) << endl; // true
    cout << cq.Rear() << endl;     // 4
    return 0;
}

Line Notes

vector<int> queue;Use vector to store queue elements dynamically

if ((int)queue.size() == capacity) return false;Check if queue is full before enqueue to prevent overflow

queue.push_back(value);Add element at the end to maintain FIFO order

queue.erase(queue.begin());Remove first element, shifting all others left which is costly

if (queue.empty())Check if queue is empty before accessing elements

return queue.empty();Check if queue is empty by verifying vector size

return (int)queue.size() == capacity;Check if queue is full by comparing size to capacity

class MyCircularQueue {
    constructor(k) {
        this.queue = [];
        this.capacity = k;
    }

    enQueue(value) {
        if (this.queue.length === this.capacity) return false;
        this.queue.push(value);
        return true;
    }

    deQueue() {
        if (this.queue.length === 0) return false;
        this.queue.shift(); // shifting elements
        return true;
    }

    Front() {
        if (this.queue.length === 0) return -1;
        return this.queue[0];
    }

    Rear() {
        if (this.queue.length === 0) return -1;
        return this.queue[this.queue.length - 1];
    }

    isEmpty() {
        return this.queue.length === 0;
    }

    isFull() {
        return this.queue.length === this.capacity;
    }
}

// Driver code
const cq = new MyCircularQueue(3);
console.log(cq.enQueue(1)); // true
console.log(cq.enQueue(2)); // true
console.log(cq.enQueue(3)); // true
console.log(cq.enQueue(4)); // false
console.log(cq.Rear());     // 3
console.log(cq.isFull());   // true
console.log(cq.deQueue());  // true
console.log(cq.enQueue(4)); // true
console.log(cq.Rear());     // 4

Line Notes

this.queue = []Initialize empty array to hold queue elements dynamically

if (this.queue.length === this.capacity) return false;Check if queue is full before enqueue to avoid overflow

this.queue.push(value)Add element at the end to maintain FIFO order

this.queue.shift()Remove first element, shifting all others left which is inefficient

if (this.queue.length === 0)Check if queue is empty before accessing elements

return this.queue.length === 0Check if queue is empty by verifying array length

return this.queue.length === this.capacityCheck if queue is full by comparing length to capacity

⏱

Complexity

TimeO(n) per deQueue due to shifting elements

SpaceO(k) for storing up to k elements

Each deQueue operation shifts all elements left, causing O(n) time per dequeue. Enqueue is O(1).

💡 For n=1000 dequeues, this approach could do up to 1,000,000 operations, which is inefficient and not suitable for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand queue basics before optimizing.

🧠

Better Approach (Using Fixed-Size Array with Head and Tail Pointers)

💡 This approach uses a fixed-size array and two pointers (head and tail) to track the front and rear positions, avoiding costly shifts and enabling O(1) operations. It models the queue as a circular buffer where pointers wrap around.

Intuition

Use a fixed-size array as a ring buffer. Maintain head and tail indices that wrap around using modulo arithmetic to simulate circular behavior.

Algorithm

1. Initialize an array of size k, head and tail pointers to -1.
2. For enQueue, if queue is not full, move tail forward modulo k and insert value.
3. For deQueue, if queue is not empty, move head forward modulo k.
4. Front and Rear return elements at head and tail respectively, or -1 if empty.
5. isEmpty checks if head == -1, isFull checks if next tail equals head.

💡 The tricky part is correctly updating head and tail pointers and handling empty/full states.

</>

Code

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = [0] * k
        self.head = -1
        self.tail = -1
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty():
            self.head = 0
        self.tail = (self.tail + 1) % self.capacity
        self.queue[self.tail] = value
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
            return True
        self.head = (self.head + 1) % self.capacity
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.tail]

    def isEmpty(self) -> bool:
        return self.head == -1

    def isFull(self) -> bool:
        return (self.tail + 1) % self.capacity == self.head

# Driver code
if __name__ == '__main__':
    cq = MyCircularQueue(3)
    print(cq.enQueue(1))  # True
    print(cq.enQueue(2))  # True
    print(cq.enQueue(3))  # True
    print(cq.enQueue(4))  # False
    print(cq.Rear())      # 3
    print(cq.isFull())    # True
    print(cq.deQueue())   # True
    print(cq.enQueue(4))  # True
    print(cq.Rear())      # 4

Line Notes

self.queue = [0] * kPre-allocate fixed size array for queue elements to avoid resizing

self.head = -1Reset head to -1 when queue becomes empty

self.tail = -1Reset tail to -1 when queue becomes empty

if self.isFull()Check if queue is full before enqueue to prevent overflow

if self.isEmpty()If queue is empty, set head to 0 to start

self.tail = (self.tail + 1) % self.capacityMove tail pointer forward circularly using modulo

self.queue[self.tail] = valueInsert element at tail position

if self.head == self.tailCheck if queue has only one element before dequeue

self.head = (self.head + 1) % self.capacityMove head pointer forward circularly on dequeue

return self.head == -1Check if queue is empty by head pointer

return (self.tail + 1) % self.capacity == self.headCheck if queue is full by comparing next tail to head

class MyCircularQueue {
    private int[] queue;
    private int head;
    private int tail;
    private int capacity;

    public MyCircularQueue(int k) {
        queue = new int[k];
        head = -1;
        tail = -1;
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) head = 0;
        tail = (tail + 1) % capacity;
        queue[tail] = value;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % capacity;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return queue[head];
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return queue[tail];
    }

    public boolean isEmpty() {
        return head == -1;
    }

    public boolean isFull() {
        return (tail + 1) % capacity == head;
    }

    public static void main(String[] args) {
        MyCircularQueue cq = new MyCircularQueue(3);
        System.out.println(cq.enQueue(1)); // true
        System.out.println(cq.enQueue(2)); // true
        System.out.println(cq.enQueue(3)); // true
        System.out.println(cq.enQueue(4)); // false
        System.out.println(cq.Rear());     // 3
        System.out.println(cq.isFull());   // true
        System.out.println(cq.deQueue());  // true
        System.out.println(cq.enQueue(4)); // true
        System.out.println(cq.Rear());     // 4
    }
}

Line Notes

queue = new int[k];Allocate fixed size array for queue elements

head = -1;Reset head to -1 when queue becomes empty

tail = -1;Reset tail to -1 when queue becomes empty

if (isFull()) return false;Check if queue is full before enqueue to avoid overflow

if (isEmpty()) head = 0;If queue is empty, set head to 0 to start

tail = (tail + 1) % capacity;Move tail pointer forward circularly using modulo

queue[tail] = value;Insert element at tail index

if (head == tail)Check if queue has only one element before dequeue

head = (head + 1) % capacity;Move head pointer forward circularly on dequeue

return head == -1;Check if queue is empty by head pointer

return (tail + 1) % capacity == head;Check if queue is full by comparing next tail to head

#include <iostream>
using namespace std;

class MyCircularQueue {
    int* queue;
    int head;
    int tail;
    int capacity;
public:
    MyCircularQueue(int k) {
        queue = new int[k];
        capacity = k;
        head = -1;
        tail = -1;
    }

    bool enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) head = 0;
        tail = (tail + 1) % capacity;
        queue[tail] = value;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % capacity;
        return true;
    }

    int Front() {
        if (isEmpty()) return -1;
        return queue[head];
    }

    int Rear() {
        if (isEmpty()) return -1;
        return queue[tail];
    }

    bool isEmpty() {
        return head == -1;
    }

    bool isFull() {
        return (tail + 1) % capacity == head;
    }

    ~MyCircularQueue() {
        delete[] queue;
    }
};

int main() {
    MyCircularQueue cq(3);
    cout << boolalpha;
    cout << cq.enQueue(1) << endl; // true
    cout << cq.enQueue(2) << endl; // true
    cout << cq.enQueue(3) << endl; // true
    cout << cq.enQueue(4) << endl; // false
    cout << cq.Rear() << endl;     // 3
    cout << cq.isFull() << endl;   // true
    cout << cq.deQueue() << endl;  // true
    cout << cq.enQueue(4) << endl; // true
    cout << cq.Rear() << endl;     // 4
    return 0;
}

Line Notes

queue = new int[k];Allocate fixed size array for queue elements

head = -1;Reset head to -1 when queue becomes empty

tail = -1;Reset tail to -1 when queue becomes empty

if (isFull()) return false;Check if queue is full before enqueue to avoid overflow

if (isEmpty()) head = 0;If queue is empty, set head to 0 to start

tail = (tail + 1) % capacity;Move tail pointer forward circularly using modulo

queue[tail] = value;Insert element at tail index

if (head == tail)Check if queue has only one element before dequeue

head = (head + 1) % capacity;Move head pointer forward circularly on dequeue

return head == -1;Check if queue is empty by head pointer

return (tail + 1) % capacity == head;Check if queue is full by comparing next tail to head

class MyCircularQueue {
    constructor(k) {
        this.queue = new Array(k);
        this.head = -1;
        this.tail = -1;
        this.capacity = k;
    }

    enQueue(value) {
        if (this.isFull()) return false;
        if (this.isEmpty()) this.head = 0;
        this.tail = (this.tail + 1) % this.capacity;
        this.queue[this.tail] = value;
        return true;
    }

    deQueue() {
        if (this.isEmpty()) return false;
        if (this.head === this.tail) {
            this.head = -1;
            this.tail = -1;
            return true;
        }
        this.head = (this.head + 1) % this.capacity;
        return true;
    }

    Front() {
        if (this.isEmpty()) return -1;
        return this.queue[this.head];
    }

    Rear() {
        if (this.isEmpty()) return -1;
        return this.queue[this.tail];
    }

    isEmpty() {
        return this.head === -1;
    }

    isFull() {
        return (this.tail + 1) % this.capacity === this.head;
    }
}

// Driver code
const cq = new MyCircularQueue(3);
console.log(cq.enQueue(1)); // true
console.log(cq.enQueue(2)); // true
console.log(cq.enQueue(3)); // true
console.log(cq.enQueue(4)); // false
console.log(cq.Rear());     // 3
console.log(cq.isFull());   // true
console.log(cq.deQueue());  // true
console.log(cq.enQueue(4)); // true
console.log(cq.Rear());     // 4

Line Notes

this.queue = new Array(k);Pre-allocate fixed size array for queue elements

this.head = -1;Reset head to -1 when queue becomes empty

this.tail = -1;Reset tail to -1 when queue becomes empty

if (this.isFull()) return false;Check if queue is full before enqueue to avoid overflow

if (this.isEmpty()) this.head = 0;If queue is empty, set head to 0 to start

this.tail = (this.tail + 1) % this.capacity;Move tail pointer forward circularly using modulo

this.queue[this.tail] = value;Insert element at tail index

if (this.head === this.tail)Check if queue has only one element before dequeue

this.head = (this.head + 1) % this.capacity;Move head pointer forward circularly on dequeue

return this.head === -1;Check if queue is empty by head pointer

return (this.tail + 1) % this.capacity === this.head;Check if queue is full by comparing next tail to head

⏱

Complexity

TimeO(1) for all operations

SpaceO(k) for fixed size array

All operations use constant time pointer arithmetic and array access without shifting.

💡 For n=100000 operations, this approach performs efficiently with constant time per operation.

Interview Verdict: Accepted / Optimal for interview coding

This is the standard approach expected in interviews for designing circular queues.

🧠

Optimal Approach (Using Size Variable to Distinguish Full/Empty)

💡 This approach improves clarity by maintaining a size variable instead of using head == -1 to track empty state, simplifying full/empty checks and reducing edge case complexity. It is easier to reason about and less error-prone.

Intuition

Track the number of elements in the queue explicitly. Use head and tail pointers with modulo arithmetic. The queue is empty if size is 0, full if size equals capacity.

Algorithm

1. Initialize array, head and tail pointers to 0, and size to 0.
2. For enQueue, if size < capacity, insert at tail, move tail forward modulo capacity, increment size.
3. For deQueue, if size > 0, move head forward modulo capacity, decrement size.
4. Front and Rear return elements at head and (tail - 1 + capacity) % capacity respectively, or -1 if empty.
5. isEmpty checks if size == 0, isFull checks if size == capacity.

💡 Using size removes ambiguity in empty/full states and makes code easier to reason about.

</>

Code

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = [0] * k
        self.head = 0
        self.tail = 0
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.queue[self.tail] = value
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[(self.tail - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

# Driver code
if __name__ == '__main__':
    cq = MyCircularQueue(3)
    print(cq.enQueue(1))  # True
    print(cq.enQueue(2))  # True
    print(cq.enQueue(3))  # True
    print(cq.enQueue(4))  # False
    print(cq.Rear())      # 3
    print(cq.isFull())    # True
    print(cq.deQueue())   # True
    print(cq.enQueue(4))  # True
    print(cq.Rear())      # 4

Line Notes

self.queue = [0] * kPre-allocate fixed size array for queue elements

self.head = 0Initialize head pointer at start of array

self.tail = 0Initialize tail pointer at start of array

self.size = 0Track current number of elements in queue

if self.isFull()Check if queue is full before enqueue to prevent overflow

self.queue[self.tail] = valueInsert element at tail position

self.tail = (self.tail + 1) % self.capacityMove tail pointer forward circularly using modulo

self.size += 1Increment size after enqueue

if self.isEmpty()Check if queue is empty before dequeue

self.head = (self.head + 1) % self.capacityMove head pointer forward circularly on dequeue

self.size -= 1Decrement size after dequeue

return self.size == 0Check if queue is empty by size

return self.size == self.capacityCheck if queue is full by size

class MyCircularQueue {
    private int[] queue;
    private int head;
    private int tail;
    private int size;
    private int capacity;

    public MyCircularQueue(int k) {
        queue = new int[k];
        head = 0;
        tail = 0;
        size = 0;
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        queue[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return queue[head];
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return queue[(tail - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public static void main(String[] args) {
        MyCircularQueue cq = new MyCircularQueue(3);
        System.out.println(cq.enQueue(1)); // true
        System.out.println(cq.enQueue(2)); // true
        System.out.println(cq.enQueue(3)); // true
        System.out.println(cq.enQueue(4)); // false
        System.out.println(cq.Rear());     // 3
        System.out.println(cq.isFull());   // true
        System.out.println(cq.deQueue());  // true
        System.out.println(cq.enQueue(4)); // true
        System.out.println(cq.Rear());     // 4
    }
}

Line Notes

queue = new int[k];Allocate fixed size array for queue elements

head = 0;Initialize head pointer at start

tail = 0;Initialize tail pointer at start

size = 0;Track number of elements in queue

if (isFull()) return false;Check if queue is full before enqueue to avoid overflow

queue[tail] = value;Insert element at tail index

tail = (tail + 1) % capacity;Advance tail pointer circularly using modulo

size++;Increment size after enqueue

if (isEmpty())Check if queue is empty before dequeue

head = (head + 1) % capacity;Advance head pointer circularly on dequeue

size--;Decrement size after dequeue

return size == 0;Check if queue is empty by size

return size == capacity;Check if queue is full by size

#include <iostream>
using namespace std;

class MyCircularQueue {
    int* queue;
    int head;
    int tail;
    int size;
    int capacity;
public:
    MyCircularQueue(int k) {
        queue = new int[k];
        capacity = k;
        head = 0;
        tail = 0;
        size = 0;
    }

    bool enQueue(int value) {
        if (isFull()) return false;
        queue[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    int Front() {
        if (isEmpty()) return -1;
        return queue[head];
    }

    int Rear() {
        if (isEmpty()) return -1;
        return queue[(tail - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

    ~MyCircularQueue() {
        delete[] queue;
    }
};

int main() {
    MyCircularQueue cq(3);
    cout << boolalpha;
    cout << cq.enQueue(1) << endl; // true
    cout << cq.enQueue(2) << endl; // true
    cout << cq.enQueue(3) << endl; // true
    cout << cq.enQueue(4) << endl; // false
    cout << cq.Rear() << endl;     // 3
    cout << cq.isFull() << endl;   // true
    cout << cq.deQueue() << endl;  // true
    cout << cq.enQueue(4) << endl; // true
    cout << cq.Rear() << endl;     // 4
    return 0;
}

Line Notes

queue = new int[k];Allocate fixed size array for queue elements

head = 0;Initialize head pointer at start

tail = 0;Initialize tail pointer at start

size = 0;Track current number of elements

if (isFull()) return false;Check if queue is full before enqueue to avoid overflow

queue[tail] = value;Insert element at tail index

tail = (tail + 1) % capacity;Advance tail pointer circularly using modulo

size++;Increment size after enqueue

if (isEmpty())Check if queue is empty before dequeue

head = (head + 1) % capacity;Advance head pointer circularly on dequeue

size--;Decrement size after dequeue

return size == 0;Check if queue is empty by size

return size == capacity;Check if queue is full by size

class MyCircularQueue {
    constructor(k) {
        this.queue = new Array(k);
        this.head = 0;
        this.tail = 0;
        this.size = 0;
        this.capacity = k;
    }

    enQueue(value) {
        if (this.isFull()) return false;
        this.queue[this.tail] = value;
        this.tail = (this.tail + 1) % this.capacity;
        this.size++;
        return true;
    }

    deQueue() {
        if (this.isEmpty()) return false;
        this.head = (this.head + 1) % this.capacity;
        this.size--;
        return true;
    }

    Front() {
        if (this.isEmpty()) return -1;
        return this.queue[this.head];
    }

    Rear() {
        if (this.isEmpty()) return -1;
        return this.queue[(this.tail - 1 + this.capacity) % this.capacity];
    }

    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return this.size === this.capacity;
    }
}

// Driver code
const cq = new MyCircularQueue(3);
console.log(cq.enQueue(1)); // true
console.log(cq.enQueue(2)); // true
console.log(cq.enQueue(3)); // true
console.log(cq.enQueue(4)); // false
console.log(cq.Rear());     // 3
console.log(cq.isFull());   // true
console.log(cq.deQueue());  // true
console.log(cq.enQueue(4)); // true
console.log(cq.Rear());     // 4

Line Notes

this.queue = new Array(k);Pre-allocate fixed size array for queue elements

this.head = 0;Initialize head pointer at start

this.tail = 0;Initialize tail pointer at start

this.size = 0;Track number of elements in queue

if (this.isFull()) return false;Check if queue is full before enqueue to avoid overflow

this.queue[this.tail] = value;Insert element at tail index

this.tail = (this.tail + 1) % this.capacity;Advance tail pointer circularly using modulo

this.size++;Increment size after enqueue

if (this.isEmpty())Check if queue is empty before dequeue

this.head = (this.head + 1) % this.capacity;Advance head pointer circularly on dequeue

this.size--;Decrement size after dequeue

return this.size === 0;Check if queue is empty by size

return this.size === this.capacity;Check if queue is full by size

⏱

Complexity

TimeO(1) for all operations

SpaceO(k) for fixed size array

All operations use constant time pointer arithmetic and array access without shifting.

💡 This approach is the clearest and easiest to maintain for large scale implementations.

Interview Verdict: Accepted / Preferred in production code

Maintaining size simplifies logic and reduces bugs, making this approach ideal for interviews and real systems.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the optimal approach with fixed-size array and size variable for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Dynamic Array with Shifting)	O(n) per dequeue	O(k)	No	N/A	Mention only - never code due to inefficiency
2. Fixed-Size Array with Head/Tail Pointers	O(1) per operation	O(k)	No	N/A	Good approach, but pointer logic can be tricky
3. Fixed-Size Array with Size Variable (Optimal)	O(1) per operation	O(k)	No	N/A	Best approach to implement and explain in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using a dynamic array with shifting.Step 3: Explain the fixed-size array with head and tail pointers approach.Step 4: Present the optimal approach using a size variable for clarity.Step 5: Code the optimal approach and test edge cases.Step 6: Discuss time and space complexity and possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of circular buffer logic, pointer arithmetic, handling edge cases, and writing clean, efficient code.

Common Follow-ups

• How would you implement a circular deque? → Use two pointers with insert/delete at both ends.
• How to handle dynamic resizing of the circular queue? → Allocate a larger array and copy elements in order.

💡 These follow-ups test your ability to extend the design and handle real-world scenarios beyond the basic queue.

🔍

Pattern Recognition

When to Use

1) Need a queue with fixed capacity, 2) Operations must be O(1), 3) Circular wrap-around is mentioned or implied, 4) Avoid shifting elements

Signature Phrases

circular queuefixed size bufferwrap around using modulo

NOT This Pattern When

Problems involving dynamic queues without fixed capacity or linked list implementations

Similar Problems

Design Circular Deque - extends circular queue with insert/delete at both endsImplement Queue using Stacks - different data structure but similar FIFO concept

Practice

1. Given the following code for the stock span problem, what is the return value of the third call to next with input prices [100, 80, 60]?

easy

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Trace the first two calls

   Call 1 with price=100: stack empty, span=1, stack=[0], prices=[100]. Call 2 with price=80: top price=100 > 80, no pop, span=2-0=1, stack=[0,1], prices=[100,80].

2. Step 2: Trace the third call with price=60

   Top price=80 > 60, no pop, span=3-1=1, stack=[0,1,2], prices=[100,80,60]. Return 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each price less than previous yields span 1 [OK]

Hint: Span resets to 1 when price is less than previous [OK]

Common Mistakes:

• Confusing index difference calculation
• Off-by-one errors in span computation

2. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly

3. Suppose the problem is modified so that the input string can contain not only '(' and ')' but also '*' characters, where '*' can represent either '(' or ')' or an empty string. Which approach is best suited to handle this variant efficiently?

hard

A. Use dynamic programming to track valid substring lengths considering '*' as wildcards.

B. Use the two-pass counter approach ignoring '*' characters.

C. Use brute force checking all substrings and validating with '*' replacements.

D. Use a stack-based approach tracking indices and possible '*' substitutions.

Solution

1. Step 1: Understand the complexity introduced by '*'

   The '*' character can represent multiple possibilities, requiring tracking multiple states.

2. Step 2: Evaluate approaches for handling wildcards

   Dynamic programming can efficiently track valid substring lengths considering '*' as '(', ')' or empty, unlike counters or naive stack approaches.

3. Step 3: Rule out brute force due to exponential possibilities

   Brute force checking all substrings with '*' replacements is infeasible for large inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles wildcard substitutions efficiently [OK]

Hint: DP handles wildcard '*' efficiently [OK]

Common Mistakes:

• Ignoring '*' in counters
• Assuming stack alone can handle wildcards
• Trying brute force for large inputs

4. Suppose the input array can contain negative numbers and duplicates, and you want to find the previous smaller element for each position. Which modification to the monotonic stack algorithm is necessary to handle duplicates correctly and maintain O(n) time?

hard

A. Change the popping condition to pop elements strictly greater than current (arr[stack[-1]] > num)

B. Store values instead of indexes in the stack to simplify comparisons

C. Use a balanced binary search tree instead of a stack to handle duplicates

D. Change the popping condition to pop elements greater than or equal to current (arr[stack[-1]] >= num)

Solution

1. Step 1: Understand the role of popping condition

   To correctly handle duplicates, the stack must pop elements that are greater than or equal to the current element to maintain strictly increasing order.

2. Step 2: Evaluate options for duplicates and negative numbers

   Using '>=' ensures duplicates are popped, preventing incorrect previous smaller elements; other options either break correctness or efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pop equal or greater elements to maintain correct monotonic stack with duplicates [OK]

Hint: Pop >= current to handle duplicates correctly [OK]

Common Mistakes:

• Using '>' only causes duplicates to remain on stack
• Replacing stack with BST increases complexity unnecessarily
• Pushing values instead of indexes loses position info

5. Suppose the sliding window maximum problem is modified so that the window size k can vary dynamically during the iteration. Which of the following approaches correctly adapts the monotonic deque solution to handle this efficiently?

hard

A. Adjust the window boundary checks and remove indices outside the current window size dynamically without rebuilding the deque

B. Rebuild the deque from scratch each time the window size changes

C. Switch to a max heap data structure since deque cannot handle variable window sizes

D. Use a brute force approach for variable window sizes to avoid complexity

Solution

1. Step 1: Understand dynamic window size impact

   Window boundaries change, so indices outside the current window must be removed accordingly.

2. Step 2: Adapt monotonic deque maintenance

   Instead of rebuilding, update boundary checks and pop indices outside the new window size dynamically.

3. Step 3: Evaluate alternatives

   Rebuilding deque or switching to heap is inefficient; brute force is too slow.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dynamic boundary checks maintain O(n) amortized complexity [OK]

Hint: Update boundary removals dynamically, avoid rebuilding [OK]

Common Mistakes:

• Rebuilding deque wastes time
• Assuming heap is better for variable k