Stack and Queue Patterns for Coding Interviews
Monotonic stacks, BFS with queues, expression evaluation — the essential stack and queue patterns for interviews.
Stacks and queues are fundamental, but knowing when to apply them in interviews is a different skill from knowing how they work. Here are the high-value patterns that show up repeatedly.
Stack Patterns
Parentheses Matching
Valid Parentheses: push opening brackets, pop on closing brackets and check for matches. Empty stack at the end means valid. Extends to Minimum Remove to Make Valid Parentheses (stack identifies unmatched brackets) and Longest Valid Parentheses (stack of indices tracks valid substrings).
The core algorithm uses a stack to track unmatched opening brackets. When a closing bracket appears, it must match the type of the bracket at the top of the stack. If the stack is empty when encountering a closing bracket, or if the types don't match, the string is invalid. After processing all characters, a valid string will have an empty stack.
def isValid(s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping: # Closing bracket
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else: # Opening bracket
stack.append(char)
return not stack
Monotonic Stack
Maintains elements in strictly increasing or decreasing order. When a new element violates the property, pop until restored. Answers "next greater/smaller element" queries in O(n). The key insight is that by maintaining monotonicity, we can efficiently find relationships between elements without nested loops.
Next Greater Element I: Decreasing stack. For each element, pop everything smaller -- those popped elements have found their next greater (the current element). This pattern solves problems where you need to find the next element with a certain property for each element in an array.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # Decreasing stack of indices
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
Daily Temperatures: Decreasing stack of indices. When a warmer day appears, popped indices get their answer as the index difference. This is essentially the same as Next Greater Element but returns distances instead of values.
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # Decreasing stack of indices
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
answer[idx] = i - idx
stack.append(i)
return answer
Largest Rectangle in Histogram: Increasing stack of indices. When a shorter bar appears, pop taller bars and calculate rectangles using the current index and new stack top as boundaries. This technique also solves Maximal Rectangle. The key is that each popped bar forms a rectangle with height equal to its own height and width determined by the distance between the current index and the index after the new top of the stack.
def largestRectangleArea(heights):
stack = []
max_area = 0
heights.append(0) # Sentinel value to clear stack
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
Expression Evaluation
Basic Calculator II (no parentheses, +, -, _, /): Track the previous operator. On encountering a new operator, apply the previous one. For +/-, push to stack. For _,/, pop, compute, push result. Sum the stack at the end. The algorithm processes the string character by character, building numbers and applying operators based on precedence.
def calculate(s: str) -> int:
stack = []
num = 0
op = '+'
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
if (not char.isdigit() and char != ' ') or i == len(s) - 1:
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
elif op == '/':
stack.append(int(stack.pop() / num))
op = char
num = 0
return sum(stack)
Basic Calculator (with parentheses): Push current result and sign on open-paren, reset, pop and combine on close-paren. This approach uses recursion in an iterative form by using the stack to save state when entering parentheses.
def calculate(s: str) -> int:
stack = []
result = 0
num = 0
sign = 1
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == '+':
result += sign * num
num = 0
sign = 1
elif char == '-':
result += sign * num
num = 0
sign = -1
elif char == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
result += sign * num
num = 0
result *= stack.pop() # Previous sign
result += stack.pop() # Previous result
return result + sign * num
Min Stack
Stack that supports O(1) min retrieval. Maintain a parallel stack tracking the minimum at each level. Push the min of the new element and current minimum alongside each push. This design ensures that for every element in the main stack, we know the minimum value in the stack up to that point.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
else:
self.min_stack.append(self.min_stack[-1])
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
Queue Patterns
BFS Template
Queues power BFS: initialize with starting nodes, mark visited, process each by adding unvisited neighbors. Track distance by processing layer by layer (record queue size at each iteration). This template works for trees, graphs, and grid problems.
Key problems: Word Ladder, Rotting Oranges (multi-source), Shortest Path in Binary Matrix. See the graph algorithms cheatsheet for more.
Here's a generic BFS template for grid problems:
from collections import deque
def bfs_grid(grid, start):
rows, cols = len(grid), len(grid[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = deque([start])
visited = set([start])
distance = 0
while queue:
# Process level by level
level_size = len(queue)
for _ in range(level_size):
r, c = queue.popleft()
# Process current cell
# (e.g., check if it's the target)
# Explore neighbors
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in visited and
grid[nr][nc] != 0): # Some condition
visited.add((nr, nc))
queue.append((nr, nc))
distance += 1
return -1 # If target not found
Priority Queue (Heap)
Always dequeues the min/max element. O(log n) insert and extract. Priority queues are essential for problems requiring repeated access to extreme values.
Merge K Sorted Lists: Min-heap of size K. Extract minimum, add its next pointer. O(n log K). The heap stores the current node from each list, allowing us to always pick the smallest available element.
import heapq
from typing import List, Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
# Push first node of each list into heap
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Kth Largest Element: Min-heap of size K. After processing all elements, the top is the Kth largest. This approach is more efficient than sorting when K is much smaller than N.
import heapq
def findKthLargest(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
Find Median from Data Stream: Max-heap for lower half, min-heap for upper half. Balance sizes to differ by at most 1. Median is from the larger heap's top. This two-heap approach maintains the invariant that all elements in the max-heap are less than or equal to all elements in the min-heap.
import heapq
class MedianFinder:
def __init__(self):
self.max_heap = [] # Lower half (invert values for max-heap)
self.min_heap = [] # Upper half
def addNum(self, num: int) -> None:
# Add to appropriate heap
if not self.max_heap or num <= -self.max_heap[0]:
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
# Balance heaps
if len(self.max_heap) > len(self.min_heap) + 1:
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
elif len(self.min_heap) > len(self.max_heap):
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def findMedian(self) -> float:
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0]) / 2
else:
return -self.max_heap[0]
Task Scheduler: Max-heap processes the most frequent task. After processing, cooldown queue holds tasks until they can re-enter the heap. This approach maximizes CPU utilization by always scheduling the most frequent available task.
import heapq
from collections import Counter, deque
def leastInterval(tasks, n):
count = Counter(tasks)
max_heap = [-cnt for cnt in count.values()]
heapq.heapify(max_heap)
time = 0
queue = deque() # (next_available_time, count)
while max_heap or queue:
time += 1
if max_heap:
cnt = heapq.heappop(max_heap) + 1 # +1 because we use negative counts
if cnt < 0: # If tasks remain
queue.append((time + n, cnt))
if queue and queue[0][0] == time:
heapq.heappush(max_heap, queue.popleft()[1])
return time
Choosing the Right Tool
Stack: Nesting, matching, "most recent" context. Parentheses, next greater element, DFS. Use a stack when you need to process elements in LIFO (Last-In-First-Out) order, particularly when dealing with recursive structures, backtracking, or when you need to remember the most recent element to compare with current elements.
Queue: Processing in order, BFS, level-by-level traversal. Use a queue when you need FIFO (First-In-First-Out) processing, such as when handling requests in order, traversing trees/graphs level by level, or implementing caches with LRU (Least Recently Used) eviction policies.
Priority queue: Repeatedly extracting min/max. Top K, merging sorted structures, scheduling. Use a priority queue when you need to repeatedly access the smallest or largest element, especially when the set of elements changes dynamically and you need efficient updates.
Practice Problems
Stack:
- Valid Parentheses
- Min Stack
- Daily Temperatures
- Largest Rectangle in Histogram
- Basic Calculator II
Queue/BFS: 6. Rotting Oranges 7. Binary Tree Level Order Traversal
Priority Queue: 8. Kth Largest Element in an Array 9. Merge K Sorted Lists 10. Find Median from Data Stream 11. Task Scheduler
Explore problems by company on the CodeJeet dashboard. Monotonic stack is popular at Amazon and Google; priority queues at Meta.
To master these patterns, implement each algorithm from scratch without looking at the code examples. Start with the basic versions, then tackle the variations. For example, after implementing Valid Parentheses, try Minimum Remove to Make Valid Parentheses. After mastering Next Greater Element, try the circular array version. The key is to understand the underlying principles so you can adapt them to new problems.