622. Design Circular Queue

Problem Description

The problem requires designing a circular queue, which is a variation of a standard queue that allows for efficient utilization of storage space. In contrast with a conventional queue where once it becomes full you cannot add new elements, even if there is available space due to earlier removed elements, a circular queue allows you to use that space and continue adding new elements by circling back to the beginning of the queue.

The operations that need to be supported are:

MyCircularQueue(k): Constructor - initialize the queue with a fixed size k.
enQueue(value): Insert an element into the queue, return true if successful.
deQueue(): Remove an element from the queue, return true if successful.
Front(): Return the element at the front of the queue without removing it, return -1 if the queue is empty.
Rear(): Return the element at the end of the queue without removing it, return -1 if the queue is empty.
isEmpty(): Check if the queue is empty.
isFull(): Check if the queue is full.

The implementation should not use any built-in queue data structures provided by the programming language.

Intuition

In order to implement a circular queue, we can use a fixed-size array to represent the queue. Two pointers, front and size, and the capacity of the queue are needed to keep track of its state:

front: This stores the index of the first (front) element of the queue.
size: This represents the current number of elements in the queue.
capacity: This is the maximum number of elements our queue can hold, as defined upon initialization.

The key to achieving circular behavior is to use modulo operator (%) for index calculation. When we increment the front pointer or add new elements (incrementing the size), we are always wrapping around using modulo capacity.

For instance, when enqueueing, to find the index position to insert the new element, we compute (front + size) % capacity. When dequeueing, to move the front pointer, we simply do (front + 1) % capacity. This allows us to reuse the free space resulting from removing elements at the front.

The enQueue operation should insert a value at the rear of the queue. We first check if the queue is full by comparing size with capacity. If not full, we calculate the position to insert the new element, store the value, and increment size.

The deQueue operation should remove the value at the front of the queue. We check if the queue is empty if not, we move the front pointer forward and decrement size.

The Front operation returns the element at the front pointer if the queue isn't empty; otherwise, it returns -1.

The Rear operation calculates the position of the last element using (front + size - 1) % capacity and returns its value if the queue isn't empty; otherwise, it returns -1.

The isEmpty and isFull operations return the result of comparing the size to 0 and capacity, respectively.

This approach ensures all operations are completed in O(1) time complexity, which is optimal.

Learn more about Queue and Linked List patterns.

Solution Approach

The solution utilizes an array, two integer variables (front and size), and modulo arithmetic to simulate a circular queue. The decision to use an array is based on the need for constant-time access to elements at both the front and rear ends of the queue.

Here is the detailed breakdown of the implementation:

Initializing the Queue

We define a constructor __init__(self, k: int) which accepts the capacity k of the queue.
An array self.q with size k is initialized to store the elements. All values are initially set to 0, which acts as our storage space.
The self.front variable is set to 0, pointing at the position that the first element of the queue should occupy initially.
self.size represents the current number of elements and is initialized to 0.
self.capacity is set to k, the maximum size of the queue.

Enqueue Operation

enQueue(self, value: int) is used to insert a new element at the rear of the queue.
First, we check whether the queue is full by comparing self.size and self.capacity. If it is full, we return False as we cannot add more elements.
If not full, we calculate the next rear position using (self.front + self.size) % self.capacity to get the appropriate index within our array bounds.
Then we insert the new value into the calculated index and increase self.size by 1.
We return True to indicate the operation succeeded.

Dequeue Operation

deQueue(self) is used to remove an element from the front of the queue.
We check if the queue is empty by checking if self.size is 0. If it is, we return False as there are no elements to remove.
If not empty, we update the self.front index to the next position using (self.front + 1) % self.capacity, effectively jumping over the front element, thus removing it from the queue.
We decrement self.size by 1 and return True to indicate the operation succeeded.

Front and Rear Operations

Front(self) returns the value at the front of the queue without removing it. We calculate this simply by accessing self.q[self.front], provided self.size is not 0; if it is, we return -1.
Rear(self) returns the last element of the queue. We calculate the index of the last element using (self.front + self.size - 1) % self.capacity and return its value if the queue is not empty, otherwise return -1.

Check if Empty or Full

isEmpty(self) returns True if the queue is empty, which is the case when self.size is 0.
isFull(self) returns True if the queue is full, which happens when self.size is equal to self.capacity.

These methods implement the fundamental operations of a circular queue and meet the constraints of the problem, with all operations having a time complexity of O(1).

The solution leverages simple data structures and arithmetic properties to fulfill the requirements of the circular queue effectively and efficiently, without the need for any additional data structures or overly complex logic.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use an example to illustrate how the solution approach works. We'll create a circular queue with a capacity of 3 and walk through a sequence of operations.

Initialize the circular queue with capacity k = 3.
```
cq = MyCircularQueue(3)
```
Now, front = 0, size = 0, and capacity = 3.
Attempt to enQueue the value 1 into the queue:
```
cq.enQueue(1)
```
Since the queue is not full (size < capacity), we insert 1 at (front + size) % capacity = (0 + 0) % 3 = 0, the cq.q becomes [1, 0, 0], size becomes 1.
Enqueue the value 2 into the queue:
```
cq.enQueue(2)
```
The queue is still not full, we insert 2 at (front + size) % capacity = (0 + 1) % 3 = 1, now cq.q is [1, 2, 0], size becomes 2.
Enqueue the value 3 into the queue:
```
cq.enQueue(3)
```
Again, the queue is not full, we insert 3 at (front + size) % capacity = (0 + 2) % 3 = 2, cq.q becomes [1, 2, 3], size becomes 3.
Try to enQueue the value 4 into the queue:
```
cq.enQueue(4)
```
The queue is full (size == capacity), so this returns False, and the queue remains unchanged.
Get the front value of the queue:
```
cq.Front()
```
Returns 1 because front = 0 and cq.q[front] = 1.
DeQueue an element from the queue:
```
cq.deQueue()
```
The queue is not empty (size > 0), so we remove the front element by updating front = (front + 1) % capacity = (0 + 1) % 3 = 1, and size becomes 2. The queue now conceptually looks like [2, 3].
Get the rear value of the queue:
```
cq.Rear()
```
Returns 3 because the rear index is (front + size - 1) % capacity = (1 + 2 - 1) % 3 = 2, and cq.q[2] = 3.
Check if the queue is empty:
```
cq.isEmpty()
```
Returns False because size = 2, which is not 0.
Check if the queue is full:
```
cq.isFull()
```
Returns False because size = 2 is less than capacity = 3.

Through these operations, we can see how the circular queue correctly implements the demand for a fixed-size, efficient data structure allowing front-end removal and rear-end insertion.

Solution Implementation

1class MyCircularQueue:
2    def __init__(self, k: int):
3        self.queue = [0] * k  # Initialize the circular queue with 'k' elements set to 0
4        self.head_index = 0  # The front pointer to the first element of the circular queue
5        self.count = 0  # Current number of elements in the circular queue
6        self.capacity = k  # Maximum capacity of the circular queue
7
8    def enQueue(self, value: int) -> bool:
9        """Inserts an element into the circular queue. Return true if the operation is successful."""
10        if self.isFull():
11            # Return False if the queue is full
12            return False
13        # Calculate the index at which to insert the new value
14        idx = (self.head_index + self.count) % self.capacity
15        self.queue[idx] = value  # Insert the value
16        self.count += 1  # Increment the size of the queue
17        return True  # Return True on successful insertion
18
19    def deQueue(self) -> bool:
20        """Deletes an element from the circular queue. Return true if the operation is successful."""
21        if self.isEmpty():
22            # Return False if the queue is empty
23            return False
24        # Increment the head_index as we remove the front element
25        self.head_index = (self.head_index + 1) % self.capacity
26        self.count -= 1  # Decrement the size of the queue
27        return True  # Return True on successful deletion
28
29    def Front(self) -> int:
30        """Gets the front item from the queue. If the queue is empty, return -1."""
31        if self.isEmpty():
32            # If the queue is empty, return -1
33            return -1
34        # Otherwise, return the front element
35        return self.queue[self.head_index]
36
37    def Rear(self) -> int:
38        """Gets the last item from the queue. If the queue is empty, return -1."""
39        if self.isEmpty():
40            # If the queue is empty, return -1
41            return -1
42        # Calculate the index of the rear element
43        idx = (self.head_index + self.count - 1) % self.capacity
44        # Return the rear element
45        return self.queue[idx]
46
47    def isEmpty(self) -> bool:
48        """Checks whether the circular queue is empty."""
49        # Return True if count equals 0, meaning the queue is empty
50        return self.count == 0
51
52    def isFull(self) -> bool:
53        """Checks whether the circular queue is full."""
54        # Return True if count equals the capacity, meaning the queue is full
55        return self.count == self.capacity
56
57
58# Example of how the class could be used:
59# obj = MyCircularQueue(k)
60# success = obj.enQueue(value)
61# success = obj.deQueue()
62# item = obj.Front()
63# item = obj.Rear()
64# is_empty = obj.isEmpty()
65# is_full = obj.isFull()
66

1class MyCircularQueue {
2    private int[] queue;     // Array representation of the circular queue
3    private int front;       // Index of the front element
4    private int size;        // Current size of the queue
5    private int capacity;    // Maximum capacity of the queue
6
7    // Constructor to initialize the queue with a given capacity.
8    public MyCircularQueue(int k) {
9        queue = new int[k];
10        capacity = k;
11        front = 0;
12        size = 0;
13    }
14
15    // Inserts an element into the circular queue. Returns true if the operation is successful.
16    public boolean enQueue(int value) {
17        if (isFull()) { // Check if the queue is full
18            return false;
19        }
20        // Calculate the index where the value will be inserted
21        int index = (front + size) % capacity;
22        queue[index] = value;
23        size++; // Increment the size of the queue
24        return true;
25    }
26
27    // Deletes an element from the circular queue. Returns true if the operation is successful.
28    public boolean deQueue() {
29        if (isEmpty()) { // Check if the queue is empty
30            return false;
31        }
32        front = (front + 1) % capacity; // Move the front pointer to the next element
33        size--; // Decrement the size of the queue
34        return true;
35    }
36
37    // Gets the front item from the queue. If the queue is empty, return -1.
38    public int Front() {
39        if (isEmpty()) { // Check if the queue is empty
40            return -1;
41        }
42        return queue[front]; // Return the front element
43    }
44
45    // Gets the last item from the queue. If the queue is empty, return -1.
46    public int Rear() {
47        if (isEmpty()) { // Check if the queue is empty
48            return -1;
49        }
50        // Calculate the index of the rear element
51        int index = (front + size - 1) % capacity;
52        return queue[index]; // Return the rear element
53    }
54
55    // Checks if the circular queue is empty.
56    public boolean isEmpty() {
57        return size == 0; // Return true if the size is 0
58    }
59
60    // Checks if the circular queue is full.
61    public boolean isFull() {
62        return size == capacity; // Return true if the size is equal to the capacity
63    }
64}
65
66/**
67 * Example of usage:
68 * MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
69 * boolean enQueueResult = circularQueue.enQueue(1);  // return true
70 * boolean deQueueResult = circularQueue.deQueue();  // return true
71 * int front = circularQueue.Front();  // return 1, or -1 if the queue is empty
72 * int rear = circularQueue.Rear();  // return the last element, or -1 if the queue is empty
73 * boolean isEmpty = circularQueue.isEmpty();  // return false
74 * boolean isFull = circularQueue.isFull();  // return true if the queue is full
75 */
76

1class MyCircularQueue {
2private:
3    int frontIndex;     // index of the front element
4    int currentSize;    // current number of elements in the queue
5    int maxCapacity;    // maximum capacity of the queue
6    vector<int> queue;  // vector to store the elements of the queue
7
8public:
9    // Constructor to initialize the queue with a fixed size.
10    MyCircularQueue(int k) {
11        maxCapacity = k;
12        queue = vector<int>(k);
13        frontIndex = currentSize = 0;
14    }
15
16    // Enqueue an element into the circular queue.
17    // Returns true if the operation is successful.
18    bool enQueue(int value) {
19        if (isFull()) return false;
20        int idx = (frontIndex + currentSize) % maxCapacity; // calculate index using modulo operation
21        queue[idx] = value; // place value at the calculated index
22        ++currentSize; // increment currentSize since we added an element
23        return true;
24    }
25
26    // Dequeue an element from the circular queue.
27    // Returns true if the operation is successful.
28    bool deQueue() {
29        if (isEmpty()) return false;
30        frontIndex = (frontIndex + 1) % maxCapacity; // update front index to the next element
31        --currentSize; // decrement currentSize to reflect removal
32        return true;
33    }
34
35    // Get the front item from the queue.
36    // Returns -1 if the queue is empty.
37    int Front() {
38        if (isEmpty()) return -1;
39        return queue[frontIndex];
40    }
41
42    // Get the last item from the queue.
43    // Returns -1 if the queue is empty.
44    int Rear() {
45        if (isEmpty()) return -1;
46        int idx = (frontIndex + currentSize - 1) % maxCapacity; // calculate index of the rear item
47        return queue[idx];
48    }
49
50    // Check if the queue is empty.
51    // Returns true if the queue is empty.
52    bool isEmpty() {
53        return currentSize == 0;
54    }
55
56    // Check if the queue is full.
57    // Returns true if the queue is full.
58    bool isFull() {
59        return currentSize == maxCapacity;
60    }
61};
62
63/**
64 * Your MyCircularQueue object will be instantiated and called as such:
65 * MyCircularQueue* obj = new MyCircularQueue(k);
66 * bool param_1 = obj->enQueue(value);
67 * bool param_2 = obj->deQueue();
68 * int param_3 = obj->Front();
69 * int param_4 = obj->Rear();
70 * bool param_5 = obj->isEmpty();
71 * bool param_6 = obj->isFull();
72 */
73

1let queue: number[];
2let left: number;
3let right: number;
4let capacity: number;
5
6function initializeQueue(k: number): void {
7    queue = new Array(k);
8    left = 0;
9    right = 0;
10    capacity = k;
11}
12
13function enqueue(value: number): boolean {
14    if (isFull()) {
15        return false;
16    }
17    queue[right % capacity] = value;
18    right++;
19    return true;
20}
21
22function dequeue(): boolean {
23    if (isEmpty()) {
24        return false;
25    }
26    left++;
27    return true;
28}
29
30function front(): number {
31    if (isEmpty()) {
32        return -1;
33    }
34    return queue[left % capacity];
35}
36
37function rear(): number {
38    if (isEmpty()) {
39        return -1;
40    }
41    return queue[(right - 1) % capacity];
42}
43
44function isEmpty(): boolean {
45    return right - left === 0;
46}
47
48function isFull(): boolean {
49    return right - left === capacity;
50}
51
52// Usage example:
53// initializeQueue(3);
54// let successEnqueue = enqueue(10);
55// let successDequeue = dequeue();
56// let frontValue = front();
57// let rearValue = rear();
58// let isEmptyQueue = isEmpty();
59// let isFullQueue = isFull();
60

Time and Space Complexity

Time Complexity

__init__(self, k: int): The constructor has a time complexity of O(k) because it initializes an array of size k.
enQueue(self, value: int) -> bool: Enqueue operation has a time complexity of O(1) because it involves arithmetic calculations for determining the index at which to insert the new element and inserting it into the queue, which are constant-time operations.
deQueue(self) -> bool: Dequeue operation has a time complexity of O(1) since it only updates the front index and decreases the size, both of which are constant-time operations.
Front(self) -> int: Retrieving the front item has a time complexity of O(1) because it directly accesses the element at the front index of the array.
Rear(self) -> int: Retrieving the rear item has a time complexity of O(1) as it involves calculating the index of the rear and accessing it which are constant-time operations.
isEmpty(self) -> bool: Checking if the queue is empty has a time complexity of O(1) as it's a simple comparison operation.
isFull(self) -> bool: Checking if the queue is full has a time complexity of O(1) since it is also a comparison operation.

Space Complexity

The space complexity for the entire MyCircularQueue class is O(k) where k is the capacity of the queue. This is due to the array of size k used for storing the queue elements.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know