← Back to the queues page
Deque (Double-Ended Queue)
Push and pop at both ends in O(1). The monotonic deque is the only known way to do sliding-window maximum in true O(n).
What to know
- Sliding window maximum: front holds the current max’s index; smaller tails are evicted.
- Evict from the front when the index leaves the window.
- Also the natural structure for palindrome checking and work-stealing.
In the wild: Work-stealing thread pools, undo buffers, real-time min/max monitors on metrics streams.
Algorithms to reach for
Monotonic deque window max
O(n)Max of every k-window in one pass (LeetCode 239)
0-1 BFS
O(V + E)Shortest paths with 0/1 edge weights — push-front for 0
Palindrome check
O(n)Compare characters popped from both ends
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.