Why This Matters
Stacks and queues are simple, but they change the order in which a program thinks. That order controls traversal, undo, parsing, scheduling, and search.
Decision Rule
Use a stack when the most recent unfinished item should be handled next. Use a queue when earlier arrivals must be handled before later arrivals.
Comparison Table
| Feature | Stack | Queue |
|---|---|---|
| Order | last in, first out | first in, first out |
| Main operations | push, pop | enqueue, dequeue |
| Common traversal | DFS | BFS |
| Good for | undo, recursion simulation, backtracking | level order, shortest unweighted path, task arrival order |
| Python default | list.append, list.pop | collections.deque |
Worked Example
If neighbors A, B, and C are discovered from S, a queue processes A before B before C. That preserves level order for BFS.
A stack processes C first if it was pushed last. That dives down one branch before returning, which is the behavior DFS needs.
Common Mistakes
| Mistake | Correction |
|---|---|
Using a Python list as a queue with pop(0). | pop(0) shifts elements. Use collections.deque. |
| Treating BFS and DFS as interchangeable. | BFS preserves distance layers; DFS preserves depth-first exploration. |
| Forgetting that recursion uses a stack. | Recursive DFS stores unfinished calls on the call stack. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which structure is LIFO? | Stack. |
| Which one is used for BFS? | Queue. |
Why is deque.popleft() preferred for queues in Python? | It avoids shifting all remaining elements. |
Exercises
- Beginner: Simulate stack pushes
1,2,3and two pops. - Beginner: Simulate queue enqueues
1,2,3and two dequeues. - Beginner: Name one real feature that naturally uses a stack.
- Intermediate: Convert recursive DFS to iterative DFS using a stack.
- Intermediate: Use a queue to print tree nodes level by level.
- Challenge: Explain how a monotonic stack differs from an ordinary stack.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Graph search materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/