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

Stack Implementation

Next ►
►

The time has come to keep the promise: implement the stack. And we will do it twice. In module 1 we distinguished the ADT (the contract: which operations, at what cost) from the implementation (the how), with ListStack and DictStack as an example of one contract admitting several "hows". Today that idea stops being theoretical: we will write a Stack class on top of Python's list and a LinkedStack on top of the nodes from module 2, verify that both fulfill exactly the same contract and the same invariants, measure them with timeit, and discuss which one suits each situation. To close, TaskFlow gets its ActionHistory: the stack that records every user action along with the data needed to revert it. This lesson is the heart of the module: by the end you will have not just a stack, but the judgment to choose between equivalent implementations — a skill you will use with every structure in the rest of the course.

Contents

  1. The contract both implementations must fulfill
  2. Implementation 1: Stack on top of list
  3. Implementation 2: LinkedStack on top of nodes
  4. Same contract, same tests
  5. Cost comparison: amortized vs guaranteed, and memory
  6. Measuring with timeit
  7. Which one to choose, and why?
  8. TaskFlow: the ActionHistory class

The contract both implementations must fulfill

Let's put in writing what we agreed in the previous lessons. Every stack in this course must offer:

Operation Behavior Empty stack Required cost
push(e) Pushes e onto the top (not applicable) O(1)
pop() Removes and returns the top IndexError O(1)
peek() Returns the top without removing it IndexError O(1)
is_empty() True/False True O(1)
size() Number of elements 0 O(1)

Whoever uses the stack may depend only on this table: never on the internal details. That gives us total freedom to implement the inside however we want... as long as the table holds.

Implementation 1: Stack on top of list

In the previous lesson we used a bare list as a provisional stack and spotted its flaw: nothing prevents bypassing the contract (insert(0, ...), access by index...). The solution is encapsulation: keep the list as an internal attribute and expose only the five operations.

class Stack:
    """Stack (LIFO) implemented on top of Python's list.

    The top is the BACK of the internal list: append/pop at the back are O(1).
    """

    def __init__(self):
        self._items = []              # internal list; the _ signals "private"

    def push(self, element):
        self._items.append(element)           # push = append at the back

    def pop(self):
        if not self._items:
            raise IndexError("pop from an empty stack")
        return self._items.pop()              # pop() with no argument = from the back

    def peek(self):
        if not self._items:
            raise IndexError("peek at an empty stack")
        return self._items[-1]                # read-only look at the top

    def is_empty(self):
        return len(self._items) == 0

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

    def __len__(self):                        # enables len(stack)
        return len(self._items)

    def __str__(self):                        # top on the left, like the traces
        items = ", ".join(repr(e) for e in reversed(self._items))
        return f"Stack(top -> [{items}])"

Detailed explanation:

  • self._items: the leading underscore is Python's convention for "internal attribute: don't touch it from outside". Python doesn't technically forbid it, but the whole ecosystem respects the signal. This line is the encapsulation: the user of Stack no longer sees a list, they see a stack.
  • The top is the back of the list: a decision inherited from the previous lesson. append and pop() at the back are the dynamic array's cheap operations; with insert(0)/pop(0) we would have paid O(n).
  • pop and peek raise IndexError with our own message: the list would already raise IndexError, but checking it ourselves lets us give a clear message ("pop from an empty stack" instead of "pop from empty list") and, above all, leaves the design decision written in the code rather than delegated by accident.
  • len(stack) and print(stack): small Pythonic luxuries, just as we did with __str__ in LinkedList. __str__ prints the top first, so it matches our trace tables.

Let's try it with TaskFlow actions:

s = Stack()
s.push({"type": "create", "task": 7})
s.push({"type": "change_priority", "task": 7})
print(s.peek())        # {'type': 'change_priority', 'task': 7}
print(s.size())        # 2
print(s.pop()["type"]) # change_priority
print(s)               # Stack(top -> [{'type': 'create', 'task': 7}])

Implementation 2: LinkedStack on top of nodes

Now the version promised at the end of module 2: a stack on top of linked nodes, "in a few lines". The whole idea fits in one sentence: the top of the stack is the head of a linked list; push is insert_front and pop is removing the head — the two O(1) operations you already command.

We reuse the Node from module 2 (data + next):

class Node:
    """The same Node from module 2: a data item and the reference to the next."""
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedStack:
    """Stack (LIFO) implemented on top of linked nodes.

    The top is the HEAD of the chain of nodes: push/pop at the head are O(1).
    """

    def __init__(self):
        self._top = None              # reference to the topmost node (or None)
        self._size = 0                # counter, so size() is O(1)

    def push(self, element):
        new_node = Node(element)      # 1. create the node
        new_node.next = self._top     # 2. the new node points to the old top
        self._top = new_node          # 3. the new node IS the top
        self._size += 1

    def pop(self):
        if self._top is None:
            raise IndexError("pop from an empty stack")
        node = self._top              # 1. hold on to the node being removed
        self._top = node.next         # 2. the top becomes the next node
        self._size -= 1
        return node.data              # 3. return the data (the node frees itself)

    def peek(self):
        if self._top is None:
            raise IndexError("peek at an empty stack")
        return self._top.data

    def is_empty(self):
        return self._top is None

    def size(self):
        return self._size

    def __len__(self):
        return self._size

    def __str__(self):
        items, current = [], self._top
        while current is not None:
            items.append(repr(current.data))
            current = current.next
        return f"LinkedStack(top -> [{', '.join(items)}])"

Step-by-step analysis of the two key operations:

  • push is exactly LinkedList's insert_front, with the head renamed _top. Three steps, no loop: O(1) always, whether there are 3 elements or 3 million. The order of steps 2 and 3 matters: if you did self._top = new_node before wiring new_node.next, you would lose the reference to the old stack (the same ordering mistake we saw when inserting into linked lists).
  • pop is removing the head: set the node aside, advance the top, return the data. Also loop-free: O(1) always. The removed node is no longer referenced, and Python's garbage collector frees it.
  • _size as a counter: counting by traversal would be O(n); maintaining the counter on each push/pop gives size() in O(1). Same technique as in LinkedList.
flowchart LR
    subgraph BEFORE["Before push(D)"]
        direction LR
        top1["_top"] --> C1["C"] --> B1["B"] --> A1["A"] --> N1["None"]
    end
    subgraph AFTER["After push(D)"]
        direction LR
        top2["_top"] --> D2["D"] --> C2["C"] --> B2["B"] --> A2["A"] --> N2["None"]
    end
    BEFORE -->|"new_node.next = old top"| AFTER

Same contract, same tests

The definitive proof that ADT and implementation are properly separated: a single set of checks (the invariants from lesson 03-02) must pass with either of the two classes, without changing a single line:

def check_contract(StackClass):
    """Verifies the ADT's invariants on any implementation."""
    s = StackClass()
    assert s.is_empty() and s.size() == 0            # invariant 1

    s.push("a")
    assert s.peek() == "a" and s.size() == 1         # invariant 2

    s.push("b")
    assert s.pop() == "b" and s.peek() == "a"        # invariant 3: pop undoes push

    before = s.size()
    s.peek()
    assert s.size() == before                        # invariant 4: peek modifies nothing

    s.pop()
    try:
        s.pop()                                      # empty stack: must fail
        assert False, "should have raised IndexError"
    except IndexError:
        pass
    print(f"{StackClass.__name__}: contract OK")

check_contract(Stack)          # Stack: contract OK
check_contract(LinkedStack)    # LinkedStack: contract OK

The function takes the class as a parameter and works with both. To client code (and to TaskFlow) the two stacks are interchangeable: that is programming against the contract.

Cost comparison: amortized vs guaranteed, and memory

If both fulfill the contract, how do they differ? In the finer points of performance and memory:

Aspect Stack (on list) LinkedStack (on nodes)
push O(1) amortized O(1) guaranteed
pop / peek O(1) O(1)
Memory per element Compact: contiguous references in the array Higher: each item pays for an extra Node object (data + next)
Memory locality Good (contiguity → happy cache) Worse (nodes scattered across memory)
After heavy draining The array may keep spare capacity Frees each node on pop
Lines of code Fewer (delegates to list) More (manages nodes and counter)

The new nuance is amortized vs guaranteed, and it deserves an explanation:

  • Python's list is a dynamic array (module 1): when it fills up, it reserves a bigger block and copies every element. That particular append costs O(n).
  • Since capacity grows geometrically (always by a percentage), those copies become rarer and rarer. Spread out ("amortized") across all the append calls, the average cost per operation is O(1). But an individual push, every once in a while, is slow.
  • LinkedStack never copies anything: each push creates a node and moves two references. O(1) in the worst case, no exceptions.

When does this difference matter? Almost never in ordinary applications... and enormously in systems with stable latency requirements (real-time audio, embedded systems), where an occasional "spike" is unacceptable. It is the first time in the course that two correct options differ not in average cost but in its distribution: note the concept down, it will come back.

Measuring with timeit

Let's back the claims with data, as we did in module 1. We measure pushing and popping 100,000 elements with each implementation:

import timeit

def drill(StackClass, n=100_000):
    s = StackClass()
    for i in range(n):
        s.push(i)
    while not s.is_empty():
        s.pop()

for StackClass in (Stack, LinkedStack):
    t = timeit.timeit(lambda: drill(StackClass), number=10)
    print(f"{StackClass.__name__:14}: {t:.3f} s (10 rounds of 100k push+pop)")

Indicative results (the exact numbers depend on your machine; the proportions don't):

Stack         : 0.35 s (10 rounds of 100k push+pop)
LinkedStack   : 1.60 s (10 rounds of 100k push+pop)

Two important readings, seemingly contradictory:

  1. Both scale the same: double n and you will see both times roughly double — linear behavior for n operations, i.e. O(1) per operation. The theory is confirmed for both.
  2. The constant matters: Stack is several times faster. Didn't we say LinkedStack had the better guarantee? Yes: a better worst case, but a worse constant, because each push creates a Node object in Python (expensive) while append is implemented in C over contiguous memory. Big O speaks of growth, not absolute speed: two O(1)s can differ by a factor of 5.

This is a hugely valuable general lesson: measuring complements reasoning. Asymptotic analysis tells you what scales; timeit tells you what it really costs on your platform.

Which one to choose, and why?

A practical criterion for Python:

  • By default: Stack on top of list. Less code, less memory, faster in practice, and it delegates to an ultra-optimized piece of the language. It is the right choice for TaskFlow and for 95% of cases.
  • LinkedStack when... you need guaranteed O(1) per operation (stable latency), or when the stack shares nodes with other linked structures. And, above all, it is the implementation you will see in books and interviews, and the one used in languages without a built-in dynamic array: understanding it is not optional.
  • The key point: since both fulfill the contract, switching from one to the other touches not a single line of client code. Choosing the implementation is a local, reversible decision; choosing the wrong ADT, on the other hand, is paid for across the whole program.

TaskFlow: the ActionHistory class

Let's close by putting the stack to work. TaskFlow's history records actions: dictionaries with the action type, the id of the affected task, and the previous data needed to revert it:

{"type": "change_status", "task": 7, "prev_data": {"status": "pending"}}

ActionHistory wraps a Stack and offers domain vocabulary (record/undo) instead of structure vocabulary (push/pop):

class ActionHistory:
    """TaskFlow's undo history: a stack of revertible actions."""

    def __init__(self):
        self._stack = Stack()             # composition: it contains a Stack

    def record(self, action_type, task_id, prev_data):
        action = {"type": action_type, "task": task_id, "prev_data": prev_data}
        self._stack.push(action)

    def undo(self):
        """Removes and returns the last recorded action (so it can be reverted)."""
        if self._stack.is_empty():
            return None                   # here None IS correct: "there was nothing"
        return self._stack.pop()

    def next_to_undo(self):
        """Text for the interface, e.g. the Undo button's tooltip."""
        if self._stack.is_empty():
            return "Nothing to undo"
        action = self._stack.peek()
        return f"Undo: {action['type']} (task {action['task']})"

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

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

And a usage session on our usual task:

task = {"id": 7, "title": "Review budget", "priority": 2, "status": "pending"}
history = ActionHistory()

# The user changes the priority to 1: we save the PREVIOUS value before touching anything
history.record("change_priority", 7, {"priority": task["priority"]})
task["priority"] = 1

# The user marks it in progress
history.record("change_status", 7, {"status": task["status"]})
task["status"] = "in_progress"

print(history.next_to_undo())          # Undo: change_status (task 7)

# They press Undo: we retrieve the action and restore the previous data
action = history.undo()
task.update(action["prev_data"])
print(task["status"])                  # pending
print(history.total())                 # 1

Design details worth underlining:

  • prev_data is captured before modifying the task: it is the minimum information needed to revert. Recording afterward would be too late: the old value would already be gone.
  • Reverting is task.update(action["prev_data"]): since the previous data is a dict with the old fields, restoring them is one line.
  • undo returns None when there is nothing: does that contradict the previous lesson? No: the stack still raises IndexError; it is ActionHistory, the domain layer, that decides "undoing with no history" is not a programming error but a normal interface case. The exception lives in the structure; the tolerance, in the application.
  • Notice there is still no "redo": if the user undoes and regrets it, there is no way back. Solving that requires a second stack cooperating with this one — it is the first application of the next lesson.

Common Mistakes and Tips

  • Breaking encapsulation: accessing stack._items or stack._top from outside "because it's faster". You have just turned your stack into a list with no contract; the day you change the implementation, all that code dies.
  • Reversing the steps of the linked push: assigning self._top = new_node before new_node.next = self._top loses the entire previous stack. If your LinkedStack "only remembers the last element", this is why.
  • Forgetting the _size counter: without it, either size() traverses the stack (O(n), contract broken) or it returns wrong data. Every push adds one; every successful pop subtracts one (don't subtract before checking for emptiness).
  • Recording the action in the history after modifying the task: prev_data would already capture the new value, and undo would undo nothing. Capture first, then modify.
  • Comparing implementations without measuring: "the linked one will be faster because it's guaranteed O(1)" — you have just seen that it isn't. Reason with Big O, decide with timeit.
  • Tip: always write a check_contract-style function when you have two implementations of the same thing. It is the safety net that lets you switch implementations without fear.

Exercises

Exercise 1: BoundedStack

TaskFlow doesn't want an infinite history. Create a BoundedStack class that takes capacity in the constructor and behaves like Stack, except that push on a full stack raises OverflowError("stack full"). Add an is_full() method. Build it by inheriting from Stack (hint: super().__init__() and super().push(...)).

Exercise 2: __iter__ for LinkedStack

Add to LinkedStack an __iter__ method (a generator, like LinkedList's in module 2) that walks the data from top to bottom without modifying the stack. With it, list(stack) must return the elements in popping order. Extra question: why is "traversing a stack" strictly speaking a step outside the ADT, and why is it useful in practice anyway?

Exercise 3: reverting by action type

Write the function revert(action, tasks) for TaskFlow, where tasks is a dict of tasks by id (like the board in module 2) and action is a history dict. It must handle three types: "change_status" and "change_priority" (restore prev_data onto the task) and "create" (reverting a creation = deleting the task; in that case prev_data is {}).

Solutions

Solution 1:

class BoundedStack(Stack):
    def __init__(self, capacity):
        super().__init__()                 # initializes Stack's internal list
        self._capacity = capacity

    def is_full(self):
        return self.size() >= self._capacity

    def push(self, element):
        if self.is_full():
            raise OverflowError("stack full")
        super().push(element)              # delegates the actual push to Stack

Inheritance reuses everything (pop, peek, is_empty, size, __str__); only push adds the guard. Test: with capacity=2, the third push raises OverflowError. (In 03-05 we will see a more useful policy for a history: instead of failing, discard the oldest action.)

Solution 2:

class LinkedStack(LinkedStack):            # or add the method to the original class
    def __iter__(self):
        current = self._top
        while current is not None:
            yield current.data             # yields data from top to bottom
            current = current.next

It is the same generator pattern as LinkedList.__iter__: a current cursor advancing along next. list(stack) returns [top, ..., bottom], the exact order they would come out in with pop, but without removing them. On the extra question: the stack's contract only grants access to the top, so iterating is "cheating" on the pure ADT; in practice it is accepted as an inspection operation (debugging, displaying the history on screen) because it doesn't modify state. The red line is modifying during iteration.

Solution 3:

def revert(action, tasks):
    task_id = action["task"]
    if action["type"] == "create":
        # Undoing a creation means removing the task from the board
        del tasks[task_id]
    elif action["type"] in ("change_status", "change_priority"):
        # Restore the previous fields onto the existing task
        tasks[task_id].update(action["prev_data"])
    else:
        raise ValueError(f"unknown action type: {action['type']}")

Quick test:

tasks = {7: {"id": 7, "title": "Review budget", "priority": 1, "status": "in_progress"}}
action = {"type": "change_status", "task": 7, "prev_data": {"status": "pending"}}
revert(action, tasks)
print(tasks[7]["status"])   # pending

The else with ValueError is deliberate: if TaskFlow adds an action type tomorrow and we forget its reversal, better a loud error than an undo that doesn't undo.

Conclusion

You now have two complete, verified stacks: Stack, which encapsulates a list with the top at the back, and LinkedStack, which reincarnates module 2's insert_front/remove-the-head with the head renamed as the top. You have verified with a single test suite that both fulfill an identical contract — the essence of the ADT — and you have learned to tell them apart where they truly differ: amortized O(1) versus guaranteed O(1), memory consumption, and real constants measured with timeit (with the moral that two O(1)s can differ by a factor of 5). TaskFlow, for its part, now records and undoes actions with ActionHistory and its "capture the previous data, then modify" pattern. But it is missing something every user expects: regretting an undo. In the next lesson we will build the full undo/redo with two cooperating stacks, and we will see that stacks also validate parentheses, evaluate expressions, and hold up every function call Python executes.

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