Stack and Queue Fundamentals
A stack is LIFO (last-in, first-out): push adds to the top, pop removes from the top. A queue is FIFO (first-in, first-out): enqueue adds to the back, dequeue removes from the front. In Python: use a list as a stack (append/pop), and collections.deque as a queue (append/popleft). Both operations are O(1). Stacks appear in: DFS, expression evaluation, undo operations, parentheses matching. Queues appear in: BFS, task scheduling, producer/consumer patterns.
from collections import deque
# Stack (list)
stack = []
stack.append(1) # push
stack.append(2)
top = stack.pop() # 2
# Queue (deque)
queue = deque()
queue.append(1) # enqueue
queue.append(2)
front = queue.popleft() # 1, O(1)
# Deque (double-ended): add/remove from both ends
dq = deque()
dq.appendleft(0) # add to front
dq.append(3) # add to back
dq.popleft() # remove from front
dq.pop() # remove from back
Pattern 1: Valid Parentheses
def is_valid(s: str) -> bool:
stack = []
pairs = {")": "(", "}": "{", "]": "["}
for char in s:
if char in "({[":
stack.append(char)
elif char in ")}]":
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
# Extension: minimum add to make valid — count unmatched open and close
def min_add_to_make_valid(s: str) -> int:
open_count = close_count = 0
for char in s:
if char == "(":
open_count += 1
elif open_count > 0:
open_count -= 1
else:
close_count += 1
return open_count + close_count
Pattern 2: Monotonic Stack (Next Greater Element)
A monotonic stack maintains elements in sorted order (increasing or decreasing). When a new element breaks the order, pop elements from the stack — those popped elements have found their “next greater” or “previous smaller” element. This solves a class of problems that would otherwise require O(n^2) nested loops.
# Next Greater Element: for each element, find the next larger element to its right
def next_greater_element(nums: list) -> list:
result = [-1] * len(nums)
stack = [] # stores indices, values in stack are decreasing
for i, num in enumerate(nums):
while stack and nums[stack[-1]] int:
stack = [] # monotonic increasing stack of indices
max_area = 0
heights.append(0) # sentinel to flush remaining stack
for i, h in enumerate(heights):
start = i
while stack and heights[stack[-1]] > h:
idx = stack.pop()
width = i - (stack[-1] + 1 if stack else 0)
max_area = max(max_area, heights[idx] * width)
start = idx
stack.append(start)
return max_area
# Daily Temperatures: how many days until a warmer day?
def daily_temperatures(temps: list) -> list:
result = [0] * len(temps)
stack = [] # indices of days waiting for a warmer day
for i, temp in enumerate(temps):
while stack and temps[stack[-1]] < temp:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
Pattern 3: Stack for Expression Evaluation
# Evaluate Reverse Polish Notation: ["2","1","+","3","*"] => 9
def eval_rpn(tokens: list) -> int:
stack = []
ops = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"*": lambda a, b: a * b,
"/": lambda a, b: int(a / b), # truncate toward zero
}
for token in tokens:
if token in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[token](a, b))
else:
stack.append(int(token))
return stack[0]
# Basic Calculator (with +, -, parentheses)
def calculate(s: str) -> int:
stack = []
result = num = 0
sign = 1
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char in "+-":
result += sign * num
num = 0
sign = 1 if char == "+" else -1
elif char == "(":
stack.append(result)
stack.append(sign)
result, sign = 0, 1
elif char == ")":
result += sign * num
num = 0
result *= stack.pop() # sign before parenthesis
result += stack.pop() # result before parenthesis
return result + sign * num
Design: Implement Queue Using Two Stacks
class MyQueue:
def __init__(self):
self.inbox = [] # for push operations
self.outbox = [] # for pop/peek operations
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
Common Stack/Queue Interview Problems
- Parentheses: Valid Parentheses, Minimum Remove to Make Valid, Longest Valid Parentheses
- Monotonic stack: Next Greater Element (I and II circular), Largest Rectangle in Histogram, Trapping Rain Water, Daily Temperatures
- Expression: Evaluate RPN, Basic Calculator (I, II, III), Decode String
- Design: Min Stack, Queue using Two Stacks, Stack using Two Queues
- BFS (queue): Level Order Traversal, Rotting Oranges, Word Ladder, 01 Matrix
Frequently Asked Questions
What is a monotonic stack and when do you use it?
A monotonic stack maintains elements in sorted order (either strictly increasing or strictly decreasing from bottom to top). When a new element violates the order, elements are popped from the stack before pushing the new one. Each popped element has found its answer — the element that caused the pop is the "next greater element" (for a decreasing stack) or "next smaller element" (for an increasing stack). This achieves O(n) time for problems that would otherwise require O(n^2) nested loops. Use a decreasing monotonic stack for: Next Greater Element, Daily Temperatures, Trapping Rain Water, Largest Rectangle in Histogram. Use an increasing monotonic stack for: Next Smaller Element, Sum of Subarray Minimums. Recognition signal: the problem asks for the nearest element satisfying some comparison for every element in the array.
How do you implement a min stack (constant-time minimum retrieval)?
A Min Stack supports push, pop, top, and getMin — all in O(1) time. The naive approach (scanning for minimum on getMin) is O(n). The O(1) approach uses an auxiliary stack that tracks the minimum at each state: when pushing a value, also push the minimum of (value, current min) onto the min stack. When popping, pop both stacks. getMin returns the top of the min stack. Each position in the main stack has a corresponding min value representing the minimum of all elements at or below that position. Example: push 5 → min stack [5]; push 3 → min stack [5, 3]; push 7 → min stack [5, 3, 3]; getMin returns 3; pop → min stack [5, 3]; getMin returns 3; pop → min stack [5]; getMin returns 5.
How is BFS implemented using a queue and what problems does it solve?
BFS (Breadth-First Search) uses a queue to process nodes level by level. Algorithm: initialize with the starting node in the queue and a visited set; while the queue is not empty, dequeue a node, process it, and enqueue all unvisited neighbors. Key property: BFS visits nodes in order of their distance from the start — the first time a node is reached is via the shortest path (for unweighted graphs). Problems BFS solves: (1) Shortest path in unweighted graphs or grids — Word Ladder, 01 Matrix, Shortest Path in Binary Matrix. (2) Level-order tree traversal — Binary Tree Level Order Traversal. (3) Multi-source BFS — start BFS from multiple sources simultaneously; Rotting Oranges, Walls and Gates. (4) Reachability — Number of Islands, Number of Connected Components. BFS requires O(V) extra space for the queue; DFS requires O(H) for the call stack (H = tree height).
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “What is a monotonic stack and when do you use it?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “A monotonic stack maintains elements in sorted order (either strictly increasing or strictly decreasing from bottom to top). When a new element violates the order, elements are popped from the stack before pushing the new one. Each popped element has found its answer — the element that caused the pop is the “next greater element” (for a decreasing stack) or “next smaller element” (for an increasing stack). This achieves O(n) time for problems that would otherwise require O(n^2) nested loops. Use a decreasing monotonic stack for: Next Greater Element, Daily Temperatures, Trapping Rain Water, Largest Rectangle in Histogram. Use an increasing monotonic stack for: Next Smaller Element, Sum of Subarray Minimums. Recognition signal: the problem asks for the nearest element satisfying some comparison for every element in the array.” } }, { “@type”: “Question”, “name”: “How do you implement a min stack (constant-time minimum retrieval)?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “A Min Stack supports push, pop, top, and getMin — all in O(1) time. The naive approach (scanning for minimum on getMin) is O(n). The O(1) approach uses an auxiliary stack that tracks the minimum at each state: when pushing a value, also push the minimum of (value, current min) onto the min stack. When popping, pop both stacks. getMin returns the top of the min stack. Each position in the main stack has a corresponding min value representing the minimum of all elements at or below that position. Example: push 5 → min stack [5]; push 3 → min stack [5, 3]; push 7 → min stack [5, 3, 3]; getMin returns 3; pop → min stack [5, 3]; getMin returns 3; pop → min stack [5]; getMin returns 5.” } }, { “@type”: “Question”, “name”: “How is BFS implemented using a queue and what problems does it solve?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “BFS (Breadth-First Search) uses a queue to process nodes level by level. Algorithm: initialize with the starting node in the queue and a visited set; while the queue is not empty, dequeue a node, process it, and enqueue all unvisited neighbors. Key property: BFS visits nodes in order of their distance from the start — the first time a node is reached is via the shortest path (for unweighted graphs). Problems BFS solves: (1) Shortest path in unweighted graphs or grids — Word Ladder, 01 Matrix, Shortest Path in Binary Matrix. (2) Level-order tree traversal — Binary Tree Level Order Traversal. (3) Multi-source BFS — start BFS from multiple sources simultaneously; Rotting Oranges, Walls and Gates. (4) Reachability — Number of Islands, Number of Connected Components. BFS requires O(V) extra space for the queue; DFS requires O(H) for the call stack (H = tree height).” } } ] }