Module Review: Stacks & Queues
You’ve mastered the strict rules of LIFO and FIFO. You can now build calculators, process browser history, and optimize sliding windows.
1. Key Takeaways
- The Difference: Stack = LIFO (Plates). Queue = FIFO (Coffee Line).
- Performance: All operations (Push, Pop, Enqueue, Dequeue) must be O(1).
- Hardware: Stacks power recursion and function calls. Queues power task scheduling and buffers.
- Patterns:
- Monotonic Stack: Solves “Next Greater Element” in O(N).
- Monotonic Deque: Solves “Sliding Window Max” in O(N).
- Two Stacks: Can implement a MinStack or a Queue.
2. Cheat Sheet
| Operation | Stack (Array/List) | Queue (List) | Queue (Array) | Deque |
|---|---|---|---|---|
| Add | Push (Top) O(1) | Enqueue (Back) O(1) | Enqueue (Back) O(1)* | AddFirst/Last O(1) |
| Remove | Pop (Top) O(1) | Dequeue (Front) O(1) | Dequeue (Front) O(N)** | RemoveFirst/Last O(1) |
| Access | Peek (Top) O(1) | Peek (Front) O(1) | Peek (Front) O(1) | PeekFirst/Last O(1) |
(*) Array Queue is O(1) amortized. () Array Queue Dequeue is O(N) unless implemented as a **Ring Buffer (Circular Queue), then O(1).
3. Interactive Flashcards
Test your knowledge. Click to flip.
What data structure is used for Breadth-First Search (BFS)?
Queue (FIFO).
What data structure is used for Depth-First Search (DFS) / Recursion?
Stack (LIFO).
Why is `java.util.Stack` deprecated?
It is synchronized (slow) and inherits from Vector. Use `ArrayDeque` instead.
What problem does a Monotonic Stack solve efficiently?
Finding the Next Greater/Smaller Element for every item in an array (O(N)).
What is the Shunting-yard algorithm used for?
Converting Infix expressions (3+4) to Postfix (3 4 +) for easier evaluation.
4. Next Steps
Next Module: Trees - Moving from linear structures to hierarchical ones.
DSA Glossary
Module Review: Stacks & Queues
[!NOTE] This module explores the core principles of Module Review: Stacks & Queues, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.
1. Practice in the Vault
Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.