Design Circular Queue

#1 Most AskedMedium

Design Circular Queue #1 Most Asked

Medium

85 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.

Try coding it in LeetCode

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 are the constraints on the integer `k` (the size of the circular queue)? Can it be zero or negative?
What is the expected data type and range of the elements to be enqueued? Should I handle potential overflows or underflows if the elements are very large or small?
When the queue is empty, is it acceptable to return -1 for `Front` and `Rear`, or should a different sentinel value or an exception be used?
If `enqueue` is called on a full queue, what should be the behavior? Should it return `false` or overwrite the oldest element?
Does the `dequeue` operation return the removed element, or is it just a void operation? The problem description implies it's just a removal, but it's good to confirm.

Brute Force Solution

Approach

To design a circular queue, the brute force approach involves creating a fixed-size storage and carefully managing where items are added and removed to simulate a wrap-around behavior. This means tracking the front and back of the queue and handling cases where the queue fills up or becomes empty by cleverly reusing space.

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

Set up a container that can hold a certain number of items.
When an item needs to be added, find the next available spot at the back of the container.
If the back reaches the end of the container, make it wrap around to the beginning.
When an item needs to be removed, take it from the front of the container.
If the front reaches the end of the container, make it wrap around to the beginning.
Keep track of how many items are currently in the container.
If the container is full when you try to add an item, you cannot add it.
If the container is empty when you try to remove an item, you cannot remove anything.

Code Implementation

class CircularQueue:

    def __init__(self, capacity):
        self.queue_storage = [None] * capacity
        self.queue_capacity = capacity
        self.front_index = 0
        self.back_index = -1
        self.current_size = 0

    def enqueue(self, item):
        if self.is_full():
            return False

        # Increment back_index and wrap around if necessary
        self.back_index = (self.back_index + 1) % self.queue_capacity
        self.queue_storage[self.back_index] = item
        self.current_size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return False

        # Remove item from the front and advance front_index, wrapping around
        removed_item = self.queue_storage[self.front_index]
        self.queue_storage[self.front_index] = None  # Optional: clear removed item
        self.front_index = (self.front_index + 1) % self.queue_capacity
        self.current_size -= 1
        return removed_item

    def peek(self):
        if self.is_empty():
            return None
        return self.queue_storage[self.front_index]

    def is_empty(self):
        return self.current_size == 0

    def is_full(self):
        return self.current_size == self.queue_capacity

Big(O) Analysis

Time Complexity

O(1) – The design of a circular queue utilizes a fixed-size storage and maintains pointers for the front and rear. Operations like enqueue (adding an element) and dequeue (removing an element) involve simple arithmetic operations (modulo arithmetic for wrap-around) and pointer updates. These operations take a constant amount of time regardless of the number of elements currently in the queue. Therefore, each of these operations has a time complexity of O(1).

Space Complexity

O(k) – The solution uses a fixed-size container (an array) of size k to store the queue elements. Additionally, it uses a few integer variables (front, rear, and count) to manage the queue's state. Since the size of the container k is predefined and does not depend on the number of elements being added or removed (unless k is dynamically sized based on input, which is not implied here), the auxiliary space complexity is constant with respect to the number of operations. Therefore, the space complexity is O(k), representing the fixed storage space required for the queue itself.

Optimal Solution

Approach

A circular queue behaves like a regular queue but wraps around. The clever trick is to use a fixed storage space and manage two pointers to keep track of the front and back of the queue, allowing it to reuse space efficiently.

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

Imagine you have a fixed-size storage area, like a row of boxes.
You need to keep track of where the first item is and where the next item should be placed.
When you add an item, you place it in the next available spot after the last item you added.
If you reach the end of your storage area while adding, you simply wrap around to the beginning.
When you remove an item, you take it from the spot where the first item is.
After removing an item, the next item to be removed is now in the spot that was just emptied.
If the storage area is full and you try to add another item, it means the queue is full and you can't add it.
If you try to remove an item from an empty storage area, it means the queue is empty and there's nothing to remove.
By having these two tracking points, you can efficiently add and remove items, reusing the storage space as it becomes available.

Code Implementation

class CircularQueue:
    def __init__(self, queue_size):
        self.queue_storage = [None] * queue_size
        self.queue_capacity = queue_size
        self.front_pointer = 0
        self.rear_pointer = 0
        self.current_item_count = 0

    def enqueue_item(self, item_to_add):
        if self.is_queue_full():
            return False

        self.queue_storage[self.rear_pointer] = item_to_add
        self.rear_pointer = (self.rear_pointer + 1) % self.queue_capacity
        self.current_item_count += 1
        return True

    def dequeue_item(self):
        if self.is_queue_empty():
            return False

        # When dequeuing, we retrieve the item at the front pointer.
        removed_item = self.queue_storage[self.front_pointer]
        self.queue_storage[self.front_pointer] = None # Optional: Clear the dequeued slot
        self.front_pointer = (self.front_pointer + 1) % self.queue_capacity
        self.current_item_count -= 1
        return removed_item

    def peek_front_item(self):
        if self.is_queue_empty():
            return None
        return self.queue_storage[self.front_pointer]

    def peek_rear_item(self):
        if self.is_queue_empty():
            return None
        # The rear pointer points to the next available slot, so we need to go back one.
        return self.queue_storage[(self.rear_pointer - 1 + self.queue_capacity) % self.queue_capacity]

    def is_queue_empty(self):
        # The queue is empty if no items have been added or all have been removed.
        return self.current_item_count == 0

    def is_queue_full(self):
        # The queue is full when the number of items equals its capacity.
        return self.current_item_count == self.queue_capacity

    def get_queue_size(self):
        return self.current_item_count

Big(O) Analysis

Time Complexity

O(1) – The operations on a circular queue, such as enqueue, dequeue, isEmpty, and isFull, involve manipulating two pointers (front and rear) and performing simple arithmetic operations. These operations do not depend on the number of elements currently in the queue or the maximum capacity of the queue. Each operation takes a constant amount of time, regardless of the input size, hence it is O(1).

Space Complexity

O(1) – The space complexity is O(1) because the solution uses a fixed-size storage area (an array) and a constant number of variables (pointers like front and rear) to manage the queue, regardless of the number of elements currently in the queue or the maximum capacity. No additional data structures are created that scale with the input or queue size.

Edge Cases

Case	How to Handle
Queue size k is 0 or negative	The constructor should validate k and throw an error or handle it gracefully, as a queue of non-positive size is invalid.
Enqueueing into a full queue	The enqueue operation should return false and not modify the queue state when isFull returns true.
Dequeueing from an empty queue	The dequeue operation should return false and not modify the queue state when isEmpty returns true.
Front or Rear operation on an empty queue	These operations must return -1 as specified when the queue is empty.
Circular wrapping of front and rear pointers	Modulo arithmetic (e.g., (index + 1) % k) must be correctly applied to ensure pointers wrap around the array.
Queue transitions from empty to full, and full to empty	The logic for isEmpty and isFull needs to accurately reflect the queue's state after enqueues and dequeues, especially when only one element is present.
Maximum k value leading to potential integer overflow if not handled	While k is an integer, the indices and count within the queue implementation should use appropriate data types to avoid overflow if k is very large.
Enqueuing and immediately dequeueing the same element	The implementation must correctly handle the scenario where the front and rear pointers might become the same after these operations, ensuring isEmpty and isFull are accurate.

Queue size k is 0 or negative

How to Handle:

The constructor should validate k and throw an error or handle it gracefully, as a queue of non-positive size is invalid.

Enqueueing into a full queue

How to Handle:

The enqueue operation should return false and not modify the queue state when isFull returns true.

Dequeueing from an empty queue

How to Handle:

The dequeue operation should return false and not modify the queue state when isEmpty returns true.

Front or Rear operation on an empty queue

How to Handle:

These operations must return -1 as specified when the queue is empty.

Circular wrapping of front and rear pointers

How to Handle:

Modulo arithmetic (e.g., (index + 1) % k) must be correctly applied to ensure pointers wrap around the array.

Queue transitions from empty to full, and full to empty

How to Handle:

The logic for isEmpty and isFull needs to accurately reflect the queue's state after enqueues and dequeues, especially when only one element is present.

Maximum k value leading to potential integer overflow if not handled

How to Handle:

While k is an integer, the indices and count within the queue implementation should use appropriate data types to avoid overflow if k is very large.

Enqueuing and immediately dequeueing the same element

How to Handle:

The implementation must correctly handle the scenario where the front and rear pointers might become the same after these operations, ensuring isEmpty and isFull are accurate.