Deque
A double-ended queue: O(1) push and pop at both the front and the back. One structure that can act as a stack, a queue, or both at once.
A deque generalises stacks and queues by allowing insertion and removal at both ends. Implementations use a doubly linked list or, more commonly, a circular buffer / block list that keeps both ends O(1) without shifting elements.
Use it as a stack (push/pop the same end), a queue (push back, pop front), or something richer: sliding-window algorithms keep a monotonic deque whose front is always the current window's best value; work-stealing schedulers pop from one end while other threads steal from the opposite end.
The trade-off mirrors the queue: no efficient random access into the middle, and cache behaviour depends on the underlying blocks.
Operations
| Operation | Complexity |
|---|---|
| push front / back | O(1) |
| pop front / back | O(1) |
| peek either end | O(1) |
| index middle | O(n) (list) / O(1) (buffer) |
Where it's used
Sliding-window maxima, work-stealing task queues, undo/redo, palindrome checks, BFS variants (0-1 BFS).