The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Stack Exercises

Next ►
►

This lesson closes the stacks module and is entirely practical: six progressive exercises, with no new theory, consolidating everything you have learned — the ADT contract (03-01 and 03-02), the Stack and LinkedStack implementations (03-03) and the application patterns (03-04) — and several of them extend TaskFlow directly. Work each exercise for real before looking at the solution: try the trace on paper first (as in 03-02), then the code, and only then compare. The solutions are complete and commented, with the reasoning that leads to them, because the goal is not "getting it to work" but knowing why it works. In every exercise you can use the Stack class from lesson 03-03 (or a list with append/pop — you know by now why at the back).

Contents

  1. Exercise 1: reversing a string (and a list of tasks)
  2. Exercise 2: processing keyboard backspaces
  3. Exercise 3: validating push/pop sequences
  4. Exercise 4: min-stack — the minimum in O(1)
  5. Exercise 5: bounded undo history
  6. Exercise 6: from recursion to iteration with an explicit stack

Exercise 1: reversing a string (and a list of tasks)

Level: basic. The "hello world" of stacks: since elements come out in the reverse order they went in, pushing everything and popping it all reverses any sequence.

  1. Write reverse_string(text) that returns the reversed text using a stack (no [::-1] and no reversed, obviously: the goal is the pattern).
  2. Write reverse_tasks(tasks) that takes a list of task dicts and returns a new list in reverse order — TaskFlow will use it to show "the most recently created tasks first".
  3. Analysis question: what is the cost in time and in space? And what if, instead of push/pop, you did two passes with pop(0)?

Solution

def reverse_string(text):
    stack = Stack()
    for char in text:             # phase 1: push everything (goes in, in order)
        stack.push(char)
    result = []
    while not stack.is_empty():   # phase 2: pop everything (comes out reversed)
        result.append(stack.pop())
    return "".join(result)

def reverse_tasks(tasks):
    stack = Stack()
    for task in tasks:
        stack.push(task)
    reversed_tasks = []
    while not stack.is_empty():
        reversed_tasks.append(stack.pop())
    return reversed_tasks

print(reverse_string("TaskFlow"))      # wolFksaT
print(reverse_tasks([{"id": 1, "title": "A", "priority": 2, "status": "pending"},
                     {"id": 2, "title": "B", "priority": 1, "status": "pending"}]))
# [{'id': 2, ...}, {'id': 1, ...}]

Comments:

  • The pattern is the double dump: everything in, everything out. One pass of push (n O(1) operations) plus one of pop (another n): O(n) time, O(n) space (the stack ends up holding all n elements).
  • Note the echo of 03-04 (exercise 1): one reversal changes the order; two reversals restore it. That is why undo+redo with two stacks brings back the chronological order.
  • On question 3: traversing with pop(0) on a list would be O(n) per element → O(n²) total. It is module 1's insert(0)/pop(0) trap all over again; with 100,000 tasks, the difference between milliseconds and minutes.

Exercise 2: processing keyboard backspaces

Level: basic. TaskFlow's "task title" field receives the sequence of keys pressed, where # represents the backspace key (it deletes the last character typed, if there is one). Write final_text(keys) that returns the resulting text.

Examples: final_text("Review####draft") → "Redraft"; final_text("##Hello#") → "Hell" (backspaces on empty text do nothing).

Solution

def final_text(keys):
    stack = Stack()
    for key in keys:
        if key == "#":
            if not stack.is_empty():    # backspace with no text: ignored
                stack.pop()             # deletes the last character typed
        else:
            stack.push(key)
    # The stack holds the text from top to bottom = reversed: flip it back
    chars = []
    while not stack.is_empty():
        chars.append(stack.pop())
    return "".join(reversed(chars))

print(final_text("Review####draft"))  # Redraft
print(final_text("##Hello#"))         # Hell

Comments:

  • "Delete the last thing typed" is the operational definition of pop: the text being edited is a stack of characters (you already identified this in exercise 2 of 03-01).
  • The is_empty() guard before the pop is mandatory: without it, "##Hello#" would raise IndexError on the first #. It is 03-02's number-one common mistake in its purest form.
  • At the end the stack contains the text reversed (the top is the last character): you have to dump it and re-reverse. Total cost O(n).

Exercise 3: validating push/pop sequences

Level: intermediate. You are given two lists: pushes (the order in which n distinct elements were pushed) and pops (a popping order someone claims to have observed). Write is_valid_sequence(pushes, pops) that returns True if that output sequence is possible on a stack, interleaving pushes and pops however you like.

Examples with pushes = [1, 2, 3, 4]:

  • pops = [2, 1, 4, 3] → True (push 1, push 2, pop 2, pop 1, push 3, push 4, pop 4, pop 3).
  • pops = [3, 1, 2] with pushes = [1, 2, 3] → False: to get 3 out first, 1 and 2 remain stacked with 2 on top; it is impossible for 1 to come out before 2.

Hint: simulate. Push the inputs in order and, after each push, pop greedily while the top matches the next expected element of pops.

Solution

def is_valid_sequence(pushes, pops):
    if len(pushes) != len(pops):
        return False
    stack = Stack()
    i = 0                                  # index of the next expected pop
    for element in pushes:                 # we simulate the pushes in their order
        stack.push(element)
        # Greedy popping: while the top is exactly what's expected, pop
        while not stack.is_empty() and i < len(pops) and stack.peek() == pops[i]:
            stack.pop()
            i += 1
    return stack.is_empty()                # everything came out in the requested order

print(is_valid_sequence([1, 2, 3, 4], [2, 1, 4, 3]))  # True
print(is_valid_sequence([1, 2, 3], [3, 1, 2]))        # False
print(is_valid_sequence([1, 2, 3], [1, 2, 3]))        # True (pop after each push)
print(is_valid_sequence([1, 2, 3], [3, 2, 1]))        # True (all pushes, then pops)

Comments:

  • The deep idea: there is no need to reason over every possible interleaving; it is enough to simulate the one sensible strategy (pop as soon as the top matches what's expected). If that strategy can't produce the sequence, none will: delaying a possible pop only buries the element deeper.
  • peek decides and pop executes: the "look before you leap" pattern from 03-02 and from 03-04's shunting-yard.
  • At the end, if the stack didn't end up empty, some element couldn't come out when its turn came: False (which is_empty() returns directly).
  • Cost O(n): each element is pushed once and popped at most once, even though there is a while inside the for (count total operations, not nesting: an amortized cost argument like the one in 03-03).

Exercise 4: min-stack — the minimum in O(1)

Level: upper-intermediate. TaskFlow wants to show at all times "the highest-priority task in the history" (remember: priority 1 = highest, so we are looking for the minimum value). Scanning the history on every query would be O(n). Design MinStack with the usual contract (push, pop, peek, is_empty, size) plus a minimum() operation that returns the minimum value on the stack, everything in O(1).

Hint: an auxiliary stack that, in parallel with the main one, stores "the minimum in effect up to this level". Think about what must be pushed onto the auxiliary stack on each push, and what happens on each pop.

Solution

class MinStack:
    """Stack with minimum() in O(1) via an auxiliary stack of running minimums."""

    def __init__(self):
        self._stack = Stack()      # the actual data
        self._mins = Stack()       # running minimums, in parallel level by level

    def push(self, value):
        self._stack.push(value)
        if self._mins.is_empty():
            self._mins.push(value)
        else:
            # The minimum in effect after this push: the lesser of new and previous
            self._mins.push(min(value, self._mins.peek()))

    def pop(self):
        self._mins.pop()           # both stacks grow and shrink together
        return self._stack.pop()

    def peek(self):
        return self._stack.peek()

    def minimum(self):
        return self._mins.peek()      # O(1): the current minimum sits on top

    def is_empty(self):
        return self._stack.is_empty()

    def size(self):
        return self._stack.size()


s = MinStack()
for priority in [3, 1, 2]:
    s.push(priority)
print(s.minimum())  # 1
s.pop()             # the 2 comes out
print(s.minimum())  # 1  (the 1 is still inside)
s.pop()             # the 1 comes out
print(s.minimum())  # 3  (the previous minimum "revives" on its own!)

Comments:

  • The trick is the parallel invariant: _mins always has the same size as _stack, and its top is "the minimum of everything currently in _stack". Each push pushes onto _mins the min of the new value and the previous minimum; each pop pops from both.
  • The magic is in the last print: when the 1 is popped, the minimum goes back to 3 without recomputing anything, because the auxiliary stack remembers the minimum of each historical level. A simple counter ("the minimum is 1") couldn't: on popping the 1 it wouldn't know what the previous one was.
  • Cost: all operations O(1); O(n) extra space for the auxiliary stack. It is a space-for-time trade — the most common currency in data structures.
  • Trace of the two stacks after pushing 3, 1, 2 (top up):
_stack _mins
2 1
1 1
3 3
  • Connection with TaskFlow: if actions are pushed and _mins stores the minimum priority seen, minimum() answers "the highest-priority task touched this session" instantly. (To always extract the highest-priority task from the board — not just query it — the right structure is the priority queue, arriving in module 4.)

Exercise 5: bounded undo history

Level: upper-intermediate. The infinite history of UndoRedoManager (03-04) burns memory without restraint. TaskFlow decides: "at most the last k undoable actions are kept". Careful: unlike 03-03's BoundedStack (which rejected the push), here, when the limit is exceeded, the oldest action (the one at the bottom) must be discarded — not the new one rejected.

  1. Can a pure stack (top only) discard from the bottom in O(1)? Reason your answer.
  2. Implement BoundedHistory with record(action), undo() (→ action or None) and size(), honoring the limit. You may lean on the internal list (accepting whatever cost that has) or propose something better.

Solution

Part 1. No. The stack's contract only grants access to the top; the bottom is, by definition, unreachable without popping everything (O(n)). We need a structure with access to both ends: insert/remove at the top and discard at the bottom. That structure exists and is called a deque (double-ended queue); module 2 mentioned it (collections.deque, a block-based doubly linked list) and module 4 develops it. This exercise makes you feel why it is needed.

Part 2. An honest version with list, documenting the cost:

class BoundedHistory:
    """Undo history that keeps only the last k actions."""

    def __init__(self, limit):
        self._limit = limit
        self._actions = []                # top = back of the list, as always

    def record(self, action):
        self._actions.append(action)      # normal push: amortized O(1)
        if len(self._actions) > self._limit:
            self._actions.pop(0)          # discard the OLDEST: O(n), ouch!

    def undo(self):
        if not self._actions:
            return None                   # domain layer: None, as in 03-03
        return self._actions.pop()        # the most recent: O(1)

    def size(self):
        return len(self._actions)


h = BoundedHistory(3)
for n in (1, 2, 3, 4):
    h.record({"type": "change_status", "task": n, "prev_data": {}})
print(h.size())                   # 3  (task 1's action was discarded)
print(h.undo()["task"])           # 4  (the most recent is still the top)
print(h.undo()["task"])           # 3
print(h.undo()["task"])           # 2
print(h.undo())                   # None (1 no longer exists: it was discarded)

Comments:

  • LIFO behavior is preserved intact at the top; the limit only acts at the bottom, and only once k is exceeded.
  • That pop(0) is our old friend the O(n) trap. Is it acceptable? It depends: with limit = 50 actions, shifting 50 references is negligible; with limit = 1,000,000, it isn't. Knowing how to quantify when an O(n) is tolerable is engineering too (small, bounded n's don't hurt).
  • The elegant solution replaces the list with collections.deque(maxlen=limit): with maxlen, the deque itself automatically discards from the bottom on append, all in O(1). Write it in your head and save it: we will do it properly in module 4, when the deque stops being a mention and becomes a protagonist.

Exercise 6: from recursion to iteration with an explicit stack

Level: advanced. In 03-04 you saw that the recursive sum_ids blows up with RecursionError on long chains. Let's generalize the cure. TaskFlow now organizes projects with nested subtasks: a task can hold a "subtasks" list of tasks, which in turn can have their own, to any depth.

  1. Write count_pending_rec(task) (recursive): it counts how many tasks in the subtask tree (root included) have "status": "pending".
  2. Rewrite it as count_pending_iter(task) without recursion, using an explicit stack of "tasks pending a visit".
  3. Verify that the recursive version fails on a chain of 100,000 nested subtasks and the iterative one doesn't.

Solution

Part 1: recursive version.

def count_pending_rec(task):
    total = 1 if task["status"] == "pending" else 0
    for subtask in task.get("subtasks", []):     # get: there may be no subtasks
        total += count_pending_rec(subtask)      # one stack frame per level
    return total

Part 2: iterative version. The general conversion recipe: wherever the recursion left pending work on the call stack, we leave pending work on a Stack of our own.

def count_pending_iter(task):
    total = 0
    pending = Stack()                 # tasks not yet visited
    pending.push(task)                # we start at the root
    while not pending.is_empty():
        current = pending.pop()       # visit the most recently pending one
        if current["status"] == "pending":
            total += 1
        for subtask in current.get("subtasks", []):
            pending.push(subtask)     # its children await their visit
    return total

Part 3: the acid test.

# We build a chain of 100,000 nested tasks (each with one subtask)
root = {"id": 0, "title": "T0", "priority": 2, "status": "pending"}
current = root
for i in range(1, 100_000):
    child = {"id": i, "title": f"T{i}", "priority": 2, "status": "pending"}
    current["subtasks"] = [child]
    current = child

print(count_pending_iter(root))   # 100000: without breaking a sweat
print(count_pending_rec(root))    # RecursionError: maximum recursion depth exceeded

Comments:

  • Compare the skeletons: they are the same algorithm. The recursive one says "count this one and delegate the children to the call stack"; the iterative one says "count this one and leave the children on my stack". The difference is who holds the pending work: an implicit stack limited to ~1000 frames, or an explicit stack limited only by your RAM.
  • The loop while not pending.is_empty(): current = pending.pop() is 03-02's draining pattern, now with the subtlety that the loop itself adds elements: the stack grows and shrinks until the work runs out.
  • The visit order changes relative to the recursive version (pushed children come out in reverse order), but for counting, order is irrelevant. When order matters, you control the pushing order — exactly what you will do in tree traversals (module 6) and graph DFS (module 7): this function is a DFS over the subtask tree, even if we don't call it that yet.

Common Mistakes and Tips

  • Looking at the solution at the first snag: the snag is where the learning happens. Give yourself at least 15 minutes and one paper trace per exercise before comparing.
  • Forgetting the is_empty() guard: it appeared in exercises 2, 3 and 5. If your solution raises IndexError on odd inputs (empty ones, all backspaces...), a guard is almost certainly missing.
  • In exercise 3, trying to enumerate interleavings: the combinatorial explosion is enormous; the greedy simulation is O(n). Faced with an "is this sequence possible?" problem, think simulate before enumerate.
  • In the min-stack, storing a single global minimum: it fails as soon as the minimum is popped. If your minimum() goes stale after a pop, this is the mistake: you need the minimum per level.
  • In the iterative conversion, forgetting to push the root or failing to consume with pop: a loop that never starts, or an infinite one. Mental template: push seed → while not empty → pop → process → push children.
  • Final tip: come back to these exercises in a week and try to solve them from memory. Stacks are fixed with the hands, not the eyes.

Conclusion

Stacks module complete. In five lessons you have gone from a promise ("TaskFlow's undo is waiting for you") to an arsenal: the LIFO contract and its invariants, two interchangeable implementations measured with timeit, TaskFlow's real undo/redo with two stacks, balance validation, expression evaluation, and — in this lesson — the patterns of double dumping, greedy simulation, the parallel auxiliary stack (min-stack) and converting recursion into iteration, which is a DFS that doesn't know it yet. Along the way, two bright signals were left pointing at the next module: the bounded history needed to discard at the bottom while operating at the top (two ends: a deque), and the min-stack could query the minimum but not always extract the highest-priority item (a priority queue). Both needs, together with the policy opposite to LIFO — FIFO, first in is first out, like TaskFlow's tasks waiting to be processed in fair arrival order — are exactly the program of module 4: queues. See you there.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved