LIFO and FIFO data structures. Essential for expression evaluation, BFS, and monotonic stack problems.
Time
Push/Pop/Enqueue/Dequeue: O(1)
Space
O(n)
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Valid Parentheses | Easy | Google Amazon Meta |
| 2 | Min Stack | Medium | Amazon Microsoft Goldman Sachs |
| 3 | Daily Temperatures | Medium | Google Amazon Meta |
| 4 | Largest Rectangle in Histogram | Hard | Google Amazon Microsoft |
Stack: use for matching (parentheses), backtracking (DFS), undo operations
Queue: use for BFS, level-order traversal, task scheduling
Monotonic stack: maintains increasing/decreasing order for "next greater/smaller" problems
Priority Queue (Heap) is a queue where dequeue returns min/max element
