622. Design Circular Queue - Detailed Explanation

Problem Statement

Description:
You are required to design a circular queue with a fixed size. The circular queue supports the following operations:

• MyCircularQueue(k):
  Initializes the circular queue with a maximum capacity of k.

• enQueue(value):
  Inserts an element into the circular queue. Returns true if the operation is successful; otherwise, returns false.

• deQueue():
  Deletes an element from the circular queue. Returns true if the operation is successful; otherwise, returns false.

• Front():
  Gets the front item from the queue. If the queue is empty, return -1.

• Rear():
  Gets the last item from the queue. If the queue is empty, return -1.

• isEmpty():
  Checks whether the circular queue is empty.

• isFull():
  Checks whether the circular queue is full.

Example 1:

• Input:

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

• Output:
  The operations should behave as described above.

Constraints:

• 1 ≤ k ≤ 1000 (or similar bounds)
• All values inserted will be integers.
• The operations must work in O(1) time on average.

Hints

• Hint 1:
  Think of the queue as a fixed-size array. Use two pointers (or indices) to track the front and rear positions.

• Hint 2:
  To support wrap-around, use modulo arithmetic when incrementing your pointers. This will help you simulate a circular structure within a linear array.

• Hint 3:
  Be careful when checking if the queue is empty or full. One common trick is to maintain a count of the current number of elements or reserve one slot in the array to distinguish between full and empty cases.

Approach 1: Using an Array with Head, Tail, and Count

Idea

• Data Structure:
  Use a fixed-size array to store the elements. Maintain three variables:

  • head: The index of the front element.
  • tail: The index where the next element will be inserted.
  • count: The current number of elements in the queue.

• Operations:

  • enQueue(value):
    If the queue is full (count == capacity), return false. Otherwise, insert the value at the tail index, then increment tail (using modulo arithmetic to wrap around) and increase the count.

  • deQueue():
    If the queue is empty (count == 0), return false. Otherwise, remove the element at the head, then increment head (using modulo arithmetic) and decrease the count.

  • Front():
    Return the element at head if not empty; otherwise, return -1.

  • Rear():
    The last element is at index (tail - 1 + capacity) % capacity if the queue is not empty.

  • isEmpty() / isFull():
    Use the count variable to check if the queue is empty or full.

Walkthrough Example

Let’s simulate operations on a circular queue of capacity 3:

1. Initialize:

   • head = 0, tail = 0, count = 0, and an array of size 3.

2. enQueue(1):

   • Insert 1 at tail index 0.
   • Set tail = (0 + 1) % 3 = 1 and count = 1.

3. enQueue(2):

   • Insert 2 at tail index 1.
   • Set tail = (1 + 1) % 3 = 2 and count = 2.

4. enQueue(3):

   • Insert 3 at tail index 2.
   • Set tail = (2 + 1) % 3 = 0 (wrap-around) and count = 3.

5. enQueue(4):

   • The queue is full (count == capacity), so return false.

6. Rear():

   • Calculate rear index as (tail - 1 + capacity) % capacity = (0 - 1 + 3) % 3 = 2.
   • Return element at index 2, which is 3.

7. deQueue():

   • Remove the element at head index 0.
   • Set head = (0 + 1) % 3 = 1 and count = 2.

8. enQueue(4):

   • Insert 4 at tail index 0.
   • Set tail = (0 + 1) % 3 = 1 and count = 3.

9. Rear():

   • Now the rear index is (tail - 1 + capacity) % capacity = (1 - 1 + 3) % 3 = 3 % 3 = 0.
   • Return element at index 0, which is 4.

Code Implementation

Python Code