Design Circular Queue

Medium

Asked by:

+13

39 views

Topics:

ArraysTwo PointersSliding Windows

Design your implementation of the circular queue. The 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.

Implement the MyCircularQueue class:

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

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints:

1 <= k <= 1000
0 <= value <= 1000
At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Design Circular Queue

Medium

Asked by:

+7

39 views

Topics:

ArraysTwo PointersSliding Windows

Design your implementation of the circular queue. The 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.

Implement the MyCircularQueue class:

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

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

Constraints:

1 <= k <= 1000
0 <= value <= 1000
At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that will be enqueued into the queue? Are negative numbers or zero possible?
If the queue is full and I try to enqueue, what should happen? Should I return a boolean indicating failure, throw an exception, or overwrite the oldest element?
If the queue is empty and I try to dequeue, what should I return? Should I return a special value like -1, throw an exception, or return null?
What should the initial state of the queue be when it's created, particularly regarding the head and tail pointers? Should they both point to the beginning, or should the tail point to a position 'past' the beginning indicating the queue is empty?
Is the provided integer `k` for the queue's size guaranteed to be non-negative?

Brute Force Solution

Approach

Imagine having a container with a fixed number of slots, and we want to add or remove items. The brute force way involves meticulously tracking each item and checking if adding or removing goes beyond the container's capacity. This is done without clever shortcuts, just step-by-step management.

Here's how the algorithm would work step-by-step:

To start, when we want to add an item, we first see if there's any empty space available in the container.
If there's space, we put the new item into the container.
If the container is full, we can't add the item, so we might have to say it's not possible.
When we want to remove an item, we first check if there are any items present in the container.
If there are items, we take one out of the container.
If the container is already empty, we can't remove anything, so we might have to say it's not possible.
Each time we add or remove an item, we make sure that our 'location' for the next add or remove wraps around to the beginning if we reach the end of the container, like a circle.
We repeat these checks every time we want to add or remove an item, without using any special tricks to be more efficient.

Code Implementation

class MyCircularQueue:

    def __init__(self, capacity_value: int):
        self.queue_container = [None] * capacity_value
        self.queue_capacity = capacity_value
        self.queue_head = -1
        self.queue_tail = -1

    def enqueue(self, value: int) -> bool:
        # Check if the queue is full before enqueuing
        if self.is_full():
            return False

        if self.is_empty():
            self.queue_head = 0
        
        self.queue_tail = (self.queue_tail + 1) % self.queue_capacity
        self.queue_container[self.queue_tail] = value
        return True

    def dequeue(self) -> bool:
        # Check if the queue is empty before dequeuing
        if self.is_empty():
            return False

        if self.queue_head == self.queue_tail:
            self.queue_head = -1
            self.queue_tail = -1
        else:
            # Move the head to the next element
            self.queue_head = (self.queue_head + 1) % self.queue_capacity

        return True

    def front(self) -> int:
        if self.is_empty():
            return -1
        return self.queue_container[self.queue_head]

    def rear(self) -> int:
        if self.is_empty():
            return -1
        return self.queue_container[self.queue_tail]

    def is_empty(self) -> bool:
        return self.queue_head == -1

    def is_full(self) -> bool:
        # Need to check full condition before enqueuing
        return ((self.queue_tail + 1) % self.queue_capacity) == self.queue_head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The provided brute force solution for the circular queue involves only constant time operations for each enqueue or dequeue action. We are checking for empty or full conditions and updating pointers in a fixed number of steps, regardless of the size of the queue. Therefore, each operation takes constant time. No loops or recursion dependent on the input size are present.

Space Complexity

O(N) – The described implementation utilizes a fixed-size container (presumably an array) to store the items. The size of this container is determined at the beginning and is not modified thereafter. Therefore, auxiliary space is required to store all of the elements, and the number of elements will define the size of the array. Thus, the space complexity is O(N) where N represents the capacity of the circular queue.

Optimal Solution

Approach

Imagine the queue as a circle instead of a straight line. To efficiently manage adding and removing items, we'll use special pointers to keep track of the beginning and end of the stored data in the circle.

Here's how the algorithm would work step-by-step:

First, set up a fixed-size space to hold our items, thinking of it as a circular container.
Establish two markers: one to point to the next available spot to add a new item, and another to point to the first item currently in the queue.
When adding an item, place it at the location of the 'add' marker and then advance the marker to the next available spot, wrapping back to the beginning if necessary.
When removing an item, take it from the location of the 'remove' marker and then advance that marker to the next item, again wrapping around if necessary.
To check if the queue is full, see if the 'add' marker has caught up to the 'remove' marker. If they are in the same place, and the queue has been used, the queue is full.
To check if the queue is empty, see if the 'add' marker and 'remove' marker point to the same spot and the queue is empty.
By strategically managing these markers, we can add and remove items quickly without needing to move everything around in the queue.

Code Implementation

class MyCircularQueue:

    def __init__(self, queue_size: int):
        self.queue_array = [None] * queue_size
        self.head_index = 0
        self.tail_index = 0
        self.queue_size = queue_size
        self.current_size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        self.queue_array[self.tail_index] = value
        self.tail_index = (self.tail_index + 1) % self.queue_size
        self.current_size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.head_index = (self.head_index + 1) % self.queue_size
        self.current_size -= 1
        return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1

        # Calculate the index of the rear element
        rear_index = (self.tail_index - 1 + self.queue_size) % self.queue_size

        return self.queue_array[rear_index]

    def isEmpty(self) -> bool:
        # Check if the queue is empty
        return self.current_size == 0

    def isFull(self) -> bool:
        # Check if the queue is full
        return self.current_size == self.queue_size

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The circular queue implementation involves a fixed-size array. The enqueue, dequeue, isEmpty, and isFull operations all perform a fixed number of operations such as array access, pointer manipulation (incrementing head/tail with wraparound), and comparisons. These operations do not depend on the number of elements currently in the queue or the initial size of the queue. Therefore, the time complexity for each of these operations is constant.

Space Complexity

O(1) – The algorithm uses a fixed-size array to store the queue elements. It also maintains two pointers, one for the head and one for the tail of the queue. The space required for these pointers and the array is independent of the number of enqueue and dequeue operations performed. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
k is zero or negative	Throw an IllegalArgumentException, as a circular queue cannot have a non-positive size.
Multiple enqueue operations filling the queue to capacity, then multiple dequeue operations emptying the queue.	Verify that head and tail pointers are correctly updated to wrap around and elements are properly enqueued and dequeued without data loss or incorrect pointers.
Enqueue operation when the queue is already full.	Return false from the enqueue operation, indicating that the enqueue failed.
Dequeue operation when the queue is empty.	Return false from the dequeue operation, indicating that the dequeue failed.
Calling head() or tail() when the queue is empty.	Return -1 as specified in the prompt, indicating there is no element to return.
Extreme number of enqueue and dequeue operations leading to head and tail wrapping around multiple times.	Ensure that the modulo operator (%) is used correctly when calculating new positions for head and tail to prevent out-of-bounds access and maintain circularity.
Integer overflow for queue size k, especially during index calculations.	Use `int` for index calculations; ensure k itself doesn't exceed reasonable memory constraints before instantiating the array.
Rapid sequence of enqueue and dequeue operations that continuously switch between empty and full states.	Test for race conditions (if multithreaded), make sure the `isEmpty` and `isFull` methods update correctly after each op to prevent inconsistencies.