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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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).
| Approach | Complexity |
|---|---|
| Using Circular Array | Time Complexity: O(1) for each operation. |
| Using Linked List | Time Complexity: O(1) for all operations. |
Design Circular Queue - Leetcode 622 - Python • NeetCode • 28,375 views views
Watch 9 more video solutions →Practice Design Circular Deque with our built-in code editor and test cases.
Practice on FleetCode