Design Circular Queue

Problem Description
Design a circular queue (Circular Queue), also known as a ring buffer. A circular queue is a linear data structure whose operations are based on the FIFO (First-In-First-Out) principle, and the tail of the queue is connected to the head to form a circle. It is also called a "ring buffer."

One advantage of a circular queue is that we can reuse the space that has been used before in the queue. In a regular queue, once the queue is full, we cannot insert the next element, even if there is space available at the front of the queue. However, with a circular queue, we can use that space to store new values.

You need to implement the following operations:

• MyCircularQueue(k): Constructor, sets the queue length to k.
• Front: Gets the element at the front of the queue. If the queue is empty, returns -1.
• Rear: Gets the element at the rear of the queue. If the queue is empty, returns -1.
• enQueue(value): Inserts an element into the circular queue. Returns true if the operation is successful.
• deQueue(): Deletes an element from the circular queue. Returns true if the operation is successful.
• isEmpty(): Checks if the circular queue is empty.
• isFull(): Checks if the circular queue is full.

Solution Process

Step 1: Understanding the Core Concept and Challenges of a Circular Queue

Imagine a regular queue implemented with a fixed-length array. When we remove elements from the front (head) and add elements to the rear (tail), both the front and rear pointers move backward. Even if empty spaces appear at the front of the array, when the rear pointer reaches the end of the array, we consider the queue "full" and cannot add new elements. This leads to wasted space.

A circular queue solves this problem by treating the array as a "ring." When the rear pointer reaches the end of the array, if there is empty space at the beginning of the array, the next element is placed at the start of the array. This way, as long as the queue is not truly filled with elements, we can continue adding elements.

The main challenge lies in determining whether the queue is "empty" or "full."

1. Condition for an empty queue: When there are no elements in the queue, we define the front and rear pointers to be equal.
2. Condition for a full queue: If we also use the equality of front and rear pointers to indicate a full queue, it conflicts with the condition for an empty queue.

Step 2: Choosing a Solution—Waste One Space

To resolve the conflict between empty and full conditions, the most common and clear method is to "waste" one element space in the array.

• We allocate an array of size k+1, but stipulate that it can store at most k valid elements.
• front: Points to the position of the first element in the queue.
• rear: Points to the next position after the last element in the queue (i.e., the position where the next new element should be inserted).

Now, we can define clear state conditions:

• Queue is empty: front == rear
• Queue is full: (rear + 1) % capacity == front
  • Explanation: If the next position of rear (using modulo operation to achieve circularity) is front, the queue is considered full. Since we always reserve one empty space, when rear points to this empty space, we consider the queue full and cannot insert further; otherwise, we cannot distinguish between empty and full.

Step 3: Detailed Design of Each Operation

Assume the declared array is queue, the capacity (maximum number of elements that can be stored) is k, but the actual allocated array size is k+1. We define capacity = k+1.

1. Constructor MyCircularQueue(k)

   • Initialize an array of size k+1 (e.g., self.queue = [0] * (k+1)).
   • Initialize self.front = 0.
   • Initialize self.rear = 0.
   • Record the maximum capacity of the queue: self.capacity = k+1.

2. isEmpty()

   • Directly check self.front == self.rear. If equal, return True; otherwise, return False.

3. isFull()

   • Check (self.rear + 1) % self.capacity == self.front. If equal, return True; otherwise, return False.

4. enQueue(value)

   • First, check if the queue is full (call isFull()). If full, return False.
   • If not full, perform the following:
     a. Place value at the position currently pointed to by the rear pointer: self.queue[self.rear] = value.
     b. Move the rear pointer one step backward (with circular wrap-around): self.rear = (self.rear + 1) % self.capacity.
   • Return True.

5. deQueue()

   • First, check if the queue is empty (call isEmpty()). If empty, return False.
   • If not empty, perform the following:
     a. Move the front pointer one step backward (with circular wrap-around): self.front = (self.front + 1) % self.capacity.
     • (Note: In a queue, deleting an element from the front typically does not require explicitly deleting the data in the array; moving the pointer suffices.)
   • Return True.

6. Front()

   • If the queue is empty, return -1.
   • Otherwise, return the element currently pointed to by the front pointer: return self.queue[self.front].

7. Rear()

   • If the queue is empty, return -1.
   • Otherwise, return the element at the position before rear, because rear points to the next insertion position.
   • Calculate the position of the rear element: (self.rear - 1 + self.capacity) % self.capacity.
     • Explanation: self.rear - 1 might result in a negative number (e.g., when rear is 0). Adding capacity and then taking the modulo ensures a valid, non-negative index.
   • Return the element at that position: return self.queue[(self.rear - 1) % self.capacity].

Step 4: Example

Let's design a circular queue with a capacity of 3 (k=3). The allocated array size is 4 (capacity=4).

Initial state: front = 0, rear = 0, queue is empty.
[ , , , ] (underscore indicates empty space)
Indices: 0, 1, 2, 3

1. enQueue(1): rear=0 is not full, place 1 at index 0, rear moves to (0+1)%4=1.
   Queue: [1, _, _, _], front=0, rear=1

2. enQueue(2): rear=1 is not full, place 2 at index 1, rear moves to (1+1)%4=2.
   Queue: [1, 2, _, _], front=0, rear=2

3. enQueue(3): rear=2 is not full, place 3 at index 2, rear moves to (2+1)%4=3.
   Queue: [1, 2, 3, _], front=0, rear=3

4. enQueue(4): Check if full? (3+1)%4=0, 0 == front(0)? Yes, queue is full, insertion fails.

5. deQueue(): Queue is not empty, front moves to (0+1)%4=1.
   Queue: [_, 2, 3, _], front=1, rear=3 (Space at index 0 is freed, but data 1 remains; we just no longer access it)

6. enQueue(4): Now check if full? (3+1)%4=0, 0 == front(1)? No, not full. Place 4 at index 3, rear moves to (3+1)%4=0.
   Queue: [_, 2, 3, 4], front=1, rear=0. This demonstrates the circular nature.

7. Rear(): Returns the position before rear. rear=0, previous position is (0-1+4)%4=3. Returns the value at queue[3], which is 4. Correct.

8. Front(): Returns the value at queue[1], which is 2. Correct.

Through this example, you can clearly see how the strategy of "wasting one space" works and how the pointers circulate.