The Conveyor Belt Analogy
Imagine a conveyor belt in a factory:
- You can add items to either end
- You can remove items from either end
- Unlike a regular queue (one-way) or stack (one end only)
A deque (double-ended queue) gives you the flexibility of both stacks and queues in one structure.
Deque vs Stack vs Queue
Stack (one end):
Push → [A, B, C] → Pop
Only access from TOP
Queue (two ends, one-way):
Enqueue → [A, B, C] → Dequeue
Add at back, remove from front
Deque (two ends, both ways):
← [A, B, C] →
Add/remove from BOTH ends!
All Three in One
Deque can act as:
Stack: append_right + pop_right
Queue: append_right + pop_left
Reverse queue: append_left + pop_right
Deque Operations
Core Operations
APPEND_RIGHT - Add to right end (O(1))
Deque: [A, B]
append_right(C) → [A, B, C]
APPEND_LEFT - Add to left end (O(1))
Deque: [A, B]
append_left(Z) → [Z, A, B]
POP_RIGHT - Remove from right end (O(1))
Deque: [A, B, C]
pop_right() → returns C, deque: [A, B]
POP_LEFT - Remove from left end (O(1))
Deque: [A, B, C]
pop_left() → returns A, deque: [B, C]
PEEK_RIGHT/LEFT - Look without removing (O(1))
Deque: [A, B, C]
peek_right() → C
peek_left() → A
All O(1)!
Every operation is constant time - no matter how many elements.
Visual Walkthrough
Empty deque:
[ ]
append_right(1):
[ 1 ]
append_right(2):
[ 1 | 2 ]
append_left(0):
[ 0 | 1 | 2 ]
pop_right() → 2:
[ 0 | 1 ]
pop_left() → 0:
[ 1 ]
append_left(-1), append_right(5):
[ -1 | 1 | 5 ]
Where Deques Are Used
1. Sliding Window Problems
Find max in each window of size k:
Array: [1, 3, -1, -3, 5, 3, 6, 7], k=3
Use deque to track potential maximums:
- Remove elements outside window (pop_left)
- Remove smaller elements (pop_right)
- Add new element (append_right)
- Front is the current max!
Answer: [3, 3, 5, 5, 6, 7]
2. BFS on Two Directions
0-1 BFS with weighted edges (0 or 1 cost):
- Edge cost 0: append_left (process first)
- Edge cost 1: append_right (process later)
3. Work Stealing
Thread schedulers:
- Add new tasks to own deque
- Process from one end
- Other threads can "steal" from opposite end
4. Undo/Redo with Limit
Keep last N actions:
- New action: append_right
- Undo: pop_right
- If overflow: pop_left (remove oldest)
5. Palindrome Check
Check if string is palindrome:
while deque.length > 1:
if pop_left() != pop_right():
return false
return true
Classic Deque Problems
1. Sliding Window Maximum
Window of size k, find max in each window.
Array: [1, 3, -1, -3, 5, 3], k=3
Use deque of indices, maintain decreasing order:
Window [1,3,-1]: deque has index of 3 (max)
Slide: [3,-1,-3]: deque updates, 3 still max
Slide: [-1,-3,5]: 5 is new max
Slide: [-3,5,3]: 5 is still max
Results: [3, 3, 5, 5]
2. Design Circular Deque
Implement fixed-size deque:
- insertFront, insertLast
- deleteFront, deleteLast
- getFront, getRear
- isEmpty, isFull
Use circular array with front/rear pointers.
3. Design Hit Counter
Count hits in a recent time window.
Deque stores timestamps:
- New hit: append_right(timestamp)
- Query: pop_left while timestamp too old
- Answer: len(deque)
Implementation
Array-Based (Circular)
Fixed array with wrap-around:
[C, D, _, _, A, B]
↑ ↑
rear front
append_right: rear++
append_left: front--
Wrap around when reaching array bounds.
Linked List-Based
Doubly linked list:
front ↔ A ↔ B ↔ C ↔ rear
All operations easily O(1).
No size limit!
Deque vs Array
Operation | Deque | Array
----------------|-------|------
Append left | O(1) | O(n) ← must shift everything!
Append right | O(1) | O(1)
Pop left | O(1) | O(n) ← must shift everything!
Pop right | O(1) | O(1)
Access by index | O(n)* | O(1)
* Some deque implementations support O(1) index access
Rule of thumb: If you need to add/remove from front, use deque!
Common Mistakes
1. Using List for Queue Operations
In Python, list.pop(0) is O(n)! Use collections.deque.
2. Forgetting It's Not Random Access
Deques optimize for ends, not middle. Don't index into the middle.
3. Overflow on Fixed-Size Deque
Check capacity before adding if using circular array.
FAQ
Q: Deque vs queue vs stack?
Queue: add right, remove left (FIFO). Stack: add right, remove right (LIFO). Deque: add/remove both ends (flexible).
Q: When should I use a deque?
When you need efficient operations at BOTH ends: sliding window, work stealing, BFS variants.
Q: Is Python list a deque?
No! Python list is O(n) for left operations. Use collections.deque for O(1).
Q: Pronunciation?
"Deck" (like deck of cards), not "dee-queue".
Summary
A deque is a double-ended queue that supports O(1) operations at both ends.
Key Takeaways:
- Add/remove from both left and right in O(1)
- Can act as both stack and queue
- Key for: sliding window, BFS variants, work stealing
- Don't use regular array for front operations!
- Implementations: circular array or doubly linked list
When you need flexibility at both ends, reach for a deque!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.