Design Circular Queue

Medium

Design Circular Queue

Medium

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 maximum size of the circular queue I should initialize?
Can I assume the values enqueued will always be within a certain range (e.g., integers)?
What should I return if I try to dequeue from an empty queue or enqueue into a full queue (e.g., throw an exception, return a specific error code, or a boolean indicating success/failure)?
Is this for a single-threaded or multi-threaded environment? If multi-threaded, do I need to handle concurrency?
Do I need to implement any additional methods beyond enqueue, dequeue, isEmpty, isFull, Front, and Rear?

Brute Force Solution

Approach

Think of a circular queue like a waiting line that loops around. A brute force method for managing this line involves manually checking every possible position for new people and removals, without trying to be clever or efficient.

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

When someone new wants to join the line, look at the next available spot in the circle.
If that spot is empty, put the person there.
If that spot is already taken, look at the next spot, and keep going around the circle until you find an empty spot.
When someone wants to leave the line, check if the first spot is occupied.
If it is, remove the person from that spot.
If the first spot is empty, check the next spot, and keep going around the circle until you find the person who has been waiting the longest.
Repeat these steps every time someone joins or leaves, without remembering or optimizing the process.

Code Implementation

class MyCircularQueue:

    def __init__(self, queue_capacity: int):
        self.queue_capacity = queue_capacity
        self.queue = [None] * queue_capacity
        self.queue_size = 0

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

        # Find the next available spot
        for index in range(self.queue_capacity):
            potential_spot = index % self.queue_capacity
            if self.queue[potential_spot] is None:
                self.queue[potential_spot] = value
                self.queue_size += 1
                return True

        return False

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

        # Check every element to remove the first
        for index in range(self.queue_capacity):
            potential_spot = index % self.queue_capacity
            if self.queue[potential_spot] is not None:
                self.queue[potential_spot] = None
                self.queue_size -= 1
                return True

        return False

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

        # Find the first element
        for index in range(self.queue_capacity):
            potential_spot = index % self.queue_capacity
            if self.queue[potential_spot] is not None:
                return self.queue[potential_spot]

        return -1

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

        # Find the last element by reverse iteration
        for index in range(self.queue_capacity - 1, -1, -1):
            potential_spot = index % self.queue_capacity
            if self.queue[potential_spot] is not None:
                return self.queue[potential_spot]

        return -1

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

    def isFull(self) -> bool:
        return self.queue_size == self.queue_capacity

# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

Big(O) Analysis

Time Complexity

O(n) – The enqueue operation, in the worst case, might iterate through the entire queue to find an empty spot if the queue is nearly full. Similarly, the dequeue operation, in the worst case, also iterates through the entire queue to find the front element. Therefore, both operations can take up to n steps, where n is the size of the queue. Since both enqueue and dequeue can iterate through all elements in the queue in worst-case scenarios, the time complexity is O(n).

Space Complexity

O(N) – The brute force approach, as described, stores the queue elements directly within a data structure (e.g., an array or list) that has a fixed size, say N, representing the maximum capacity of the circular queue. When someone joins the queue, a spot within this structure is filled, and when someone leaves, a spot is emptied. No auxiliary data structures are created beyond this fixed-size structure. Therefore, the auxiliary space complexity is directly proportional to the maximum queue size, N, which can be simplified to O(N).

Optimal Solution

Approach

The idea is to simulate a queue within a fixed-size container, but with a clever twist: once you reach the end, you wrap back to the beginning. This saves space by reusing emptied spots, and allows us to avoid constantly shifting data.

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

First, imagine having a fixed number of slots where you can store items.
Think of it as a circle rather than a straight line. When you add something and run out of space at the end, you go back to the beginning if there's room there.
Keep track of where the first item in the queue is, and where the next free slot is.
When you add an item, put it in the next free slot and move the 'next free slot' marker forward, wrapping around to the start if you hit the end.
When you remove an item, take it from the first item location and move the 'first item' marker forward, again wrapping around to the start if needed.
If the 'next free slot' marker catches up with the 'first item' marker, the queue is full. If they are in the same location and nothing is enqueued, the queue is empty.
This circular approach means you never have to move items around in the container, just keep track of the first item and the next available spot, making it efficient.

Code Implementation

class CircularQueue:

    def __init__(self, queue_capacity):
        self.queue_capacity = queue_capacity
        self.queue = [None] * queue_capacity
        self.head_index = 0
        self.tail_index = 0
        self.queue_size = 0

    def enqueue(self, value):
        if self.isFull():
            return False

        self.queue[self.tail_index] = value
        self.tail_index = (self.tail_index + 1) % self.queue_capacity
        self.queue_size += 1
        return True

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

        self.head_index = (self.head_index + 1) % self.queue_capacity
        self.queue_size -= 1

        return True

    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[self.head_index]

    def Rear(self):
        if self.isEmpty():
            return -1
        rear_index = (self.tail_index - 1) % self.queue_capacity
        return self.queue[rear_index]

    def isEmpty(self):
        return self.queue_size == 0

    def isFull(self):
        return self.queue_size == self.queue_capacity

Big(O) Analysis

Time Complexity

O(1) – The operations in the circular queue, such as enqueue, dequeue, isEmpty, isFull, and front, involve only updating the head and tail pointers and accessing elements at specific indices. These operations take a constant amount of time regardless of the queue size n (the capacity of the queue). Therefore, each of these operations has a time complexity of O(1).

Space Complexity

O(N) – The space complexity of the Circular Queue is determined by the size of the fixed-size container, represented as an array, which is initialized when the queue is created. If the fixed size is 'N', then an array of size N is created to hold the queue elements. The first and next available slot markers are integer variables and contribute constant space. Therefore, the auxiliary space used scales linearly with N, the declared size of the circular queue, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Queue is full when enqueueing	Return false to indicate enqueue failure without modifying the queue state.
Queue is empty when dequeueing or peeking	Return -1 (or throw an exception in some languages) to indicate an empty queue operation.
Queue is initialized with a zero or negative capacity	Throw an IllegalArgumentException or return an error code to indicate invalid input.
Enqueueing and dequeueing repeatedly, nearing max integer value for head/tail	The modulo operation ensures head and tail wrap around correctly, preventing integer overflow issues during indexing.
Capacity is 1 (minimum size)	Handle full and empty queue states carefully, paying attention to head == tail condition.
Many enqueue and dequeue operations such that tail 'catches up' to head	The isFull() and isEmpty() methods must correctly account for the modulo wrap-around.
Integer overflow when calculating next position for head or tail	The modulo operator (%) prevents overflow by wrapping indices within the queue's capacity.
Calling peek when the queue is logically full (head == tail, but size is supposed to be 0)	The isEmpty() check must preempt peek() operations when head and tail are equal and the queue's size is 0.