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 <= 10000 <= value <= 10003000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.This approach utilizes a fixed-size array along with two pointers (or indices), front and rear, to maintain the positions within the queue effectively. The idea revolves around using modular arithmetic to effectively wrap around the queue once the end of the array is reached.
Operations like enQueue and deQueue are performed using these pointers, and conditions such as when the queue is full or empty are checked based on the relative position of these pointers.
This C solution defines a structure MyCircularQueue containing an array and variables to keep track of the front, rear, current size, and maximum size. myCircularQueueCreate allocates memory and initializes the queue. The enQueue function checks if the queue is full, updates the rear pointer, and inserts the element. deQueue function checks if the queue is empty and updates the front pointer. Front and rear position values are obtained by accessing respective pointers.
C++
Java
Python
C#
JavaScript
The time complexity for each operation such as enQueue, deQueue, Front, and Rear is O(1) as they involve simple arithmetic operations. The space complexity is O(k) where k is the size of the queue since we're using a static array.
This approach employs a circular linked list to implement the queue, leveraging linked nodes instead of a fixed-size array. The circular nature simplifies the wrap-around, allowing operations with dynamic sizing. Each node in the list holds a value and a reference to the next node, with the last node pointing back to the first, forming a circle.
Such a design accommodates flexible sizing but adds complexity in managing node references for enQueue and deQueue.
This C solution uses a circular linked list wherein each Node structure holds a value and a next pointer. The MyCircularQueue structure stores front and rear Node pointers along with size information. Insertion (enQueue) and deletion (deQueue) manage node links and pointers accordingly. Circular nature is handled by pointing the last node to the front node.
C++
Java
Python
C#
JavaScript
The time complexity for each operation is O(1) since they only involve rearranging node pointers. The space complexity is O(k) in the worst case if all queue slots are occupied.
| Approach | Complexity |
|---|---|
| Approach 1: Using an Array with Two Pointers | The time complexity for each operation such as |
| Approach 2: Using a Circular Linked List | The time complexity for each operation is O(1) since they only involve rearranging node pointers. The space complexity is O(k) in the worst case if all queue slots are occupied. |
Design Circular Queue - Leetcode 622 - Python • NeetCode • 28,375 views views
Watch 9 more video solutions →Practice Design Circular Queue with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor