Why This Matters
collections.deque is the Python queue structure you actually want for BFS and many sliding window tasks. It gives O(1) appends and pops from both ends.
Core Idea
Use deque when both ends matter.
| Method | Role |
|---|---|
append | push right |
appendleft | push left |
pop | remove right |
popleft | remove left |
maxlen | keep a bounded recent history |
Non-Example or Failure Mode
list.pop(0) removes the first item but shifts the whole list. In BFS, that can turn a clean O(V + E) traversal into much slower code.
Runnable Drill
deque BFS and sliding window drill
Output will appear here.
Common Mistakes
| Mistake | Correction |
|---|---|
Using list.pop(0) for BFS. | Use deque.popleft. |
| Forgetting to mark BFS nodes before enqueue. | Mark when appending so duplicates do not pile up. |
Using maxlen when old values still need explicit cleanup logic. | maxlen discards silently; use manual pops if you need to update sums/counts. |
Treating deque like a random-access list. | It is built for end operations, not indexed scans. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What does collections.deque optimize? | Appending and popping at both ends. |
| Example / non-example | Is deque the default BFS queue? | Yes. |
| Computation | What method removes the oldest queue item? | popleft. |
| Transfer | Why can maxlen help sliding window review? | It keeps only the most recent k items. |
Exercises
Beginner:
- Replace a list queue with
deque. - Use
appendleftandpopto model a double-ended buffer. - Track the last three values with
maxlen=3.
Intermediate:
- Implement level-order tree traversal with
deque. - Build a sliding-window maximum using a monotonic deque.
Challenge:
- Compare BFS runtime with
list.pop(0)anddeque.poplefton a large grid.
References
- Python documentation.
collections.deque: https://docs.python.org/3/library/collections.html#collections.deque - Python documentation. Queue module context: https://docs.python.org/3/library/queue.html