Stacks & Queues: LIFO, FIFO, and Monotonic Patterns
Go beyond basic push/pop — learn monotonic stacks for next-greater-element problems, queue-based BFS, and how to implement one with the other.
Stacks: Last In, First Out
A stack supports push (add to top) and pop (remove from top) in O(1). Stacks model function call chains, undo operations, expression evaluation, and backtracking. In Python, use a list as a stack — append() and pop() are both O(1) amortized.
Classic: Valid Parentheses
def is_valid_parentheses(s: str) -> bool:
"""Check if brackets are balanced and properly nested."""
stack = []
matching = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0Pattern: Monotonic Stack
A monotonic stack maintains elements in sorted order (either increasing or decreasing). It's the key to solving 'next greater element', 'largest rectangle in histogram', 'daily temperatures', and 'stock span' problems — all in O(n) time. The insight: when you find a larger element, pop all smaller elements from the stack because they'll never be useful again.
def next_greater_element(nums: list[int]) -> list[int]:
"""For each element, find the next greater element to its right."""
n = len(nums)
result = [-1] * n
stack = [] # Stores indices, values are decreasing
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""Days until a warmer temperature. 0 if no warmer day exists."""
n = len(temperatures)
result = [0] * n
stack = [] # Indices of days waiting for a warmer day
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_day = stack.pop()
result[prev_day] = i - prev_day
stack.append(i)
return resultMonotonic stack problems are among the most common 'medium' difficulty interview questions. The pattern is always: iterate through elements, pop from stack while the current element breaks the monotonic property, and record the relationship.
Largest Rectangle in Histogram
This classic problem uses a monotonic increasing stack. For each bar, we find the maximum rectangle that includes it by determining how far left and right it can extend. When we pop a bar, the current index is its right boundary and the new stack top is its left boundary.
def largest_rectangle_histogram(heights: list[int]) -> int:
"""Find the largest rectangular area in a histogram."""
stack = [] # Indices of bars in increasing height order
max_area = 0
for i, h in enumerate(heights + [0]): # Sentinel 0 forces final cleanup
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_areaQueues and Deques
Queues (FIFO) are essential for BFS, task scheduling, and sliding window maximum. Python's collections.deque provides O(1) operations on both ends. A deque can act as both a stack and a queue.
from collections import deque
def sliding_window_maximum(nums: list[int], k: int) -> list[int]:
"""Find maximum in each sliding window of size k."""
dq = deque() # Stores indices, values are decreasing
result = []
for i, num in enumerate(nums):
# Remove elements outside the window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements (they'll never be the max)
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result