Stacks and queues are fundamental data structures that appear in 15-20% of coding interviews. The stack (LIFO) is essential for matching brackets, evaluating expressions, and maintaining state during recursion. The queue (FIFO) powers BFS, task scheduling, and sliding window operations. This guide covers the patterns and problems most commonly tested.
Pattern 1: Matching and Nesting
Valid Parentheses: given a string of brackets (){}[], determine if it is valid. Push opening brackets onto the stack. When encountering a closing bracket, pop the stack and check if it matches. If the stack is empty when popping, or the bracket types do not match, return false. If the stack is empty at the end, the string is valid. Time: O(N). Minimum Add to Make Parentheses Valid: count the minimum insertions needed. Track unmatched opening and closing brackets. For each “(“: push to stack (or increment open_count). For each “)”: if stack is non-empty, pop (matched). Else increment close_count. Answer: remaining stack size + close_count. Longest Valid Parentheses: find the length of the longest valid substring. Stack of indices. Push -1 as a base. For “(“: push index. For “)”: pop. If stack becomes empty, push current index as new base. Else, current_length = i – stack.top(). Track maximum. Remove Invalid Parentheses: BFS approach — try removing each bracket, check validity, continue until valid strings are found at the shallowest level.
Pattern 2: Maintaining State (Min Stack, Max Stack)
Min Stack: design a stack that supports push, pop, top, and getMin in O(1). Approach: maintain two stacks — the main stack and a min stack. The min stack top always holds the current minimum. On push(x): push x to main stack. If x <= min_stack.top() (or min stack is empty), also push x to min stack. On pop(): pop from main stack. If the popped value == min_stack.top(), also pop from min stack. getMin(): return min_stack.top(). Space: O(N) worst case (all elements are the same, every push adds to min stack). Optimization: store (value, count) in the min stack to handle duplicates without pushing each one. Max Stack: same idea with a max stack. Alternatively, maintain a stack of (value, current_max) tuples — each element stores the max at the time of its insertion. This is the cleanest implementation: push(x) pushes (x, max(x, stack.top().max)). getMax returns stack.top().max. These "design a data structure" problems test your ability to augment a standard structure with additional state to support new operations in O(1).
Pattern 3: Expression Evaluation
Basic Calculator: evaluate a string expression with +, -, (, ). Use a stack for nested parentheses. When encountering “(“: push the current result and sign to the stack, reset. When encountering “)”: pop the sign and previous result, combine. Process digits to form numbers. Apply the current sign on each number. Basic Calculator II: with +, -, *, / (no parentheses). Use a stack. Track the previous operator. When encountering a new operator or end of string: apply the previous operator. For + and -: push the number (with sign) to the stack. For * and /: pop the top, apply the operation, push the result. At the end, sum all stack elements. Reverse Polish Notation: evaluate postfix expressions. Push numbers. On operator: pop two operands, apply, push result. Straightforward stack application. The key insight for calculator problems: the stack handles operator precedence by delaying lower-precedence operations. Multiplication and division are applied immediately; addition and subtraction are pushed for later summation.
Pattern 4: Decode and Transform
Decode String: “3[a2[c]]” -> “accaccacc”. Use a stack of (current_string, repeat_count) pairs. When encountering a digit: build the number. When “[“: push (current_string, number) to stack, reset. When “]”: pop (prev_string, count), set current_string = prev_string + current_string * count. When letter: append to current_string. The stack handles nesting by saving and restoring context at each bracket level. Flatten Nested List Iterator: given a nested list (e.g., [[1,1],2,[1,1]]), iterate through all integers. Use a stack of iterators. Push the top-level iterator. hasNext(): while stack is non-empty: if top iterator has next element and it is an integer, return true. If it is a list, push an iterator for that list. If top iterator is exhausted, pop it. next(): return the integer found by hasNext(). Simplify Path: convert “/a/./b/../../c/” to “/c”. Split by “/”. Use a stack: push directory names, pop on “..”, ignore “.” and empty strings. Join remaining stack elements with “/”.
Pattern 5: Queue-Based BFS and Design
BFS uses a queue to explore level by level. Binary tree level-order traversal: push root to queue. While queue is non-empty: process all nodes at the current level (for loop over queue size), push their children. Each iteration of the outer loop processes one level. Zigzag level order: alternate left-to-right and right-to-left using a flag. Reverse the level list on odd levels. Implement Queue using Stacks: use two stacks. Push to stack1. For dequeue: if stack2 is empty, pop all from stack1 and push to stack2. Pop from stack2. Amortized O(1) per operation. Implement Stack using Queues: push to queue. For pop: dequeue all except the last element and re-enqueue them. The last element is the “top” of the stack. O(N) per pop. Design Circular Queue: fixed-size array with head and tail pointers. Enqueue: write at tail, advance tail = (tail + 1) % capacity. Dequeue: advance head = (head + 1) % capacity. Full: (tail + 1) % capacity == head. Empty: head == tail. These design problems test understanding of the underlying data structure mechanics.