Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 6
Stacks (Lecture 06)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
"LIFO" means:
First in, first out (b) is a queue — Week 7.
-
push(1),push(2),push(3),pop(),push(4),pop(). What does the nextpop()return?The stack goes [1, 2, 3] → pop 3 → [1, 2] → push 4 → [1, 2, 4] → pop 4 → [1, 2]; the next pop returns 2.
-
A stack built on a dynamic array should keep its top at:
appendandpop()at the end move nothing. Index 0 (a) shifts everything on every operation. -
A stack built on a singly linked list should keep its top at:
push_frontandpop_frontare O(1). At the last node (a), popping would need the node before it — an O(n) walk. -
Stack().pop()on an empty stack:The contract says
IndexError, aslist.pop()does. ReturningNone(b) lets an error travel silently. -
A stack on an array with its top at index 0.
pushcosts:Inserting at index 0 of an array shifts every element — the "dishonest" design that still passes every test.
-
Why is
"([)]"not balanced?The partner check fails. The count is even (a), and the stack is not empty at that point (d).
-
Which check makes
is_balanced(")")returnFalse?The closer finds nothing to match. The partner check (a) cannot even run.
-
The postfix form of
3 + 4 * 2is:*binds tighter, so4 2 *is computed first, then added to 3. -
The postfix form of
( 3 + 4 ) * 2is:The parentheses group
3 4 +first; the result is then multiplied by 2. -
Evaluating the postfix
8 3 -gives:The first value popped (3) is the right operand, the second (8) the left: 8 − 3.
-
Evaluating the postfix
2 3 4 * +gives:3 4 *is 12, then2 12 +is 14. -
In the shunting-yard algorithm, when an operator arrives, it first pops to the output every stacked operator with:
Higher or equal. Strictly higher (d) is the rule for right-associative operators such as
**. -
Why does an operator of equal precedence also leave the stack?
Popping the earlier
-before pushing the later one computes the left subtraction first. -
The postfix form of
8 - 3 - 2is:Left associative:
(8 - 3) - 2.8 3 2 - -(a) is8 - (3 - 2), which is 7, not 3. -
The worst-case extra space of
is_balancedon a text of length n is:A text of n openers,
((((…, pushes all n. -
To turn a recursive algorithm into a loop, in general you need:
The call stack does the bookkeeping for a recursion; without it, you keep that stack yourself.
-
In an undo/redo system with two stacks, what happens to the redo stack when the user performs a new action?
Redo only makes sense for actions just undone; a new action starts a new history.
-
n pushes onto the
Stackofdsa/stack.py(built on aDynamicArray) cost in total:Each push is an append to the
DynamicArray: amortised O(1). -
Which of these is not a natural stack application?
First come, first served is FIFO — a queue.
-
While
is_balanced("(((())))")runs, the largest number of items on the stack at once is:Four openers in a row, then four closers.
-
peek()differs frompop()in that it:And, like
pop, it raisesIndexErroron an empty stack — so (d) is wrong. -
The shunting-yard algorithm converts
2 * 3 + 4to:*is stacked first; when+arrives,*has higher precedence and leaves first, so2 3 *comes before4 +. (a) is2 * (3 + 4), and (c) and (d) are not postfix. -
The shunting-yard algorithm converts
( 1 + 2 ) * ( 3 - 4 ) / 5to:When
/arrives,*is on the stack with equal precedence, so it leaves first:… * 5 /, which is((1 + 2) * (3 - 4)) / 5. (a) is what the>bug produces:/waits on top of*, which computes(1 + 2) * ((3 - 4) / 5). -
A student's
infix_to_postfixpops an operator only when the stacked one has strictly higher precedence (>instead of>=). Their calculator,evaluate_postfix(infix_to_postfix(...)), now gives8 - 3 - 2as:The second
-does not pop the first, so the postfix is8 3 2 - -, which is8 - (3 - 2)= 7. The right answer (a) is 3. No error (c): the postfix is well formed, just wrong. -
With the same
>bug, which of these inputs is still converted correctly?When
*arrives,+is lower, so it stays under both rules; the two rules differ only for equal precedence. (b), (c) and (d) each have two operators of equal precedence in a row: (c) becomes8 / (4 / 2)= 4.0 instead of 1.0, (d)6 - (2 + 1)= 3 instead of 5. -
evaluate_postfix(["6", "2", "/", "3", "*"])returns:6 / 2is 3.0 (true division gives a float), then3.0 * 3is 9.0. (a) multiplies first, which the postfix order does not allow; exactly one value is left at the end, so there is noValueError(d). -
A buggy
evaluate_postfixcomputes (first value popped) op (second value popped): the operands the wrong way round. On which input does it still give the right answer?Only
+and*appear, and both commute, so the swapped order cannot show. (a) gives −5 instead of 5, (b) 0.33 instead of 3.0, (c) −2 instead of 2: every-and/exposes the bug, which is why the tests need them. -
evaluate_postfix(["3", "4"]):Two numbers and no operator leave two values on the stack; the contract says exactly one must remain, so the input is malformed. Returning the top (a) would hide the error.
-
evaluate_postfix(["1", "0", "/"]):The expression is well formed, so it is not a
ValueError(b). Python's own1 / 0raisesZeroDivisionError, andevaluate_postfixlets it through. -
A version of
is_balancedends withreturn Trueinstead ofreturn openers.is_empty(). Which input does it get wrong?((a)leaves one(on the stack, which only the empty-at-the-end check catches. The partner check still catches (a), and the non-empty check still catches (b) and (c), whose closer arrives on an empty stack. -
A version of
is_balancedpops for every closer without first checking that the stack is non-empty. On"())"it:After
()the stack is empty; the second)callspop, and yourStack.popraisesIndexError: a crash instead of the answerFalse(b). -
is_balanced("a(b)c)d(")returnsFalse. Which check fails first?(is pushed and matched by the first); the second)finds the stack empty, and the function returnsFalsethere. The final((c) is never reached. -
is_balanced("print('(')"), a line of valid Python, returns:is_balancedknows nothing about strings: it sees(,(,), and one(is left at the end. The counts are 2 and 1, not equal (b). A real parser first splits the text into tokens, so a bracket inside a string is not a bracket (Week 15). -
Most pushes onto the
Stackofdsa/stack.pyare instant, but now and then one push takes much longer. Why?That is the resize of Week 4: rare, expensive pushes, paid for by the many cheap ones. The course stack keeps the top at the end, not at index 0 (b), and nothing walks (c).
-
Which stack gives worst-case O(1) for every push, not just amortised O(1)?
push_frontmakes one node and moves one reference, always. The array with the top at the end (a) is amortised O(1): a push that triggers a resize copies everything. (b) and (d) are O(n) designs. -
s = Stack([1, 2, 3]). What doess.pop()return?Stack(values)pushes the values in order, so the last one, 3, is the top. A stack built from values is not empty (d). -
Two
peek()calls in a row, with nothing in between, return two different values. The most likely bug is thatpeek:A
peekthat removes is apop: the second call sees the item underneath. Reading index 0 (a) is wrong too, but it would return the same wrong value twice. -
An editor with an undo stack and a redo stack. The user types A, types B, types C, then: undo, undo, redo, types D. What is on the two stacks (bottom → top)?
Undo, undo: C, then B, move to the redo stack. Redo moves B back. Typing D pushes D on the undo stack and clears the redo stack, so C is gone (c). (b) forgets that C was undone.
-
nested_sumwith your ownStackinstead of recursion. Its real advantage in Python is that:Both versions visit every item once, O(n) either way (a), and the explicit stack needs memory too (d). The gain is the depth limit: Python stops a recursion at about 1,000 frames, and does not optimise tail calls.
32 marks
Written questions
9 written questions (32 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 32
-
State the Stack ADT with the cost of each operation. Describe two honest implementations, compare them, and describe one design that passes every test but is not honest.
Model answer and marking points
- ADT:
push(x),pop(),peek(),is_empty(),len()— LIFO, all O(1);popandpeekraiseIndexErrorwhen empty. - On a dynamic array, top at the end: push is amortised O(1) (occasional resize), pop and peek O(1); compact memory, contiguous.
- On a linked list, top at the head: all worst-case O(1); a node per item (about six times the memory of an array slot).
- Dishonest: top at index 0 of an array — every push and pop shifts all the elements, O(n) each, O(n2) for n operations — yet the stack behaves correctly and passes every test.
- ADT:
-
Describe the stack algorithm for balanced brackets. Give an example of each of the three ways a text can be unbalanced, and the check that catches it.
Model answer and marking points
- Scan the text. Opener: push. Closer: the stack must be non-empty and the popped opener must be its partner. End: the stack must be empty. Other characters are ignored.
- Wrong partner:
([)]—)pops[. - Closer with nothing open:
)or())— the stack is empty when a closer arrives. - Opener never closed:
(or(()— the stack is not empty at the end. - O(n) time, O(n) space in the worst case.
-
Explain how a stack evaluates a postfix expression. Why does the order in which the two operands are popped matter, and for which operators?
Model answer and marking points
- Scan the tokens: push numbers; for an operator, pop two values, apply it, push the result; at the end exactly one value must remain (otherwise the input was malformed).
- The first value popped is the right operand and the second the left, because the left operand was pushed earlier.
- It matters for the non-commutative operators,
-and/:8 3 -must be 8 − 3 = 5, not 3 − 8 = −5.
-
Explain the shunting-yard algorithm, and trace it on
2 * ( 3 + 4 ) - 5. Why must an operator of equal precedence be popped?Model answer and marking points
- Output list and operator stack. Numbers go to the output;
(is pushed;)pops to the output down to the matching(; an operator pops every stacked operator of higher or equal precedence, then is pushed; at the end the stack is emptied to the output. - Trace of
2 * ( 3 + 4 ) - 5:
Token Output Stack 2 2 * 2 * ( 2 * ( 3 2 3 * ( + 2 3 * ( + 4 2 3 4 * ( + ) 2 3 4 + * - 2 3 4 + * - 5 2 3 4 + * 5 - end 2 3 4 + * 5 - - Equal precedence pops so that left-associative operators apply left to right: in
8 - 3 - 2, the first-must be applied before the second.
- Output list and operator stack. Numbers go to the output;
-
"Recursion is a stack." Explain, and describe how you would rewrite a recursive algorithm without recursion. When is that worth doing in Python?
Model answer and marking points
- Every call pushes a frame (its local variables and where to return) on the call stack, and every return pops one — so a recursion is a computation driven by a stack.
- Rewrite: push the initial problem on an explicit
Stack; loop while it is not empty: pop a problem, solve it directly if it is a base case, otherwise push its sub-problems. - Worth it in Python when the recursion could go deeper than about 1,000 frames (
RecursionError), since there is no tail-call optimisation — e.g. a depth-first search on a large graph (Week 14).
-
A student's
infix_to_postfixpops an operator only on strictly higher precedence (>instead of>=). Give one input that it still converts correctly and one that it gets wrong, with both postfix results and their values. Explain why the tests can miss this bug, and name an operator for which>is the right rule.Model answer and marking points
- Still right:
3 + 4 * 2. It gives3 4 2 * += 11 under both rules: when*arrives,+is lower, and the two rules differ only for equal precedence. - Wrong:
8 - 3 - 2. The second-does not pop the first, so the output is8 3 2 - -, which is8 - (3 - 2)= 7 instead of8 3 - 2 -= 3. - Why tests miss it: only an input with two operators of equal precedence in a row, where the operation does not associate (
-,/), shows the difference.2 + 3 + 4gives a different postfix but the same value, so a test that checks only values passes. >is right for a right-associative operator such as**:2 ** 3 ** 2means2 ** (3 ** 2), so the later**must wait on top of the earlier one.
- Still right:
-
Run the whole calculator on
( 8 - 2 ) / ( 1 + 2 ) * 4: convert it to postfix with the shunting-yard algorithm, then evaluate the postfix with a stack, showing the stack after each operator. Why is the answer a float?Model answer and marking points
- Postfix:
8 2 - 1 2 + / 4 *. The)s output-and+; when*arrives, the/on the stack has equal precedence and leaves first. - Evaluation (stack bottom → top):
-pops 2 and 8 → [6];+pops 2 and 1 → [6, 3];/pops 3 and 6 → [2.0];*pops 4 and 2.0 → [8.0]. Exactly one value is left: the answer, 8.0. - A float because
/is true division in Python:6 / 3is 2.0, and every result built on it stays a float.
- Postfix:
-
Compare a stack on a dynamic array (top at the end) with a stack on a singly linked list (top at the head): the cost of push in the worst case and amortised, the memory per item, and memory locality. The lecture's timings found the linked stack faster in this course. Why, and would that still hold for Python's own
list? Which would you choose for a program that must never pause?Model answer and marking points
- Push: the array stack is amortised O(1), but a push that fills the block copies everything, O(n) for that one push. The linked stack is O(1) in the worst case: one node and one reference, every time.
- Memory and locality: the array stores one reference per item (plus spare capacity) in one contiguous block; the linked stack needs a whole node per item (about 48 bytes), scattered in memory.
- The measurement: every access to the course
Arraygoes through a Python-level bounds check indsa/array.py, while a node'snextis a plain attribute. That is a constant factor, not a different Big-O. Python's ownlist, whose checks run in C, is faster than both. - Never pause: the linked stack, because its worst case is O(1) (or an array allocated once at its full size, so that it never resizes).
-
Design undo and redo for a text editor with two stacks. Say what each of action, Undo and Redo does to the two stacks, and show both stacks after: type A, type B, type C, undo, undo, redo, type D. What would go wrong if a new action did not clear the redo stack?
Model answer and marking points
- Action: push it on the undo stack and clear the redo stack. Undo: pop from undo, reverse it, push it on redo. Redo: pop from redo, do it again, push it on undo. Undo or Redo on an empty stack does nothing.
- Trace: after A, B, C: undo [A, B, C], redo []. Undo, undo: undo [A], redo [C, B] (top B). Redo: undo [A, B], redo [C]. Type D: undo [A, B, D], redo [].
- Without the clear, Redo would bring back C on top of D, an edit made to a different text, and the history would no longer describe a sequence of states the user actually saw.