Design Circular Queue

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Circular Queue

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.

Medium

Approach 1

Level I: Array with Front/Rear Pointers

Intuition

Use a fixed-size array and two pointers, head and tail. Use modulo arithmetic to wrap around the array. We use a size variable to easily distinguish between empty and full states.

⏱ O(1) for all ops.💾 O(N).

Detailed Dry Run

Enqueue(1), Enqueue(2), Dequeue()...

Op	Array	Head	Tail	Size
`init(3)`	`[0,0,0]`	0	-1	0
`enq(1)`	`[1,0,0]`	0	0	1
`enq(2)`	`[1,2,0]`	0	1	2
`deq()`	`[1,2,0]`	1	1	1

java

class MyCircularQueue {
    private int[] q; private int head, tail, size, k;
    public MyCircularQueue(int k) { this.k = k; q = new int[k]; head = 0; tail = -1; size = 0; }
    public boolean enQueue(int val) {
        if (isFull()) return false;
        tail = (tail + 1) % k; q[tail] = val; size++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % k; size--; return true;
    }
    public int Front() { return isEmpty() ? -1 : q[head]; }
    public int Rear() { return isEmpty() ? -1 : q[tail]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == k; }
}

Approach 2

Level II: Linked List Implementation

Intuition

Instead of an array, use a Doubly Linked List. This avoids modulo arithmetic but uses more memory for pointers. To make it 'circular' in memory, we can limit the number of nodes to k.

⏱ O(1) all ops.💾 O(k) where k is max size.

Detailed Dry Run

Head -> [1] <-> [2] <-> [3] <- Tail Enqueue(4) if size < k: Add new node after tail, move tail.

java

class MyCircularQueue {
    class Node { int val; Node next; Node(int v) { val = v; } }
    Node head, tail; int count, capacity;
    public MyCircularQueue(int k) { capacity = k; }
    public boolean enQueue(int value) {
        if (isFull()) return false;
        Node newNode = new Node(value);
        if (isEmpty()) head = tail = newNode;
        else { tail.next = newNode; tail = newNode; }
        count++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = head.next; count--; return true;
    }
    public int Front() { return isEmpty() ? -1 : head.val; }
    public int Rear() { return isEmpty() ? -1 : tail.val; }
    public boolean isEmpty() { return count == 0; }
    public boolean isFull() { return count == capacity; }
}

← Previous QuestionDesign Hit Counter

Next Question →Min Stack

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.