grid47 Exploring patterns and algorithms
Sep 5, 2024
7 min read
Solution to LeetCode 622: Design Circular Queue Problem
Design and implement a Circular Queue. A circular queue is a linear data structure where the operations follow the FIFO principle, and the last position is connected to the first, forming a circle. This design allows better space utilization.
Problem
Approach
Steps
Complexity
Input: You will be provided with an integer `k`, the size of the circular queue. The operations available are enQueue, deQueue, Front, Rear, isEmpty, and isFull.
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.
Output: For each operation, return the appropriate result: true/false for enQueue, deQueue, isEmpty, isFull; the element for Front and Rear operations.
• Explanation: This example demonstrates the behavior of the queue when full, showing the operations enQueue, deQueue, and the correct handling of the queue size limit.
Approach: We will use a circular array with two pointers to track the front and rear of the queue, ensuring efficient insertion and removal of elements.
Observations:
• Circular queues provide better space utilization by reusing the front space once elements are dequeued.
• We will use modular arithmetic to wrap the indices around when the front or rear reaches the end of the array.
Steps:
• 1. Create a circular array of size `k`.
• 2. Implement a variable to keep track of the front and rear positions.
• 3. Use modular arithmetic to handle wrapping around the queue when inserting and removing elements.
Empty Inputs:
• Trying to dequeue or get the front/rear of an empty queue should return -1.
Large Inputs:
• The queue size can go up to 1000, but the implementation should still be efficient.
Special Values:
• When the queue is full, trying to enqueue an element should return false.
Constraints:
• Ensure the number of operations does not exceed 3000.
Constructor that initializes the circular queue with a given size `k`, setting the front index (`frd`) to 0, the back index (`bck`) to -1, and initializing the queue array `q` with `k` zeros. The element count (`cnt`) is also set to 0.
5 : Enqueue Method
boolenQueue(int value) {
Defines the `enQueue` method that adds an element to the circular queue if it's not full.
6 : Enqueue Check Full
if(isFull()) returnfalse;
Checks if the queue is full. If true, returns `false` to indicate the enqueue operation failed.
7 : Enqueue Update Back Index
bck = (bck +1) % sz;
Updates the back index (`bck`) to the next position in the circular queue, wrapping around if necessary.
8 : Enqueue Insert Value
q[bck] = value;
Inserts the given value into the queue at the current back index.
9 : Enqueue Increment Count
cnt++;
Increments the count (`cnt`) of elements in the queue after successfully inserting the value.
10 : Enqueue Return
returntrue;
Returns `true` to indicate that the enqueue operation was successful.
11 : Dequeue Method
booldeQueue() {
Defines the `deQueue` method that removes an element from the front of the circular queue if it's not empty.
12 : Dequeue Check Empty
if(isEmpty()) returnfalse;
Checks if the queue is empty. If true, returns `false` to indicate the dequeue operation failed.
13 : Dequeue Update Front Index
frd = (frd +1) % sz;
Updates the front index (`frd`) to the next position in the circular queue, wrapping around if necessary.
14 : Dequeue Decrement Count
cnt--;
Decrements the count (`cnt`) of elements in the queue after successfully removing an element.
15 : Dequeue Return
returntrue;
Returns `true` to indicate that the dequeue operation was successful.
16 : Front Method
intFront() {
Defines the `Front` method that returns the element at the front of the circular queue, or -1 if empty.
17 : Front Check Empty
if(isEmpty()) return-1;
Checks if the queue is empty. If true, returns `-1` to indicate there is no front element.
18 : Front Return
return q[frd];
Returns the element at the front of the queue.
19 : Rear Method
intRear() {
Defines the `Rear` method that returns the element at the rear of the circular queue, or -1 if empty.
20 : Rear Check Empty
if(isEmpty()) return-1;
Checks if the queue is empty. If true, returns `-1` to indicate there is no rear element.
21 : Rear Return
return q[bck];
Returns the element at the rear of the queue.
22 : isEmpty Method
boolisEmpty() {
Defines the `isEmpty` method that checks if the queue is empty.
23 : isEmpty Return
return cnt ==0;
Returns `true` if the queue is empty, i.e., if the element count (`cnt`) is 0.
24 : isFull Method
boolisFull() {
Defines the `isFull` method that checks if the queue is full.
25 : isFull Return
return cnt == sz;
Returns `true` if the queue is full, i.e., if the element count (`cnt`) is equal to the queue size (`sz`).
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: All operations (enQueue, deQueue, Front, Rear, isEmpty, isFull) take constant time.
Best Case: O(k)
Worst Case: O(k)
Description: Space complexity is proportional to the size of the queue, which is `k`.
