Stacks, Queues, Heaps

These are order-focused data structures used to control how elements are added and removed:

• Stack (LIFO): Last-In-First-Out. Operations: push, pop, top/peek. Typical uses: recursion emulation, undo/redo, parsing.
• Queue (FIFO): First-In-First-Out. Operations: enqueue, dequeue, front/peek. Uses: BFS, task scheduling, rate limiting.
• Deque: Double-ended queue; push/pop on both ends. Uses: sliding window, monotonic queue.
• Heap (Priority Queue): Always extract min/max element in O(log n). Uses: Dijkstra, top-K, scheduling, median maintenance.

Time/Space (typical implementations):

• Stack/Queue/Deque: push/pop/enqueue/dequeue O(1) amortized, space O(n)
• Heap: insert/extract/top O(log n)/O(log n)/O(1), build-heap O(n), space O(n)

• Everywhere in algorithms: DFS uses a stack; BFS uses a queue; many greedy/graph problems use heaps.
• Enables common patterns: Parentheses validation, next-greater-element, sliding window maximum, k-way merge, shortest paths.
• Performance guarantees: Predictable O(1) or O(log n) operations enable scalable solutions.

Use a:

1. Stack when handling nested structures (parsing, parentheses), undo/redo, or when you need to backtrack (DFS, evaluate RPN).
2. Queue for level-order processing (BFS), multi-source expansion, producer-consumer pipelines.
3. Deque for problems where you push/pop from both ends or maintain a sliding window with monotonic property.
4. Heap/Priority Queue for extracting/extending the current best candidate: k largest/smallest, merge k sorted lists, Dijkstra, A*.

1. Monotonic Stack/Queue Maintain increasing/decreasing order to get next greater/smaller in O(n): daily temperatures, largest rectangle in histogram.

2. Sliding Window with Deque Track candidates for max/min in window in O(n) total: sliding window maximum.

3. Heaps for Selection/Aggregation

• Top-K: maintain a size-k heap.
• Kth smallest/largest: heap or quickselect.
• Median maintenance with two heaps (max-heap low, min-heap high).

4. Graphs and Scheduling

• Dijkstra/A* with min-heap.
• Event/task scheduling by priority or deadline.

5. Emulating Recursion Use an explicit stack to avoid recursion depth limits.

Stack-based:

• Valid parentheses, min stack, evaluate RPN
• Next greater element, daily temperatures
• Largest rectangle in histogram, trapping rain water (two pointers or stack)

Queue/Deque-based:

• BFS (shortest path in unweighted), level-order traversal
• Sliding window maximum/minimum with deque

Heap-based:

• Kth largest/smallest, top-K frequent elements
• Merge k sorted lists/arrays
• Dijkstra shortest path, prim's MST variant
• Meeting rooms (min-heap by end times)

• Monotonic logic off-by-one: Decide if equal elements should pop (strict vs non-strict monotonicity).
• Forgetting visited in BFS: Causes reprocessing and potential infinite loops in implicit graphs.
• Wrong heap type/comparator: Min-heap vs max-heap mistakes lead to wrong answers.
• Inefficient top-K: Sorting entire array is O(n log n); use size-k heap for O(n log k).
• Deque index/window drift: Remove indices that fall out of window before using them.
• Heap decrease-key: Many languages lack native decrease-key; push a new pair and lazily skip stale ones.

1. Nested or backtracking? → Stack
2. Level-order or shortest in steps? → Queue (BFS)
3. Sliding window max/min? → Monotonic deque
4. Top-K / Kth / streaming? → Heap (size-k or two-heaps)
5. Greedy expansion by best score? → Priority queue
6. Avoid recursion depth? → Explicit stack