Design Circular Queue

Design a circular queue that allows efficient FIFO operations using linked-list pointer manipulation to optimize space usage.

array linked list design queue

Problem Statement

The task is to design and implement a circular queue that efficiently uses available space while adhering to the FIFO (First In First Out) principle. A circular queue is a linear structure where the last position points to the first one, effectively forming a circle. This allows for more efficient utilization of space compared to traditional queues, as new elements can be inserted even when some earlier positions are empty.

You need to implement the MyCircularQueue class, providing methods to insert elements, remove them, and check for specific states of the queue. Operations like enQueue, deQueue, and checking whether the queue is full or empty should be part of your solution, and the goal is to design it in a way that ensures optimal space and time complexity for all operations.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 Approach

Use an Array with Circular Indexing

In this approach, we can utilize a simple array and manipulate the indices to simulate the circular behavior. Both the front and rear pointers wrap around when they reach the boundaries of the array. The enQueue operation moves the rear pointer forward, and deQueue moves the front pointer. This avoids wasting space in the queue and optimizes performance.

Linked-List Pointer Manipulation

For a more space-efficient design, we can implement the circular queue using a linked list. Each node points to the next, and the last node points back to the first node. This method allows dynamic resizing, although the operations must be carefully managed to avoid excessive memory usage or complexity.

Optimized Array Implementation

An optimized array-based approach involves using modulo arithmetic to manage the circular behavior of the queue. The rear and front indices are updated with modulo operations, allowing for constant time operations for enQueue and deQueue. This avoids shifting elements and improves space usage over traditional queue implementations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both the time and space complexity depend on the approach used. The array-based circular queue has a time complexity of O(1) for enQueue and deQueue, and space complexity of O(k), where k is the size of the queue. The linked-list-based approach has similar time complexities for these operations, but may have additional memory overhead for pointers, leading to slightly higher space usage in practice.

What Interviewers Usually Probe

Ability to optimize space usage in a FIFO data structure.
Proficiency with circular data structure concepts.
Understanding of linked-list manipulation and pointer handling.

Common Pitfalls or Variants

Common pitfalls

Failing to properly handle the circular nature of the queue, leading to overflow or underflow.
Not managing the front and rear pointers correctly, causing incorrect operations.
Using excessive space when a linked-list or array-based approach could optimize memory usage.

Follow-up variants

Implement the circular queue using a doubly linked list for bi-directional traversal.
Modify the queue to support multiple types of data (generic queue).
Add extra methods like peek or getSize to extend the basic operations.

FAQ

What is the main pattern to solve Design Circular Queue?

The primary pattern used in solving the Design Circular Queue problem is linked-list pointer manipulation or array-based circular indexing, both of which optimize space utilization.

How does using a circular queue optimize space compared to a regular queue?

A circular queue allows the reuse of available space in the array when the front elements are removed, unlike a regular queue that fails to reuse space once the queue is full.

What is the time complexity of enQueue and deQueue operations in the Design Circular Queue?

Both enQueue and deQueue operations have a time complexity of O(1), as the front and rear pointers are simply adjusted with constant-time operations.

What is a common mistake when implementing the Design Circular Queue?

A common mistake is failing to handle the circular behavior correctly, which can result in overflow, underflow, or incorrectly updating the front and rear pointers.

Can the Design Circular Queue be implemented using a doubly linked list?

Yes, a doubly linked list can be used for the circular queue to provide efficient bi-directional traversal and flexible memory management.

terminal

Solution

Solution 1: Array Simulation

We can use an array $q$ of length $k$ to simulate a circular queue, with a pointer $\textit{front}$ to record the position of the front element. Initially, the queue is empty, and $\textit{front}$ is $0$. Additionally, we use a variable $\textit{size}$ to record the number of elements in the queue, initially $\textit{size}$ is $0$.

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [0] * k
        self.size = 0
        self.capacity = k
        self.front = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.q[(self.front + self.size) % self.capacity] = value
        self.size += 1
        return True

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

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[(self.front + self.size - 1) % self.capacity]

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

    def isFull(self) -> bool:
        return self.size == self.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()

Continue Practicing

#641 design circular deque #705 design hashset #706 design hashmap