Stack
LIFO (Last In, First Out). Think: a stack of plates.
# Python list as stack
stack = []
stack.append(1) # push: O(1)
stack.append(2)
stack.append(3)
print(stack[-1]) # peek: O(1) → 3
print(stack.pop()) # pop: O(1) → 3
print(stack) # [1, 2]
# Class implementation
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack underflow")
return self._items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._items[-1]
def is_empty(self):
return len(self._items) == 0
def size(self):
return len(self._items)
Classic Stack Problems
Valid Parentheses
def is_valid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in '([{':
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
print(is_valid("()[]{}")) # True
print(is_valid("([)]")) # False
print(is_valid("{[]}")) # True
Min Stack
class MinStack:
"""Stack with O(1) min retrieval"""
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
min_val = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(min_val)
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
ms.push(1)
print(ms.get_min()) # 1
ms.pop()
print(ms.get_min()) # 3
Evaluate Reverse Polish Notation
def eval_rpn(tokens):
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]
print(eval_rpn(["2", "1", "+", "3", "*"])) # 9 = (2+1)*3
print(eval_rpn(["4", "13", "5", "/", "+"])) # 6 = 4+13/5
Monotonic Stack
A stack that maintains elements in increasing or decreasing order.
Next Greater Element
def next_greater(nums):
"""For each element, find the next greater element to the right"""
n = len(nums)
result = [-1] * n
stack = [] # stores indices, decreasing values (monotonic decreasing)
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
print(next_greater([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]
Largest Rectangle in Histogram
def largest_rectangle(heights):
"""Monotonic stack — O(n)"""
stack = [] # indices of bars (increasing heights)
max_area = 0
heights = heights + [0] # sentinel
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
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
Queue
FIFO (First In, First Out). Think: a waiting line.
from collections import deque
# deque-based queue (O(1) enqueue and dequeue)
queue = deque()
queue.append(1) # enqueue: O(1)
queue.append(2)
queue.append(3)
print(queue[0]) # peek front: O(1) → 1
print(queue.popleft()) # dequeue: O(1) → 1
print(queue) # deque([2, 3])
Queue Class
from collections import deque
class Queue:
def __init__(self):
self._items = deque()
def enqueue(self, item):
self._items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self._items.popleft()
def front(self):
return self._items[0]
def is_empty(self):
return len(self._items) == 0
def size(self):
return len(self._items)
BFS with Queue
from collections import deque
def bfs(graph, start):
"""Breadth-First Search using queue"""
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
Circular Queue
class CircularQueue:
def __init__(self, capacity):
self.data = [None] * capacity
self.capacity = capacity
self.head = self.tail = 0
self.size = 0
def enqueue(self, val):
if self.size == self.capacity:
raise OverflowError("Queue is full")
self.data[self.tail] = val
self.tail = (self.tail + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.size == 0:
raise IndexError("Queue is empty")
val = self.data[self.head]
self.head = (self.head + 1) % self.capacity
self.size -= 1
return val
Priority Queue (Heap)
import heapq
# Min-heap (default in Python)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 1)
print(heapq.heappop(pq)) # 1
print(heapq.heappop(pq)) # 1
print(heapq.heappop(pq)) # 3
# Max-heap: negate values
max_pq = []
for val in [3, 1, 4, 1, 5, 9]:
heapq.heappush(max_pq, -val)
print(-heapq.heappop(max_pq)) # 9
# K Largest Elements
def k_largest(nums, k):
return heapq.nlargest(k, nums)
def k_smallest(nums, k):
return heapq.nsmallest(k, nums)
Exercises
Exercise 1: Daily Temperatures
For each day, find how many days until a warmer temperature.
Solution:
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = [] # indices
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
idx = stack.pop()
result[idx] = i - idx
stack.append(i)
return result
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
Exercise 2: Task Scheduler
Given tasks with cooldown n, find minimum time to complete all tasks.
Solution:
from collections import Counter
def least_interval(tasks, n):
freq = Counter(tasks)
max_freq = max(freq.values())
max_count = sum(1 for v in freq.values() if v == max_freq)
# Formula: (max_freq - 1) * (n + 1) + max_count
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)
print(least_interval(list("AAABBB"), 2)) # 8
print(least_interval(list("AAABBB"), 0)) # 6