Design Circular Queue - Leetcode Solution

Problem statement:

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed in a circular manner. This means that the last item in the queue points to the first item in the queue. Thus, when you add an item to the queue, it is added after the last item in the queue, and the next item will become the first item. Similarly, when you remove an item from the queue, the first item is removed, and the next item becomes the first item.

Your circular queue should support the following operations:

• MyCircularQueue(k): Constructor, set the size of the queue to be k.
• Front: Get the front item from the queue. If the queue is empty, return -1.
• Rear: Get the last item from the queue. If the queue is empty, return -1.
• enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
• deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
• isEmpty(): Check whether the circular queue is empty or not.
• isFull(): Check whether the circular queue is full or not.

Solution:

To design a circular queue, we can use an array data structure. However, unlike a standard queue, we need to keep track of two pointers - front and rear. The front pointer points to the first element in the queue, while the rear pointer points to the last element in the queue. When an element is enqueued, the rear pointer is incremented, and when an element is dequeued, the front pointer is incremented. If the rear pointer exceeds the array size, it is set back to 0 to continue the circular counting.

The implementation of the MyCircularQueue class is as follows:

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = [-1] * k  # k-size array to store queue elements
        self.front = 0  # front pointer
        self.rear = 0  # rear pointer
        self.size = k  # size of queue

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

    def deQueue(self) -> bool:
        if not self.isEmpty():
            self.queue[self.front] = -1
            self.front = (self.front + 1) % self.size
            return True
        else:
            return False

    def Front(self) -> int:
        return self.queue[self.front]

    def Rear(self) -> int:
        return self.queue[(self.rear - 1 + self.size) % self.size]

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.queue[self.front] == -1

    def isFull(self) -> bool:
        return self.front == self.rear and self.queue[self.front] != -1

The constructor initializes the queue and the front and rear pointers. It takes an integer k as input, which is the size of the queue. The queue is initialized with -1 values to indicate that it is empty.

The enQueue method checks if the queue is full before adding an item. If it is not full, it adds the item to the rear of the queue and increments the rear pointer. It returns True if the operation is successful and False otherwise.

The deQueue method checks if the queue is empty before removing an item. If it is not empty, it removes the item from the front of the queue and increments the front pointer. It returns True if the operation is successful and False otherwise.

The Front and Rear methods return the first and last elements in the queue, respectively. They use the front and rear pointers to access the elements in the array.

The isEmpty and isFull methods check if the queue is empty or full, respectively, by checking if the front and rear pointers are equal and if the front element is -1 (indicating an empty queue) or not.

Testing:

We can test the MyCircularQueue class with the following test cases:

cq = MyCircularQueue(3)
assert cq.enQueue(1) == True
assert cq.enQueue(2) == True
assert cq.enQueue(3) == True
assert cq.enQueue(4) == False
assert cq.Rear() == 3
assert cq.isFull() == True
assert cq.deQueue() == True
assert cq.enQueue(4) == True
assert cq.Rear() == 4

This test creates a circular queue of size 3, enqueues elements 1, 2, and 3, and checks if the queue is full. It then dequeues the first element, enqueues element 4, and checks the last element in the queue.

1