Quiz: Stacks, Queues, and Beyond
Test your understanding before moving on. Target: 70% or higher to proceed confidently.
Section 1: Multiple Choice (1 point each)
1. Which principle describes a stack's access pattern?
- A) FIFO — First In, First Out
- B) LIFO — Last In, First Out
- C) Random access
- D) Priority-based access
Answer
**B)** LIFO — Last In, First Out. *Why B:* A stack always removes the most recently added item first, like a stack of plates. *Why not A:* FIFO describes a queue, not a stack. *Reference:* Section 20.22. What is the output of this code?
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.pop()
s.push(4)
print(s.peek())
- A) 1
- B) 2
- C) 3
- D) 4
Answer
**D)** 4 *Why D:* After pushing 1, 2, 3, we pop (removes 3). Then push 4. The top is now 4. *Why not C:* 3 was removed by `pop()`. *Reference:* Section 20.23. Which operation is NOT part of the standard stack ADT?
- A)
push(item) - B)
pop() - C)
insert(index, item) - D)
peek()
Answer
**C)** `insert(index, item)` *Why C:* Stacks only allow adding/removing at the top. Inserting at an arbitrary position violates the LIFO constraint. *Why not A/B/D:* These are the three core stack operations. *Reference:* Section 20.2, 20.64. Why does our Queue implementation use collections.deque instead of a plain list?
- A)
dequeuses less memory than a list - B)
deque.popleft()is O(1), whilelist.pop(0)is O(n) - C) Lists cannot store mixed types
- D)
dequeautomatically sorts elements
Answer
**B)** `deque.popleft()` is O(1), while `list.pop(0)` is O(n). *Why B:* When you remove the first element of a list, Python shifts every remaining element forward. A deque uses a doubly-linked block structure that avoids this shift. *Why not A:* Memory isn't the reason. Both are memory-efficient containers; the difference that matters here is the cost of removing from the front. *Reference:* Section 20.45. In the bracket-matching algorithm, what data structure is used and why?
- A) Queue — brackets must be checked in order of appearance
- B) Stack — the most recently opened bracket must be the first one closed
- C) Dictionary — to map opening brackets to closing brackets
- D) Set — to check if a character is a bracket in O(1)
Answer
**B)** Stack — the most recently opened bracket must be the first one closed. *Why B:* Brackets nest, so the last opening bracket encountered must match the next closing bracket. This is LIFO behavior. *Why not A:* While we scan left to right (order matters), the matching logic is LIFO. *Reference:* Section 20.36. What is the output of this code?
q = Queue()
q.enqueue("X")
q.enqueue("Y")
q.enqueue("Z")
print(q.dequeue())
print(q.dequeue())
- A) Z, Y
- B) X, Y
- C) Y, X
- D) Z, X
Answer
**B)** X, Y *Why B:* Queues are FIFO. X was enqueued first, so it's dequeued first. Then Y. *Why not A:* That would be LIFO (stack) behavior. *Reference:* Section 20.47. What does ADT stand for, and what does it describe?
- A) Advanced Data Technology — the fastest implementation of a data structure
- B) Abstract Data Type — the operations and behavior of a data structure, independent of implementation
- C) Automated Data Testing — a framework for testing data structures
- D) Applied Data Transformation — converting between data formats
Answer
**B)** Abstract Data Type — the operations and behavior of a data structure, independent of implementation. *Why B:* An ADT specifies *what* operations are available and their behavior, but not *how* they're implemented internally. *Reference:* Section 20.68. In a linked list, each node contains:
- A) Only data
- B) Data and an index number
- C) Data and a reference to the next node
- D) Data and a reference to all other nodes
Answer
**C)** Data and a reference to the next node. *Why C:* A singly-linked list node stores its value and a pointer/reference to the next node. The last node's reference is `None`. *Why not D:* Each node only knows about the *next* node, not all nodes. *Reference:* Section 20.79. What is the time complexity of accessing the 100th element in a linked list?
- A) O(1)
- B) O(log n)
- C) O(n)
- D) O(n^2)
Answer
**C)** O(n) *Why C:* Linked lists don't support random access. You must start at the head and follow references one by one until you reach the 100th node. *Why not A:* O(1) random access is a property of arrays/Python lists, not linked lists. *Reference:* Section 20.710. Which data structure would be BEST for modeling a social network (who follows whom)?
- A) Stack
- B) Queue
- C) Tree
- D) Graph
Answer
**D)** Graph *Why D:* A graph represents arbitrary relationships between entities. Social network connections (follows, friendships) can be bidirectional or unidirectional, with cycles — exactly what graphs model. *Why not C:* Trees are hierarchical (parent-child) and don't allow cycles. Social networks have complex, non-hierarchical connections. *Reference:* Section 20.8Section 2: Short Answer (2 points each)
11. Explain the difference between push and enqueue. Under what circumstances would you use each?
Answer
**`push`** adds an item to the top of a **stack** (LIFO). Use it when you need to reverse order or access the most recent item first (undo systems, backtracking, bracket matching). **`enqueue`** adds an item to the back of a **queue** (FIFO). Use it when you need to process items in the order they arrived (task scheduling, print queues, BFS). Both add items, but the removal order differs: stacks remove from the same end (top), queues remove from the opposite end (front). *Reference:* Sections 20.2, 20.412. A student writes this code:
my_queue = []
my_queue.append("task1")
my_queue.append("task2")
my_queue.append("task3")
first = my_queue.pop(0)
Identify the problem and suggest a fix.
Answer
The code works correctly but has a **performance problem**. `list.pop(0)` is O(n) because Python must shift all remaining elements forward by one position. For a queue with many items, this becomes very slow. **Fix:** Use `collections.deque`:from collections import deque
my_queue = deque()
my_queue.append("task1")
my_queue.append("task2")
my_queue.append("task3")
first = my_queue.popleft() # O(1) instead of O(n)
13. What happens when you try to pop() from an empty stack in our implementation? Why is this behavior (raising an exception) preferable to returning None?
Answer
Our implementation raises an `IndexError` with the message "pop from empty stack." Raising an exception is preferable to returning `None` because: 1. **Fail-fast design:** An empty pop almost always indicates a logic error. An exception makes the bug immediately visible rather than letting `None` propagate silently through the program. 2. **Ambiguity:** If `None` is a valid item in the stack, returning `None` from an empty pop is indistinguishable from popping an actual `None` value. 3. **Consistency:** Python's own `list.pop()` raises `IndexError` on an empty list. Our stack follows the same convention. *Reference:* Section 20.2, 20.914. Explain the threshold concept from this chapter in your own words: "A stack is a CONCEPT (LIFO behavior) that can be IMPLEMENTED in many ways." Give an example.
Answer
An abstract data type (ADT) defines *what* a data structure does — its operations and their behavior — without specifying *how* it's built internally. The stack ADT says "support push, pop, and peek with LIFO ordering." That's the concept. The implementation is a separate decision. We implemented a stack using a Python list (`append` and `pop`), but we could also implement it using a `collections.deque`, a linked list, or even a dictionary with an integer counter as the key. All of these would behave identically from the outside. This separation matters because it lets you swap implementations (e.g., for better performance) without changing any code that uses the stack. *Reference:* Section 20.6Section 3: Code Analysis (3 points each)
15. What does this function do? Trace through it with the input "hello".
def mystery(text: str) -> bool:
s = Stack()
for ch in text:
s.push(ch)
reversed_text = ""
while not s.is_empty():
reversed_text += s.pop()
return text == reversed_text
Answer
This function checks whether `text` is a **palindrome** (reads the same forwards and backwards). **Trace with "hello":** 1. Push: h, e, l, l, o → stack top is 'o' 2. Pop all: o, l, l, e, h → `reversed_text = "olleh"` 3. `"hello" == "olleh"` → `False` The function returns `False` because "hello" is not a palindrome. For "racecar": reversed would be "racecar" → returns `True`. *Reference:* Sections 20.2, 20.316. This code has a bug. Find it and explain how to fix it.
def process_tasks(task_list: list[str]) -> None:
q = Queue()
for task in task_list:
q.enqueue(task)
for i in range(len(task_list) + 1): # Bug is here
task = q.dequeue()
print(f"Processing: {task}")
Answer
**Bug:** The `range(len(task_list) + 1)` iterates one too many times. If `task_list` has 3 items, the loop runs 4 times. The fourth `dequeue()` call operates on an empty queue, raising `IndexError`. **Fix — Option 1:** Use `range(len(task_list))` (no `+ 1`). **Fix — Option 2 (preferred):** Use `while not q.is_empty()`:while not q.is_empty():
task = q.dequeue()
print(f"Processing: {task}")
17. Analyze this undo/redo sequence. What is the final value of editor.text?
editor = TextEditor()
editor.type_text("AB") # text = "AB"
editor.type_text("CD") # text = "ABCD"
editor.type_text("EF") # text = "ABCDEF"
editor.undo() # text = ?
editor.undo() # text = ?
editor.redo() # text = ?
editor.type_text("GH") # text = ?
editor.redo() # text = ? (does anything happen?)
Answer
Step by step: 1. `type_text("AB")` → text = "AB", undo stack: [""], redo stack: [] 2. `type_text("CD")` → text = "ABCD", undo stack: ["", "AB"], redo stack: [] 3. `type_text("EF")` → text = "ABCDEF", undo stack: ["", "AB", "ABCD"], redo stack: [] 4. `undo()` → text = **"ABCD"**, undo stack: ["", "AB"], redo stack: ["ABCDEF"] 5. `undo()` → text = **"AB"**, undo stack: [""], redo stack: ["ABCDEF", "ABCD"] 6. `redo()` → text = **"ABCD"**, undo stack: ["", "AB"], redo stack: ["ABCDEF"] 7. `type_text("GH")` → text = **"ABCDGH"**, undo stack: ["", "AB", "ABCD"], redo stack: **[]** (cleared!) 8. `redo()` → Nothing happens. Redo stack is empty because the new action in step 7 cleared it. **Final text: "ABCDGH"** The key insight: typing "GH" after undoing clears the redo stack, because you've branched into a new timeline. *Reference:* Section 20.318. Compare these two implementations of the same operation. Which is better and why?
# Version A
def drain_queue_a(q: Queue) -> list:
result = []
while q.size() > 0:
result.append(q.dequeue())
return result
# Version B
def drain_queue_b(q: Queue) -> list:
result = []
try:
while True:
result.append(q.dequeue())
except IndexError:
pass
return result
Answer
**Both work, but Version A is the better fit here.** It explicitly checks whether the queue has items before dequeuing ("Look Before You Leap," LBYL). The loop's whole purpose is to run until the queue is empty, so the check *is* the stopping condition, and it's cheap and reads exactly like the intent. **Version B** uses the EAFP style from Chapter 11, which Python generally favors, but EAFP earns its keep when checking first is expensive, has to repeat work, or could go stale (a race condition). None of that applies to a single-threaded drain loop. Version B also has a hidden cost: the `try` swallows *any* `IndexError` raised inside it. If `dequeue()` (or anything else in the loop) had a real indexing bug, Version B would silently stop early and return a partial list instead of crashing where you could see it. Note: `while not q.is_empty()` reads a little more naturally than `while q.size() > 0`, but both are fine. *Reference:* Section 20.9, [Chapter 11](../../part-04-building-robust-programs/chapter-11-error-handling/index.md) (error handling philosophy)Section 4: Conceptual Questions (2 points each)
19. A student says: "Linked lists are better than Python lists because insertion is O(1)." What important caveat are they missing?
Answer
The student is missing a critical caveat: **linked list insertion is O(1) only when you already have a reference to the insertion point.** Finding that point (i.e., getting to the right node) is O(n) because you must traverse from the head. In contrast, a Python list provides O(1) *access* to any position via indexing, though the actual insertion at that position is O(n) due to shifting. The full trade-off: linked lists sacrifice O(1) random access for O(1) insertion/deletion *at known positions*. Python lists sacrifice O(1) insertion for O(1) random access. Neither is universally better — the right choice depends on the problem. *Reference:* Section 20.720. For each scenario, name the best data structure and justify your choice in one sentence:
a) Reopening recently closed browser tabs (Ctrl+Shift+T brings back the most recently closed one first) b) Processing customer service tickets in the order they were submitted c) Representing a family tree d) Checking if a word exists in a dictionary of 100,000 words e) Implementing Ctrl+Z in a word processor