Implementing Circular Queue

Problem Description
A Circular Queue is a queue data structure implemented based on an array, which solves the problem of wasted space after dequeuing in a regular queue by reusing array space circularly. The following operations need to be implemented:

• enqueue(value): Add an element to the rear of the queue.
• dequeue(): Remove and return the element at the front of the queue.
• front(): Get the front element (without removing it).
• isEmpty(): Check if the queue is empty.
• isFull(): Check if the queue is full.

Key Challenge: How to distinguish between an empty queue and a full queue.

Solution Process

1. Basic Structure Design
The circular queue uses an array to store data and requires maintaining two pointers:

• front: Points to the position of the front element.
• rear: Points to the next position after the rear element (i.e., the position where a new element will be inserted).
• Reserve one empty slot to distinguish between empty and full states (a common technique).

Example initialization (queue with capacity k):

class CircularQueue:
    def __init__(self, k: int):
        self.size = k + 1  # One extra empty slot
        self.data = [None] * self.size
        self.front = 0
        self.rear = 0

2. Empty/Full Judgment Logic

• Empty queue: front == rear
• Full queue: (rear + 1) % size == front
  (When the next position of rear is front, it is considered full, and the actual capacity at this time is size-1.)

3. Enqueue Operation (enqueue)

def enqueue(self, value: int) -> bool:
    if self.isFull():
        return False  # Queue is full
    self.data[self.rear] = value
    self.rear = (self.rear + 1) % self.size  # Circular movement
    return True

Key point: Achieve pointer circulation through modulo operation:

• When rear reaches the end of the array, (rear+1) % size will return to the beginning of the array.
• For example, when size=5 and rear=4: (4+1)%5=0.

4. Dequeue Operation (dequeue)

def dequeue(self) -> bool:
    if self.isEmpty():
        return False
    self.front = (self.front + 1) % self.size  # Move front pointer
    return True

Note: In practical applications, it may be necessary to return the dequeued value; here, it is simplified to a boolean.

5. Get Front Element

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

6. Get Rear Element

def Rear(self) -> int:
    if self.isEmpty():
        return -1
    return self.data[(self.rear - 1 + self.size) % self.size]  # Handle circulation

Difficulty Analysis: rear points to the next empty slot, so the rear element is at position rear-1. When rear=0, (0-1+5)%5=4 is needed to correctly get the last element.

7. Complete Code Example

class CircularQueue:
    def __init__(self, k: int):
        self.size = k + 1
        self.data = [None] * self.size
        self.front = 0
        self.rear = 0

    def enqueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        return True

    def dequeue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.size
        return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1) % self.size]

    def isEmpty(self) -> bool:
        return self.front == self.rear

    def isFull(self) -> bool:
        return (self.rear + 1) % self.size == self.front

8. Practical Testing

# Test case
q = CircularQueue(3)
q.enqueue(1)  # Returns True
q.enqueue(2)  # Returns True  
q.enqueue(3)  # Returns True
q.enqueue(4)  # Returns False (full)
q.Front()     # Returns 1
q.Rear()      # Returns 3
q.dequeue()   # Returns True
q.enqueue(4)  # Returns True (reuse space circularly)
q.Rear()      # Returns 4

Core Idea: Achieve circular movement of pointers through modulo operation. Use (rear+1)%size == front to determine if the queue is full, ensuring at least one empty slot is unused, thereby distinguishing it from the empty queue state.