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.Problem Overview: Design a fixed-size circular queue that supports enQueue, deQueue, Front, Rear, isEmpty, and isFull. The key constraint is circular behavior: when the end of the storage is reached, the queue should wrap around and reuse empty space at the beginning.
Approach 1: Using an Array with Two Pointers (Time: O(1), Space: O(k))
This approach stores elements in a fixed-size array and tracks positions using two indices: front and rear. When inserting or removing elements, you update these pointers using modulo arithmetic ((index + 1) % k) so they wrap around the array. A separate counter or size variable helps determine whether the queue is full or empty. All operations—insert, delete, and peek—run in constant time because they only involve index updates. This design is common in system-level implementations of queue structures and works well when the capacity is known in advance.
Approach 2: Using a Circular Linked List (Time: O(1), Space: O(k))
Instead of a fixed array, this method uses nodes connected in a circular linked list. The tail node points back to the head, forming a loop. You maintain references to the head, tail, and a size counter. Insertion attaches a new node after the tail and updates the circular link, while deletion moves the head pointer forward. Because pointer adjustments are constant-time operations, every queue operation still runs in O(1). This approach is useful when demonstrating dynamic memory management or when implementing custom data structure design problems.
Recommended for interviews: The array-based circular buffer is the expected solution. Interviewers typically want to see correct pointer movement with modulo arithmetic and accurate handling of full vs empty states. Implementing the circular linked list shows deeper data structure understanding, but the array approach is simpler, faster in practice due to cache locality, and widely used in production systems.
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.
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.
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.
We can use an array q of length k to simulate a circular queue, with a pointer front to record the position of the front element. Initially, the queue is empty, and front is 0. Additionally, we use a variable size to record the number of elements in the queue, initially size is 0.
When calling the enQueue method, we first check if the queue is full, i.e., size = k. If it is full, we return false. Otherwise, we insert the element at position (front + size) bmod k, then size = size + 1, indicating that the number of elements in the queue has increased by 1. Finally, we return true.
When calling the deQueue method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return false. Otherwise, we set front = (front + 1) bmod k, indicating that the front element has been dequeued, then size = size - 1.
When calling the Front method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return -1. Otherwise, we return q[front].
When calling the Rear method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return -1. Otherwise, we return q[(front + size - 1) bmod k].
When calling the isEmpty method, we simply check if size = 0.
When calling the isFull method, we simply check if size = k.
In terms of time complexity, the above operations all have a time complexity of O(1). The space complexity is O(k).
| 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. |
| Array Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array with Two Pointers | O(1) per operation | O(k) | Best choice when capacity is fixed and high performance is required |
| Circular Linked List | O(1) per operation | O(k) | Useful when demonstrating pointer-based queue design or dynamic allocation |
Design Circular Queue - Leetcode 622 - Python • NeetCode • 37,800 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