Deque
DSA · Stacks and Queues
Theory
A deque (double-ended queue) allows adding and removing items at both the front and the back in O(1). It can act as both a stack and a queue. Python's collections.deque also supports a maxlen that automatically drops the oldest items, which is ideal for keeping the last N events.
Why we use it
It combines stack and queue behaviour efficiently and powers the sliding-window maximum technique.
When to use it
Use a deque for sliding window problems, recent-history buffers, palindrome checks and work-stealing schedulers.
How it works
- Empty deque
- Add? Yes: appendleft (front) or append (rear). No: Remove.
- Remove from which end? Yes: popleft (front). No: pop (rear).
- All operations O(1)
Syntax
d = deque()
d.append(x); d.appendleft(x)
d.pop(); d.popleft()
deque(maxlen=3) # keeps only the last 3 itemsExample
from collections import deque
recent = deque(maxlen=3)
for page in ["home", "sql", "python", "dsa", "blog"]:
recent.append(page)
print("Visited", page, "| last 3:", list(recent))
d = deque([2, 3])
d.appendleft(1)
d.append(4)
print("Both ends:", d.popleft(), d.pop(), "| left:", list(d))Key points
- O(1) at both ends
- Works as a stack or a queue
- maxlen keeps a fixed-size history
- Used in sliding window maximum