Exercises: Stacks, Queues, and Beyond
These exercises progress from concept checks through increasingly challenging data structure problems. Type every solution yourself — don't copy-paste.
Difficulty Guide: - ⭐ Foundational (5-10 min each) - ⭐⭐ Intermediate (10-20 min each) - ⭐⭐⭐ Challenging (20-40 min each) - ⭐⭐⭐⭐ Advanced/Research (40+ min each)
Part A: Stack Fundamentals ⭐
A.1. Using the Stack class from this chapter, predict the output of the following code without running it. Then run it to verify.
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.pop())
print(s.peek())
s.push(40)
print(s.pop())
print(s.pop())
print(s.size())
A.2. Write a function reverse_list(items: list) -> list that uses a Stack to reverse a list. Do not use slicing, reversed(), or list.reverse().
print(reverse_list([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1]
print(reverse_list(["a", "b", "c"])) # ['c', 'b', 'a']
print(reverse_list([])) # []
A.3. Write a function is_palindrome_stack(text: str) -> bool that uses a stack to check whether a string is a palindrome (reads the same forwards and backwards). Ignore case and spaces.
print(is_palindrome_stack("racecar")) # True
print(is_palindrome_stack("hello")) # False
print(is_palindrome_stack("A man a plan a canal Panama")) # True
A.4. What happens if you call pop() on an empty stack? What happens if you call peek() on an empty stack? Write code that demonstrates both errors and handles them with try/except.
A.5. Trace the state of the stack after each operation. Draw the stack contents at each step.
s = Stack()
s.push("X")
s.push("Y")
s.pop()
s.push("Z")
s.push("W")
s.pop()
s.pop()
# What is left in the stack?
Part B: Queue Fundamentals ⭐
B.1. Using the Queue class from this chapter, predict the output of the following code without running it. Then run it to verify.
q = Queue()
q.enqueue("first")
q.enqueue("second")
q.enqueue("third")
print(q.dequeue())
print(q.front())
q.enqueue("fourth")
print(q.dequeue())
print(q.size())
B.2. Write a function interleave(q: Queue) -> Queue that takes a queue with an even number of elements and returns a new queue that interleaves the first half with the second half. Use only queue operations (enqueue, dequeue, size, is_empty) plus one temporary Queue; no converting to a list.
q = Queue()
for item in [1, 2, 3, 4, 5, 6]:
q.enqueue(item)
result = interleave(q)
# Dequeuing result front to back gives: 1, 4, 2, 5, 3, 6
Hint: move the first half into the temporary queue, then alternate dequeuing from the temporary queue and the original.
B.3. Write a function hot_potato(names: list[str], count: int) -> str that simulates the hot potato game. Players stand in a circle (modeled as a queue), and whoever is at the front of the queue holds the potato. The potato is passed count times; after count passes, the player now holding it is eliminated. Repeat until one player remains.
players = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
winner = hot_potato(players, 7)
print(f"Winner: {winner}") # Winner: Alice
(If you print each eliminated player, the order is Charlie, Bob, Eve, Diana.)
Hint: one pass means dequeuing the player at the front and enqueuing them at the back.
B.4. Explain why using list.pop(0) for a queue is problematic. What is its time complexity? What does collections.deque use instead, and why is it better?
B.5. Trace the state of the queue after each operation:
q = Queue()
q.enqueue("A")
q.enqueue("B")
q.dequeue()
q.enqueue("C")
q.enqueue("D")
q.dequeue()
q.dequeue()
# What is left in the queue?
Part C: Stack Applications ⭐⭐
C.1. Write a function decimal_to_binary(n: int) -> str that uses a stack to convert a non-negative integer to its binary representation.
Algorithm: repeatedly divide by 2, push remainders onto a stack, then pop all to form the binary string.
print(decimal_to_binary(42)) # "101010"
print(decimal_to_binary(10)) # "1010"
print(decimal_to_binary(0)) # "0"
print(decimal_to_binary(255)) # "11111111"
C.2. Extend the bracket matcher from the chapter so it reports ALL errors (not just the first one), with the position and type of each. Return a list of error messages. Use this recovery rule: when a closer doesn't match the top of the stack, record the mismatch, pop the opener anyway, and keep scanning. When the scan ends, report every opener still on the stack, oldest first.
errors = check_all_brackets("([)]{")
# Should report:
# Mismatched '[' at position 1 with ')' at position 2
# Mismatched '(' at position 0 with ']' at position 3
# Unmatched '{' at position 4
Notice that one misplaced ) produced two mismatch reports. That cascade is why many real tools stop at the first bracket error or use smarter recovery. Can you design a rule that reports only one error for this input?
C.3. Write a function evaluate_postfix(expression: str) -> float that evaluates a mathematical expression in postfix notation (also called Reverse Polish Notation). Tokens are separated by spaces. Support +, -, *, /.
print(evaluate_postfix("3 4 +")) # 7.0
print(evaluate_postfix("5 1 2 + 4 * + 3 -")) # 14.0
print(evaluate_postfix("10 2 /")) # 5.0
Algorithm: scan left to right. If a token is a number, push it. If it's an operator, pop two operands, apply the operator, push the result.
C.4. Write a function check_html_tags(html: str) -> tuple[bool, str] that uses a stack to validate that HTML opening and closing tags are properly matched. Only consider simple tags like <div>, </div>, <p>, </p>, etc. Ignore self-closing tags and attributes.
print(check_html_tags("<div><p>Hello</p></div>")) # (True, "Valid")
print(check_html_tags("<div><p>Hello</div></p>")) # (False, "Mismatched ...")
print(check_html_tags("<div><p>Hello</p>")) # (False, "Unclosed <div>")
C.5. Write a BrowserHistory class that uses two stacks to implement back/forward navigation. Methods: visit(url), back(), forward(), current().
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("python.org")
browser.visit("github.com")
print(browser.current()) # github.com
browser.back()
print(browser.current()) # python.org
browser.back()
print(browser.current()) # google.com
browser.forward()
print(browser.current()) # python.org
browser.visit("stackoverflow.com")
browser.forward() # Nothing to go forward to
print(browser.current()) # stackoverflow.com
Part D: Queue Applications ⭐⭐
D.1. Write a PrinterQueue class that simulates a shared printer. Methods: submit(owner, document, pages), process_next(), status(). The printer processes jobs in FIFO order and tracks total pages printed.
printer = PrinterQueue()
printer.submit("Alice", "essay.pdf", 5)
printer.submit("Bob", "report.docx", 12)
printer.submit("Charlie", "photo.png", 1)
printer.process_next() # Prints Alice's essay
printer.status() # 2 jobs remaining, 5 pages printed so far
D.2. Write a function josephus(n: int, k: int) -> int that solves the Josephus Problem using a queue. n people stand in a circle. Starting from person 1, every k-th person is eliminated. Return the position of the last person standing.
print(josephus(7, 3)) # 4
print(josephus(5, 2)) # 3
D.3. Write a CustomerService class that manages a call center queue with two priority levels: "urgent" and "normal." Urgent customers are served before normal customers, but within each priority level, FIFO order is maintained.
cs = CustomerService()
cs.add_customer("Alice", "normal")
cs.add_customer("Bob", "normal")
cs.add_customer("Charlie", "urgent")
cs.add_customer("Diana", "normal")
cs.add_customer("Eve", "urgent")
print(cs.serve_next()) # Charlie (first urgent)
print(cs.serve_next()) # Eve (second urgent)
print(cs.serve_next()) # Alice (first normal)
D.4. Write a function moving_average(data: list[float], window: int) -> list[float] that computes a moving average using a queue to track the window.
print(moving_average([1, 2, 3, 4, 5, 6, 7], 3))
# [2.0, 3.0, 4.0, 5.0, 6.0]
D.5. Write a TypewriterEffect class that uses a queue to display text character by character with a simulated delay. Enqueue all characters, then dequeue and print them one at a time.
typer = TypewriterEffect()
typer.load("Hello, World!")
typer.play() # Prints characters one at a time
(Hint: use time.sleep(0.05) and print(ch, end="", flush=True) for each character.)
Part E: Abstract Data Types and Design ⭐⭐⭐
E.1. Implement a MinStack — a stack that supports push, pop, peek, and get_min(), all in O(1) time. get_min() returns the minimum element currently in the stack.
Hint: use an auxiliary stack that tracks the minimum at each level.
ms = MinStack()
ms.push(5)
ms.push(3)
ms.push(7)
print(ms.get_min()) # 3
ms.pop() # removes 7
print(ms.get_min()) # 3
ms.pop() # removes 3
print(ms.get_min()) # 5
E.2. Implement a MaxQueue — a queue that supports enqueue, dequeue, and get_max(). get_max() can be O(n) for this exercise.
mq = MaxQueue()
mq.enqueue(3)
mq.enqueue(7)
mq.enqueue(2)
print(mq.get_max()) # 7
mq.dequeue() # removes 3
print(mq.get_max()) # 7
mq.dequeue() # removes 7
print(mq.get_max()) # 2
E.3. Implement a stack using two queues. (Yes, this is inefficient — the point is understanding ADT flexibility.) The push operation can be O(n).
E.4. Write a Deque class (double-ended queue) that supports push_front, push_back, pop_front, pop_back, front, back, is_empty, and size. Then show how you can use a Deque to implement both a stack and a queue.
E.5. The Python standard library includes queue.Queue, queue.LifoQueue, and queue.PriorityQueue. Read the documentation and write a short program that demonstrates each one. How do their interfaces compare to the classes we built?
Part F: Integration and TaskFlow ⭐⭐⭐-⭐⭐⭐⭐
F.1. Extend the TaskFlow v1.9 undo system to also support undoing complete_task operations. When you undo a completion, the task should go back to its incomplete state. What additional information do you need to store in the UndoableAction?
F.2. Add a history() method to TaskFlow that displays all actions performed (without modifying the undo stack). Hint: you could reach into the stack's _items list, but that leading underscore says "hands off." Better options: keep a separate history list, or add a method to Stack that returns a copy of its items. Which one still works after an undo removes an action from the stack, and which should?
F.3. Add a "priority queue" mode to TaskFlow: tasks with priority "high" are processed before "medium," which are processed before "low." Within the same priority level, maintain FIFO order. Use three separate queues internally.
F.4. Write a MazeRunner class that takes a 2D grid (list of lists) and uses BFS (with a queue) to find the shortest path from a start position to a goal position. Print the path and its length.
maze = [
[".", ".", "#", "."],
["#", ".", "#", "."],
[".", ".", ".", "."],
[".", "#", "#", "."],
]
runner = MazeRunner(maze)
path = runner.solve((0, 0), (3, 3))
print(f"Path: {path}")
print(f"Length: {len(path) - 1}")
# Path: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (3, 3)]
# Length: 6
Hint: when you enqueue a neighbor, record which cell you came from (a dict works well). Once you reach the goal, follow those records backward to rebuild the path.
F.5. (Research) Read about the Shunting Yard Algorithm (Dijkstra, 1961). It uses a stack to convert infix expressions (like 3 + 4 * 2) into postfix notation (like 3 4 2 * +). Implement it for expressions with +, -, *, /, and parentheses. Then chain it with your evaluate_postfix function from C.3 to create a complete expression evaluator.
postfix = infix_to_postfix("3 + 4 * 2 / ( 1 - 5 )")
print(postfix) # "3 4 2 * 1 5 - / +"
print(evaluate_postfix(postfix)) # 1.0