algoadvance

Design your implementation of the circular queue. A 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. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the class MyCircularQueue:

MyCircularQueue(k: int) Initializes the object with the size of the queue to be k.
bool enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
bool 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.
bool isEmpty() Checks whether the circular queue is empty or not.
bool isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language.

Clarifying Questions

Is the size of the circular queue fixed after initialization?
- Yes, the size of the queue is fixed after the object is initialized.
Can negative or zero be an input value for enQueue?
- Yes, any integer (positive, negative, or zero) can be enqueued.
What should the methods return when operations can’t be performed (like deQueue on an empty queue, enQueue on a full queue)?
- In such cases, the methods should return false for unsuccessful operations and -1 for Front/Rear when the queue is empty.

Strategy

Data Structure:
- Use a fixed-size list to represent the queue and maintain front and rear pointers for the circular movement.
Initialization:
- Initialize queue with a list of given size k.
- Set both front and rear to -1 and maintain a variable count to track the number of elements.
Methods Implementation:
- enQueue: Insert an element by moving the rear pointer circularly and increase count.
- deQueue: Remove an element by moving the front pointer circularly and decrease count.
- Front: Return the element at the front pointer.
- Rear: Return the element at the rear pointer.
- isEmpty: Check if count is 0.
- isFull: Check if count is equal to the capacity k.

Code

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.capacity = k
        self.front = -1
        self.rear = -1
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        self.count -= 1
        return True

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

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

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

Time Complexity

enQueue: O(1)
deQueue: O(1)
Front: O(1)
Rear: O(1)
isEmpty: O(1)
isFull: O(1)

The time complexity of each operation is O(1), which is optimal for queue operations.

Try our interview co-pilot at AlgoAdvance.com

Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?