- Apply stacks to browser history, infix-to-postfix conversion, next greater element
- Use queues for BFS shortest path, rate limiting, level-order traversal
- Implement queue with stacks and stack with queues to understand trade-offs
Stack and Queue Applications
Stacks and queues aren't just theory. They solve real problems.
Stack: Browser History
Your browser's back button. How does it work?
Each page you visit is pushed onto a stack. Back button pops.
back_stack = []
forward_stack = []
current_page = "home"
def visit(page):
global current_page
back_stack.append(current_page)
current_page = page
forward_stack.clear() # Clear forward history
def go_back():
global current_page
if back_stack:
forward_stack.append(current_page)
current_page = back_stack.pop()
def go_forward():
global current_page
if forward_stack:
back_stack.append(current_page)
current_page = forward_stack.pop()
visit("page1")
visit("page2")
visit("page3")
print(current_page) # page3
go_back()
print(current_page) # page2
go_back()
print(current_page) # page1
go_forward()
print(current_page) # page2
Two stacks: one for back, one for forward. Simple and effective.
Stack: Infix to Postfix Conversion
Convert infix expressions to postfix (Reverse Polish Notation).
Infix: 3 + 4 * 2
Postfix: 3 4 2 * +
Why? Postfix is easier to evaluate (no parentheses, no operator precedence).
def infix_to_postfix(expr):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
output = []
for token in expr.split():
if token.isdigit():
output.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # Remove '('
else: # Operator
while (stack and stack[-1] != '(' and
precedence.get(stack[-1], 0) >= precedence[token]):
output.append(stack.pop())
stack.append(token)
while stack:
output.append(stack.pop())
return ' '.join(output)
print(infix_to_postfix("3 + 4 * 2")) # "3 4 2 * +"
print(infix_to_postfix("( 3 + 4 ) * 2")) # "3 4 + 2 *"
Push operators based on precedence. Pop when you find higher precedence.
Stack: Tower of Hanoi
Classic puzzle. Move disks from one peg to another. Smaller disk on larger only.
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C
Recursion uses call stack implicitly. You could implement with explicit stack too.
Queue: Request Queue (Rate Limiting)
Limit requests per second. Track recent requests in a queue.
from collections import deque
import time
class RateLimiter:
def __init__(self, max_requests, time_window):
self.max_requests = max_requests
self.time_window = time_window
self.requests = deque()
def allow_request(self):
now = time.time()
# Remove old requests outside time window
while self.requests and self.requests[0] < now - self.time_window:
self.requests.popleft()
if len(self.requests) < self.max_requests:
self.requests.append(now)
return True
return False
limiter = RateLimiter(5, 1) # 5 requests per second
for i in range(10):
if limiter.allow_request():
print(f"Request {i+1}: Allowed")
else:
print(f"Request {i+1}: Denied")
time.sleep(0.1)
Queue tracks request timestamps. Remove old ones, check if under limit.
Queue: Shortest Path (BFS)
Find shortest path in an unweighted graph.
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = set([start])
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
path = shortest_path(graph, 'A', 'F')
print(path) # ['A', 'C', 'F'] or ['A', 'B', 'E', 'F']
BFS guarantees shortest path in unweighted graphs. Queue explores level by level.
Both: Implement Queue with Stacks
Can you implement a queue using two stacks?
class QueueWithStacks:
def __init__(self):
self.stack_in = []
self.stack_out = []
def enqueue(self, item):
self.stack_in.append(item)
def dequeue(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
if not self.stack_out:
raise Exception("Queue is empty")
return self.stack_out.pop()
q = QueueWithStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 1
print(q.dequeue()) # 2
q.enqueue(4)
print(q.dequeue()) # 3
print(q.dequeue()) # 4
Push to stack_in. Pop from stack_out. When stack_out is empty, transfer from stack_in (reversing order).
Enqueue: O(1). Dequeue: O(1) amortized (occasional O(n) transfer).
Both: Implement Stack with Queues
Can you implement a stack using two queues?
from collections import deque
class StackWithQueues:
def __init__(self):
self.queue_main = deque()
self.queue_temp = deque()
def push(self, item):
self.queue_temp.append(item)
while self.queue_main:
self.queue_temp.append(self.queue_main.popleft())
self.queue_main, self.queue_temp = self.queue_temp, self.queue_main
def pop(self):
if not self.queue_main:
raise Exception("Stack is empty")
return self.queue_main.popleft()
s = StackWithQueues()
s.push(1)
s.push(2)
s.push(3)
print(s.pop()) # 3
print(s.pop()) # 2
Push new item to temp, then move all from main to temp. Swap queues. Now newest item is at front.
Push: O(n). Pop: O(1). Trade-off.
Stack: Next Greater Element
For each element in an array, find the next greater element to the right.
def next_greater_element(arr):
stack = []
result = [-1] * len(arr)
for i in range(len(arr) - 1, -1, -1):
while stack and stack[-1] <= arr[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(arr[i])
return result
print(next_greater_element([4, 5, 2, 10, 8]))
# [5, 10, 10, -1, -1]
Scan from right. Maintain stack of potential "next greater" candidates. Pop smaller elements.
O(n). Each element pushed and popped once.
Queue: Level Order Traversal with Level Info
Print tree level by level, showing each level separately.
from collections import deque
def level_order_levels(root):
if not root:
return
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print(level)
Process all nodes at current level before moving to next. Track level size.
Stack: Stock Span Problem
For each day, find how many consecutive days before (including today) had stock price ≤ today's price.
def stock_span(prices):
stack = []
spans = []
for i, price in enumerate(prices):
span = 1
while stack and prices[stack[-1]] <= price:
stack.pop()
if stack:
span = i - stack[-1]
else:
span = i + 1
spans.append(span)
stack.append(i)
return spans
print(stock_span([100, 80, 60, 70, 60, 75, 85]))
# [1, 1, 1, 2, 1, 4, 6]
Stack stores indices of days with unresolved spans. Pop when current price > previous.
O(n). Each element pushed and popped once.
The Pattern
Stacks:
- Reversal: Undo, DFS, expression evaluation
- Nesting: Balanced parentheses, HTML tags
- Monotonic stacks: Next greater/smaller element, stock span
Queues:
- Ordering: Task scheduling, buffering
- Level processing: BFS, level-order traversal
- Sliding windows: Maintain elements in window
Understanding these applications means recognizing when stack (LIFO) or queue (FIFO) fits your problem.
Master stacks and queues, and you'll solve ordering, nesting, and traversal problems efficiently.