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 interleaves the first half with the second half. You may use a temporary stack.
q = Queue()
for item in [1, 2, 3, 4, 5, 6]:
q.enqueue(item)
result = interleave(q)
# Result should contain: 1, 4, 2, 5, 3, 6
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). A potato is passed count times. After count passes, the player 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: Charlie
Hint: "passing the potato" means dequeuing from the front and enqueuing to 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 to also detect the position and type of mismatch, and report ALL errors (not just the first one). Return a list of error messages.
errors = check_all_brackets("([)]{")
# Should report:
# Mismatched '[' at position 1 with ')' at position 2
# Unmatched '{' at position 4
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'll need to track actions in a separate list or iterate the stack's internal list.
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}")
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