118. Design Circular Queue

🔗 LeetCode Problem: 622. Design Circular Queue
📊 Difficulty: Medium
🏷️ Topics: Array, Queue, Design

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.

Implement the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
• boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• int Front() Gets the front item from the queue. If the queue is empty, return -1.
• int Rear() Gets the last item from the queue. If the queue is empty, return -1.
• boolean isEmpty() Checks whether the circular queue is empty or not.
• boolean isFull() Checks whether the circular queue is full or not.

Example:

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]

Explanation:
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False (queue is full)
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints: - 1 <= k <= 1000 - 0 <= value <= 1000 - At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

---

🌟 Understanding the Problem

What is a Circular Queue?

Regular Queue (Linear):

Array: [_, _, _, _, _]
       0  1  2  3  4

enQueue(1) → [1, _, _, _, _]
enQueue(2) → [1, 2, _, _, _]
enQueue(3) → [1, 2, 3, _, _]

deQueue() removes 1 → [_, 2, 3, _, _]

Problem: Wasted space at index 0!
Can't reuse it in a regular queue.

Circular Queue (Wrap Around):

Imagine the array as a circle:

     [0]
  [4]   [1]
  [3]   [2]

After deQueue, we can wrap around:
  front moves → 0, 1, 2, 3, 4, 0, 1, ...
  rear moves  → 0, 1, 2, 3, 4, 0, 1, ...

When rear reaches end, it wraps to beginning!
This reuses space efficiently.

---

💡 Building Intuition

Question 1: Why Do We Need Circular Queue?

Regular Queue Problem:

Array size: 5
Operations: enQueue 5 times, deQueue 3 times, enQueue 3 times

After first 5 enQueues:
  [1, 2, 3, 4, 5]
   F           R

After 3 deQueues:
  [_, _, _, 4, 5]
         F     R

Try to enQueue(6):
  Problem! Rear is at end, but we have 3 empty spaces!
  Regular queue says "Full" even though we have space!

Circular Queue Solution:

Same scenario with circular queue:

After 3 deQueues:
  [_, _, _, 4, 5]
         F     R

enQueue(6): Rear wraps around to index 0!
  [6, _, _, 4, 5]
         F     R (wraps to 0)

enQueue(7):
  [6, 7, _, 4, 5]
         F        R (now at 1)

Reusing space! ✓

Question 2: How to Track Front and Rear?

We need TWO pointers:
  - front: Points to first element
  - rear: Points to last element (or next empty slot)

Key insight: Use modulo to wrap around!
  nextIndex = (currentIndex + 1) % size

Example with size 5:
  (0 + 1) % 5 = 1
  (1 + 1) % 5 = 2
  (2 + 1) % 5 = 3
  (3 + 1) % 5 = 4
  (4 + 1) % 5 = 0  ← Wraps around!

Question 3: How to Detect Full vs Empty?

Problem: Both can have front == rear!

Empty: front == rear (no elements)
  [_, _, _, _, _]
   F=R

Full: front == rear (after wraparound)
  [1, 2, 3, 4, 5]
   F=R (rear wrapped around)

How to distinguish?

Solution: Track count!
  count = 0 → empty
  count = size → full

---

🎯 Approach 1: Array with Shifting (Not Circular)

The Idea

Use regular array, shift elements on deQueue.
Not truly circular, but helps understand the problem.

Implementation

class MyCircularQueue {
    private int[] data;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        data = new int[k];
        count = 0;
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (count == capacity) return false;
        data[count++] = value;
        return true;
    }

    public boolean deQueue() {
        if (count == 0) return false;
        // Shift all elements left
        for (int i = 0; i < count - 1; i++) {
            data[i] = data[i + 1];
        }
        count--;
        return true;
    }

    public int Front() {
        return count == 0 ? -1 : data[0];
    }

    public int Rear() {
        return count == 0 ? -1 : data[count - 1];
    }

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

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

Complexity Analysis

⏰ Time: - enQueue(): O(1) - deQueue(): O(n) - Shift all elements - Others: O(1)

💾 Space: O(k)

The Problem

deQueue is O(n) - very slow!
Not truly circular - doesn't reuse space efficiently

---

✅ Approach 2: Circular Array with Two Pointers (Optimal)

The Idea

Use array as circular with front and rear pointers.
Use modulo for wraparound.
Track count to distinguish empty vs full.

Implementation

class MyCircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        data = new int[k];
        front = 0;
        rear = -1;  // Will be incremented on first enQueue
        count = 0;
        capacity = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;

        rear = (rear + 1) % capacity;
        data[rear] = value;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;

        front = (front + 1) % capacity;
        count--;
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : data[front];
    }

    public int Rear() {
        return isEmpty() ? -1 : data[rear];
    }

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

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

Complexity Analysis

⏰ Time: All operations O(1)

💾 Space: O(k)

Detailed Dry Run

═══════════════════════════════════════════════════════════
Operations: MyCircularQueue(3), enQueue(1), enQueue(2), 
            enQueue(3), enQueue(4), Rear(), isFull(), 
            deQueue(), enQueue(4), Rear()
═══════════════════════════════════════════════════════════

Initialization: MyCircularQueue(3)

  data = [_, _, _]  (size 3)
  front = 0
  rear = -1
  count = 0
  capacity = 3

═══════════════════════════════════════════════════════════
Operation: enQueue(1)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  isFull()? count == capacity?
  0 == 3? NO

Step 2: Update rear
  rear = (rear + 1) % capacity
  rear = (-1 + 1) % 3 = 0

Step 3: Insert value
  data[0] = 1

Step 4: Increment count
  count = 1

State:
  data = [1, _, _]
         F
         R
  front = 0, rear = 0, count = 1

Return: true ✓

═══════════════════════════════════════════════════════════
Operation: enQueue(2)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  1 == 3? NO

Step 2: Update rear
  rear = (0 + 1) % 3 = 1

Step 3: Insert value
  data[1] = 2

Step 4: Increment count
  count = 2

State:
  data = [1, 2, _]
         F  R
  front = 0, rear = 1, count = 2

Return: true ✓

═══════════════════════════════════════════════════════════
Operation: enQueue(3)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  2 == 3? NO

Step 2: Update rear
  rear = (1 + 1) % 3 = 2

Step 3: Insert value
  data[2] = 3

Step 4: Increment count
  count = 3

State:
  data = [1, 2, 3]
         F     R
  front = 0, rear = 2, count = 3

Return: true ✓

Queue is now FULL!

═══════════════════════════════════════════════════════════
Operation: enQueue(4)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  isFull()? count == capacity?
  3 == 3? YES

Return: false ✓

State unchanged:
  data = [1, 2, 3]
         F     R
  count = 3

═══════════════════════════════════════════════════════════
Operation: Rear()
═══════════════════════════════════════════════════════════

Check if empty: NO

Return: data[rear] = data[2] = 3 ✓

═══════════════════════════════════════════════════════════
Operation: isFull()
═══════════════════════════════════════════════════════════

Check: count == capacity?
  3 == 3? YES

Return: true ✓

═══════════════════════════════════════════════════════════
Operation: deQueue()
═══════════════════════════════════════════════════════════

Step 1: Check if empty
  isEmpty()? count == 0?
  3 == 0? NO

Step 2: Move front pointer
  front = (front + 1) % capacity
  front = (0 + 1) % 3 = 1

Step 3: Decrement count
  count = 2

State:
  data = [1, 2, 3]  (1 is still there but not accessible)
            F  R
  front = 1, rear = 2, count = 2

Return: true ✓

Explanation:
  We removed element 1 by moving front pointer
  The value 1 is still in array but "logically" removed
  Space at index 0 is now available for reuse

═══════════════════════════════════════════════════════════
Operation: enQueue(4)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  2 == 3? NO

Step 2: Update rear
  rear = (2 + 1) % 3
  rear = 3 % 3 = 0  ← WRAPAROUND!

Step 3: Insert value
  data[0] = 4  (Reusing space!)

Step 4: Increment count
  count = 3

State:
  data = [4, 2, 3]
         R  F
  front = 1, rear = 0, count = 3

Return: true ✓

Explanation:
  Rear wrapped around to index 0!
  We reused the space from deQueued element
  This is the CIRCULAR property!

Visual of circular nature:
     [0]=4
  [2]=3 [1]=2
     R   F

═══════════════════════════════════════════════════════════
Operation: Rear()
═══════════════════════════════════════════════════════════

Check if empty: NO

Return: data[rear] = data[0] = 4 ✓

Final state:
  data = [4, 2, 3]
         R  F
  Elements in queue order: 2, 3, 4
  Front element: 2 (at index 1)
  Rear element: 4 (at index 0)

---

📊 Approach Comparison

┌─────────────────────────────────────────────────────────┐
│               Approach 1         Approach 2             │
│               (Shifting)         (Circular)             │
├─────────────────────────────────────────────────────────┤
│ Strategy      Shift on deQueue  Two pointers + modulo  │
│                                                          │
│ enQueue()     O(1)               O(1) ✓                 │
│ deQueue()     O(n)               O(1) ✓                 │
│ Front/Rear    O(1)               O(1) ✓                 │
│                                                          │
│ Space         O(k)               O(k)                   │
│                                                          │
│ Circular      No                 Yes ✓                  │
│ behavior                                                 │
│                                                          │
│ Space reuse   Poor               Excellent ✓            │
│                                                          │
│ Best for      Never              Always! ✓              │
│                                                          │
│ Interview     Understanding      Required solution      │
└─────────────────────────────────────────────────────────┘

Which Approach to Use?

Approach 2 (Circular Array) is the ONLY correct solution!

Why Approach 2:
  ✓ All operations O(1)
  ✓ True circular behavior
  ✓ Efficient space reuse
  ✓ This is what "circular queue" means
  ✓ Expected in interviews

---

🧪 Edge Cases

Edge Case 1: Size 1 Queue

MyCircularQueue(1)

enQueue(1) → true
enQueue(2) → false (full)
Front() → 1
Rear() → 1
deQueue() → true
isEmpty() → true ✓

Edge Case 2: Fill, Empty, Refill

MyCircularQueue(2)

enQueue(1), enQueue(2) → both true
deQueue(), deQueue() → both true
enQueue(3), enQueue(4) → both true

Wraparound works correctly ✓

Edge Case 3: Front == Rear (Empty vs Full)

Initial: front=0, rear=-1, count=0 → Empty
After operations: front=0, rear=2, count=3 → Full

Count distinguishes them! ✓

Edge Case 4: Wraparound Multiple Times

MyCircularQueue(3)

Operations causing multiple wraps:
  enQueue, deQueue repeatedly

Modulo handles all wraps correctly ✓

---

⚠️ Common Mistakes

Mistake 1: Not using modulo

// ❌ WRONG - Goes out of bounds
rear = rear + 1;

// ✓ CORRECT - Wraps around
rear = (rear + 1) % capacity;

Mistake 2: Not tracking count

// ❌ WRONG - Can't distinguish empty vs full
public boolean isFull() {
    return front == rear;  // Could be empty too!
}

// ✓ CORRECT - Use count
public boolean isFull() {
    return count == capacity;
}

Mistake 3: Wrong initial rear value

// ❌ WRONG - rear starts at 0
rear = 0;
// First enQueue overwrites without incrementing!

// ✓ CORRECT - rear starts at -1
rear = -1;
// First enQueue increments to 0, then inserts

Mistake 4: Modifying data on deQueue

// ❌ WRONG - Wastes time
public boolean deQueue() {
    data[front] = 0;  // Unnecessary!
    front = (front + 1) % capacity;
}

// ✓ CORRECT - Just move pointer
public boolean deQueue() {
    front = (front + 1) % capacity;
    count--;
}

---

🎯 Pattern Recognition

When you see:

- "circular queue/buffer"
- "fixed size queue"
- "reuse space efficiently"
- "ring buffer"

Think:
  "Array with two pointers + modulo wraparound"

Similar Problems: - Design Circular Deque (LC 641) - Moving Average from Data Stream (LC 346) - Design Hit Counter (LC 362)

---

📝 Quick Revision Notes

🎯 Core Concept

Circular queue reuses space by wrapping around. Use array with front and rear pointers. Use modulo (%) for wraparound. Track count to distinguish empty vs full.

⚡ Quick Implementation

class MyCircularQueue {
  int[] a;
  int capacity;
  int front = 0;
  int rear = -1;
  int size = 0;

  public MyCircularQueue(int k) {
    a = new int[k];
    capacity = k;
  }

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

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

  public boolean enQueue(int value) {
    if(isFull()) {
      return false;
    }

    rear = (rear + 1) % capacity;
    a[rear] = value;
    size++;

    return true;
  }

  public boolean deQueue() {
    if(isEmpty()) {
      return false;
    }

    front = (front + 1) % capacity;
    size--;

    return true;
  }

  public int Front() {
    return isEmpty() ? -1 : a[front];
  }

  public int Rear() {
    return isEmpty() ? -1 : a[rear];
  }  
}

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

🔑 Key Insights

• Pattern: Circular buffer with wraparound
• Data Structure: Array + two pointers
• Wraparound: (index + 1) % capacity
• Empty check: count == 0
• Full check: count == capacity
• Initial rear: -1 (incremented before first insert)
• Space reuse: Modulo enables circular behavior
• Time: All operations O(1) ✓
• Space: O(k)

🎪 Memory Aid

"Two pointers dance around the circle!"
"Modulo makes the magic happen!"
"Count knows empty from full!" ✨

⚠️ Don't Forget

• Use modulo for wraparound
• Track count, not just pointers
• Initialize rear = -1
• Don't modify array on deQueue
• All operations must be O(1)

---

Happy practicing! 🎯