Design your implementation of the circular double-ended queue (deque).
Implement the MyCircularDeque class:
MyCircularDeque(int k) Initializes the deque with a maximum size of k.boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.boolean isEmpty() Returns true if the deque is empty, or false otherwise.boolean isFull() Returns true if the deque is full, or false otherwise.
Example 1:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4] Explanation MyCircularDeque myCircularDeque = new MyCircularDeque(3); myCircularDeque.insertLast(1); // return True myCircularDeque.insertLast(2); // return True myCircularDeque.insertFront(3); // return True myCircularDeque.insertFront(4); // return False, the queue is full. myCircularDeque.getRear(); // return 2 myCircularDeque.isFull(); // return True myCircularDeque.deleteLast(); // return True myCircularDeque.insertFront(4); // return True myCircularDeque.getFront(); // return 4
Constraints:
1 <= k <= 10000 <= value <= 10002000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.Problem Overview: Design a double-ended queue (deque) with a fixed capacity that behaves like a circular buffer. You must support operations such as insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull in constant time.
Approach 1: Circular Array (O(1) time, O(k) space)
This approach stores elements in a fixed-size array and treats it as circular using modular arithmetic. Maintain two pointers: front and rear. When inserting at the front, decrement the front index using (front - 1 + capacity) % capacity. When inserting at the rear, increment rear using (rear + 1) % capacity. Deletions move the pointers in the opposite direction. The key insight is that wrap‑around indexing lets the array reuse freed positions instead of shifting elements. A counter or size variable helps detect isFull and isEmpty. All operations run in O(1) time with O(k) space, where k is the deque capacity. This approach leverages simple memory layout and cache-friendly access patterns using an array.
Approach 2: Doubly Linked List (O(1) time, O(k) space)
A linked list implementation models the deque with nodes that store prev and next pointers. Maintain two references: head for the front and tail for the rear. Insertions at either end create a new node and adjust the neighboring pointers. Deletions simply move the head or tail pointer and detach the removed node. Because each node directly connects to both neighbors, operations at both ends remain constant time. Track the current size to enforce the capacity limit and determine isFull or isEmpty. Every operation runs in O(1) time with O(k) space for storing nodes. This approach is more flexible but has slightly higher memory overhead due to pointer storage.
Both implementations follow the core behavior of a deque: efficient insertions and removals from both ends. The difference lies in memory layout and pointer management. Circular arrays rely on index arithmetic, while linked lists rely on pointer adjustments.
Recommended for interviews: The circular array implementation is usually the expected answer. It demonstrates understanding of circular buffers, modular arithmetic, and memory efficiency. The linked list approach still satisfies the requirements and shows solid knowledge of pointer manipulation, but interviewers often prefer the array solution because it avoids extra node allocations and mirrors how real systems implement bounded deques.
This approach involves using a fixed-size array to represent the deque. We'll maintain two indices, front and rear, to manage the current front and last positions in the deque. Operations like insertions and deletions are performed by adjusting these indices while ensuring they wrap around using the modulo operation as necessary to remain within the array bounds.
This implementation uses a circular array to manage the deque operations. The array is of fixed size, calculated by the given capacity, and follows the circular method to use the front and rear indices effectively. The modulo operation is crucial to wrap around these indices and prevent them from exceeding array bounds.
Time Complexity: O(1) for each operation.
Space Complexity: O(k), where k is the capacity of the deque.
This approach makes use of a doubly linked list to implement the deque. This is particularly effective because it offers dynamic memory usage which can grow or shrink with the number of elements, instead of relying on a pre-allocated fixed-size structure as with arrays.
Using a linked list in C allows dynamic memory management for each element in the deque. Nodes are created or deleted dynamically, with pointers next and prev facilitating easy front and rear operations.
Time Complexity: O(1) for all operations.
Space Complexity: O(n), where n is the number of elements currently in the deque (potentially more efficient if n is much less than the initial capacity).
We can use an array to implement the circular deque. We maintain a pointer front pointing to the front of the queue, a variable size representing the number of elements in the queue, and a variable capacity representing the queue's capacity. We use an array q to store the elements.
When insertFront is called, we first check if the queue is full; if so, return false. Otherwise, we move front one position forward (using modular arithmetic for circular wrapping), insert the new element at front, and increment size by 1.
When insertLast is called, we first check if the queue is full; if so, return false. Otherwise, we compute the insertion position (using front and size), insert the new element there, and increment size by 1.
When deleteFront is called, we first check if the queue is empty; if so, return false. Otherwise, we move front one position backward (using modular arithmetic for circular wrapping) and decrement size by 1.
When deleteLast is called, we first check if the queue is empty; if so, return false. Otherwise, we decrement size by 1.
When getFront is called, we first check if the queue is empty; if so, return -1. Otherwise, we return q[front].
When getRear is called, we first check if the queue is empty; if so, return -1. Otherwise, we compute the position of the rear element (using front and size) and return the element at that position.
When isEmpty is called, we check whether size equals 0.
When isFull is called, we check whether size equals capacity.
All operations above have a time complexity of O(1) and a space complexity of O(k), where k is the capacity of the deque.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using Circular Array | Time Complexity: O(1) for each operation. |
| Using Linked List | Time Complexity: O(1) for all operations. |
| Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Circular Array | O(1) per operation | O(k) | Preferred for fixed-capacity deque implementations and interview settings due to simplicity and cache efficiency |
| Doubly Linked List | O(1) per operation | O(k) | Useful when dynamic node manipulation is preferred or when implementing deque behavior without array indexing |
Design Circular Deque | Simplest Explanation | 2 Ways | Leetcode 641 | codestorywithMIK • codestorywithMIK • 7,669 views views
Watch 9 more video solutions →Practice Design Circular Deque with our built-in code editor and test cases.
Practice on FleetCode