Watch 10 video solutions for Design Circular Queue, a medium level problem involving Array, Linked List, Design. This walkthrough by NeetCode has 37,800 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |