Deque
mediumO(1) push and pop at the front and the back. That combination is what makes the sliding-window maximum trick possible - every element enters and leaves exactly once.
O(1) at both endsSpace O(n)What to notice
O(1) at both ends
That combination is what makes the sliding-window maximum trick possible: push candidates at the back, evict stale ones from the front, and every element enters and leaves exactly once.
Saved in this browser - no sign-up, nothing sent anywhere.
How a deque works
A deque is a queue with the restriction removed: push and pop are O(1) at the front and at the back. Four operations instead of two, and each is still a single read or write at an end - no shifting, no walking, no exceptions.
That combination is what makes the sliding-window maximum trick possible. New candidates enter at the back, popping anything they dominate; stale elements expire off the front as the window slides. Every element enters and leaves exactly once, so processing a whole array of windows costs O(n).
It also subsumes both simpler structures: use one end only and it is a stack; use opposite ends and it is a queue. That is why Python ships collections.deque as the standard answer for both - append with popleft is the idiomatic queue.
Step by step
- Start with 14, 27, 8 - 14 at the front, 8 at the back, and both ends live.
- pushBack(52): 52 joins behind 8 with one write at the back - ordinary queue behaviour so far.
- pushFront(3): 3 lands ahead of 14 - the O(1) operation a plain queue cannot offer.
- popFront: 3 leaves from the front immediately - no shifting of the four elements behind it.
- popBack: 52 leaves from the back, stack-style. The deque is back to 14, 27, 8.
- Four operations across two different ends, every one of them constant time - that symmetry is the entire structure.
Complexity
| Worst case time | O(1) at both ends |
|---|---|
| Space | O(n) |
Reference implementation
Python
from collections import deque
q = deque()
q.append(x) # enqueue at the back - O(1)
x = q.popleft() # dequeue from the front - O(1)
q.appendleft(y) # deque only
y = q.pop() # deque only
# Never use a list for a queue: list.pop(0) is O(n),
# because every remaining element shifts down one slot.JavaScript
const stack = [];
stack.push(x); // O(1)
const top = stack.at(-1);
stack.pop(); // O(1)
// Array.shift() is O(n) - for a real queue use two stacks,
// a ring buffer, or a linked list.Common pitfalls
- Backing it with a plain array: pushFront then shifts everything, making one end O(n). Real deques use a ring buffer or linked blocks.
- Mixing up ends in sliding-window code: candidates are evicted from the back, expiries from the front - swap them and answers are silently wrong.
- Indexing into the middle: collections.deque allows it but at O(n) - a deque is fast at its ends, not everywhere.
- Assuming thread safety everywhere: Python's deque documents thread-safe appends and pops, but most implementations in other languages promise nothing.
Where it is used
- Sliding-window maximum and minimum - the canonical hard interview use.
- Work-stealing schedulers: a worker pops its own end while thieves take from the other.
- Undo and redo with a bounded history - push new actions, drop the oldest off the far end.
- 0-1 BFS on graphs with 0 and 1 edge weights, pushing zero-weight moves at the front.
Frequently asked questions
What is the time complexity of deque operations?
O(1) worst case at both ends - pushFront, pushBack, popFront and popBack each touch only their own end. Space is O(n) for the stored elements. Middle access is the exception: indexing into a linked-block deque like Python's costs O(n).
When should I use a deque instead of a stack or queue?
When one algorithm genuinely needs both ends: window problems that admit at the back and expire at the front, work stealing, bounded histories that drop the oldest entry. If you only ever touch one end, a plain stack or queue states the intent more clearly.
How does the sliding-window maximum use a deque?
Keep indices whose values decrease from front to back. Each new element pops smaller values off the back before joining; the front is always the current window's maximum, and it is popped once it slides out of range. Every element enters and leaves once - O(n) overall.
Is collections.deque faster than a list in Python?
At the front, dramatically: appendleft and popleft are O(1) while list.insert(0, x) and list.pop(0) are O(n). At the back both are fast. For random access into the middle the list wins - deque indexing walks its blocks in O(n).