Definition
Deque (Double-Ended Queue) is a data structure that allows insertion and deletion at both ends. It combines the characteristics of both stack and queue for flexible use.
Key Characteristics
- ✓O(1) insertion/deletion at both ends
- ✓Can be used as a stack (using one end only)
- ✓Can be used as a queue (different operations at each end)
- ✓Frequently used in sliding window algorithms
Use Cases
Used in these scenarios:
Sliding Window Max/Min
Deque is used to find max/min in sliding window in O(n) because removal from both ends is possible.
Palindrome Check
Characters can be taken from both ends to efficiently check if a string is a palindrome.
Task Scheduling
High priority tasks can be added to front, low priority to back for flexible management.
Browser History
Manage visit history from both ends to implement forward/backward navigation.
Operations
Main operations:
pushFront
O(1)Insert an element at the front of the deque.
pushBack
O(1)Insert an element at the back of the deque.
popFront
O(1)Remove and return the element at the front.
popBack
O(1)Remove and return the element at the back.
peekFront / peekBack
O(1)View front/back element without removing it.
Complexity
Time Complexity
Space Complexity
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization