Stacks & Queues

Stacks and queues are the two fundamental access-pattern data structures. Stack (LIFO) is the natural structure for problems with 'undo' or 'matching' semantics — parentheses, expression evaluation, and DFS call stack all use LIFO. Queue (FIFO) is the natural structure for level-by-level processing — BFS, task scheduling, and sliding windows. The monotonic stack is the most powerful interview pattern: maintain a stack where elements are in sorted order to find the next-greater or next-smaller element in O(n). Understanding Stacks A stack is a LIFO (Last In, First Out) data structure. Think of a stack of plates — you can only add or remove from the top. Stacks are used for tracking state, backtracking, and expression evaluation. Why stacks are interview favorites: They model function call stacks (recursion) They solve parentheses matching, expression evaluation Monotonic stacks solve "next greater/smaller" problems efficiently Key patterns: Matching pairs: parentheses, brackets, HTML tags Monotonic stack: maintain increasing/decreasing order to find next greater/smaller element in O(n) Expression evaluation: convert infix to postfix, evaluate postfix Backtracking: undo operations (browser history, undo/redo) When to use a stack: "Find the nearest/next greater/smaller element" → Monotonic stack "Check if balanced/valid" → Regular stack "Evaluate expression" → Two stacks (operators operands) Stacks & Queues Stacks (LIFO) and Queues (FIFO) are foundational structures used in BFS, DFS, expression parsing, and many interview problems. Monotonic Stack Pattern A stack that maintains elements in sorted order. Used for 'next greater/smaller element' problems. Min Stack Key Problems #20 Valid Parentheses, #155 Min Stack, #739 Daily Temperatures #84 Largest Rectangle in Histogram, #42 Trapping Rain Water Interview Tip "When I see 'next greater element' or 'nearest smaller', I immediately think monotonic stack. It converts O(n²) brute force to O(n)." Java Implementation: