The Project | About Us | Contribute | Donations | License

HOME

In the previous lesson you met the stack ADT's contract: push, pop, peek, is_empty and size, all at O(1) cost. Now we are going to open up each operation and watch it work step by step, with traces of the stack's state after every move, exactly as you would when debugging. We will also make a design decision every author of data structures must face (what should happen when someone calls pop on an empty stack?), formulate the invariants every stack must satisfy, and apply all of it to TaskFlow's undo. To practice without waiting for the full implementation (lesson 03-03), we will use Python's list as a provisional stack. Mastering the fine mechanics of these operations is what will later let you implement them and, above all, reason confidently about any algorithm that uses stacks.

push: stacking step by step
pop: unstacking step by step
peek: look, don't touch
is_empty and size: the state queries
The empty-stack case: exception vs None
Invariants of the stack ADT
Sequences of operations: TaskFlow's undo
Guided mini-practice: list as a provisional stack

`push`: stacking step by step

push(element) places element on the top. It is the only way into a stack. Let's trace it starting from an empty stack, pushing actions from TaskFlow's history (we draw the stack vertically, top up, the way it really grows):

Operation	Stack state (top up)	`size()`
(start)	(empty)	0
`push("create task 7")`	`create task 7`	1
`push("change priority")`	`change priority` ← top `create task 7`	2
`push("mark in_progress")`	`mark in_progress` ← top `change priority` `create task 7`	3

Key points:

Each push covers the previous element: create task 7 is still there, but it is no longer reachable until everything above it is removed.
push never fails because of the stack's state: a (conceptual) stack has no capacity limit. (Bounded stacks exist — we will see one in an exercise in 03-05 with the history limit — but they are not part of the base contract.)
push returns nothing: its effect is the change of state.

As a diagram, the first two steps:

flowchart LR
    subgraph P1["After push(create task 7)"]
        direction TB
        a1["create task 7 ← top"]
    end
    subgraph P2["After push(change priority)"]
        direction TB
        b2["change priority ← top"]
        b1["create task 7"]
        b2 --- b1
    end
    P1 -->|"push(change priority)"| P2

`pop`: unstacking step by step

pop() does two things in one: it removes the top element and returns it. Let's continue the previous trace (the stack held 3 elements):

Operation	Returns	Stack state (top up)	`size()`
(previous state)	—	`mark in_progress` `change priority` `create task 7`	3
`pop()`	`"mark in_progress"`	`change priority` `create task 7`	2
`pop()`	`"change priority"`	`create task 7`	1
`pop()`	`"create task 7"`	(empty)	0
`pop()`	??	(empty)	0

Notice two things:

Elements come out in the reverse order they went in: they entered 7→priority→in_progress and left in_progress→priority→7. That is the essence of LIFO, and it is exactly the order an undo needs.
The fourth pop() is a problem: the stack is empty and there is nothing to return. That "??" deserves its own section (number 5).

A common pattern is to drain a stack while processing each element:

while not stack_is_empty():
    element = pop()
    process(element)

This loop processes elements in reverse insertion order. Memorize the pattern: we will use it again and again (undo everything, reverse sequences, evaluate expressions...).

`peek`: look, don't touch

peek() returns the top element without removing it. The stack stays exactly the same:

Operation	Returns	State after the operation
(previous state)	—	`change priority` `create task 7`
`peek()`	`"change priority"`	`change priority` `create task 7` (identical)
`peek()`	`"change priority"`	(identical: peek is repeatable)
`pop()`	`"change priority"`	`create task 7`

What is it for, if pop already returns the top? For deciding before acting. Two typical uses in TaskFlow:

The interface wants to show "Undo: change priority" on the button. It needs to read the next action without undoing it: peek.
An algorithm wants to pop only if the top satisfies a condition (you will see this in the expression conversion of 03-04): first peek, check the condition, and only then pop.

Golden rule: if the stack changed after calling a query operation, that operation is implemented wrong. peek, is_empty and size are observers; push and pop are mutators.

`is_empty` and `size`: the state queries

is_empty() returns True if size() == 0. It is the natural guard before any pop or peek, and the stopping condition of the draining loop.
size() returns the number of elements. To make it O(1), the implementation will keep a counter incremented on every push and decremented on every pop — the same technique as LinkedList's size attribute in module 2, where counting by traversal would have cost O(n).

They may look trivial, but these two operations are what make using the stack safe: nearly every stack bug is a pop without checking is_empty first.

The empty-stack case: exception vs `None`

What should pop() (or peek()) do on an empty stack? It is a design decision, and the two reasonable options have different consequences:

Strategy	Behavior	Advantages	Drawbacks
Raise an exception	`raise IndexError("pop from an empty stack")`	The error cannot go unnoticed; it forces the caller to think; it is what Python's `list.pop()` does	Requires `try/except` or a prior check
Return `None`	`return None`	Shorter caller code	Silent bug: if someone pushes `None` as a legitimate value, you cannot tell "empty stack" from "the top was None"; the error blows up far from its cause

In this course we adopt the exception, for two reasons:

Consistency with Python: [].pop() raises IndexError. Our stack will behave like the rest of the language.
Fail fast and loud: an unexpected None can travel through half the program before breaking something, and by then the traceback doesn't point at the cause. An exception at the guilty pop points exactly at the error.

The caller then has two correct styles, both valid:

# Style 1: look before you leap (LBYL)
if not history_is_empty():
    action = pop_action()
    revert(action)
else:
    print("Nothing to undo")

# Style 2: ask forgiveness, not permission (EAFP, the idiomatic style in Python)
try:
    action = pop_action()
    revert(action)
except IndexError:
    print("Nothing to undo")

What matters is not which style you pick, but that the decision "exception, not None" is written into the contract, so every user of the stack can rely on it.

Invariants of the stack ADT

An invariant is a property that holds always, before and after every operation (we already reasoned this way in module 2, when we kept head, tail and size consistent after every insertion). The stack's invariants are the "quality control" of any implementation:

size() >= 0 at all times; and is_empty() is equivalent to size() == 0.
After push(x): peek() returns x, and size() has grown by exactly 1.
pop() right after push(x) (no operations in between) returns x and leaves the stack exactly as it was before the push. That is: pop undoes push.
peek() modifies nothing: size() and the contents are identical before and after.
Global LIFO order: if n elements are pushed and then n are popped, they come out in exactly reverse order.

These invariants translate directly into tests. When we implement the two stacks of lesson 03-03, either of them must pass exactly the same checks: that is the practical proof that the ADT is independent of the implementation.

Sequences of operations: TaskFlow's undo

Let's play out a realistic TaskFlow session, still in contract pseudocode. Every user action is recorded with push; every press of Undo runs pop and reverts. We follow the task {"id": 7, "title": "Review budget", "priority": 2, "status": "pending"}:

#	The user...	Operation on the stack	History stack (top up)
1	Creates task 7	`push(create id=7)`	`create 7`
2	Raises priority 2→1	`push(priority 7: 2→1)`	`priority 2→1` `create 7`
3	Marks it in progress	`push(status 7: pending→in_progress)`	`status →in_progress` `priority 2→1` `create 7`
4	Presses Undo	`pop()` → reverts status to `pending`	`priority 2→1` `create 7`
5	Assigns to Anna	`push(assign 7 to anna)`	`assign anna` `priority 2→1` `create 7`
6	Presses Undo	`pop()` → removes the assignment	`priority 2→1` `create 7`
7	Presses Undo	`pop()` → priority goes back to 2	`create 7`
8	Presses Undo	`pop()` → task 7 is deleted	(empty)
9	Presses Undo	`is_empty()` is `True` → button disabled, `pop` is not called	(empty)

Two important observations:

In step 4 the status was undone, and in step 5 the user did something new. The undone action does not "come back": the stack only records what is currently in effect. (What if they wanted to redo it? We would need a second stack; that is exactly the undo/redo construction of lesson 03-04.)
Every pushed action carries the information needed to revert it (the previous value: 2→1, pending→in_progress). In 03-03 we will formalize this with dictionaries {"type": ..., "task": ..., "prev_data": ...}.

Guided mini-practice: `list` as a provisional stack

We don't have our Stack class yet (it arrives in 03-03), but Python's list can serve as a provisional stack, because its operations at the back are the right ones:

my_list.append(x) → acts as push → amortized O(1).
my_list.pop() (no argument) → acts as pop → O(1).
my_list[-1] → acts as peek → O(1).
len(my_list) == 0 → acts as is_empty → O(1).

Why the BACK and not the front? Remember the trap from module 1: insert(0, x) and pop(0) are O(n), because a list is a dynamic array and touching the front forces every element to shift. The top of our provisional stack must be the back of the list, where the array works in O(1). A stack built with insert(0)/pop(0) "works" but degrades every operation to O(n): it would break the contract's cost table.

Open an interpreter and reproduce the TaskFlow session from the previous section:

history = []            # empty stack (provisional, on a list)

# The user works: each action is pushed with append (= push)
history.append("create task 7")
history.append("task 7 priority: 2 -> 1")
history.append("task 7 status: pending -> in_progress")

print(len(history))     # 3  (= size)
print(history[-1])      # 'task 7 status: pending -> in_progress'  (= peek: nothing removed)

# Press Undo: pop() removes and returns the top
action = history.pop()
print(f"Undoing: {action}")       # Undoing: task 7 status: pending -> in_progress
print(history[-1])                # 'task 7 priority: 2 -> 1'  (new top)

# Undo everything with the draining pattern
while len(history) > 0:           # (= not is_empty)
    print(f"Undoing: {history.pop()}")
# Undoing: task 7 priority: 2 -> 1
# Undoing: create task 7

history.pop()                     # IndexError: pop from empty list

Line-by-line explanation:

history = [] creates the empty stack. The empty list is our empty stack.
The three append calls push in order; after them, the top (the back of the list) is the most recent action.
history[-1] reads the top without removing it: it is our peek. Careful: on an empty list, [-1] also raises IndexError, consistent with our design decision.
history.pop() with no argument removes from the back: LIFO guaranteed, and O(1).
The while loop is the draining pattern: it prints the actions in the reverse order they happened, which is exactly the right order for an "undo everything".
The last pop() on the empty list raises IndexError: Python already implements the exception strategy we chose.

This provisional stack is fully functional, but it has one flaw: it does not protect the contract. Nothing prevents another programmer from doing history.insert(0, x) or history[3] and breaking LIFO discipline. Encapsulating the list inside a class that exposes only the five operations is precisely the job of the next lesson.

Common Mistakes and Tips

Calling pop without checking first (or without try/except): the classic IndexError in production. Every call to pop/peek must be protected by is_empty() or by an except IndexError.
Using pop(0) or insert(0, x) on the list-as-stack: it works, but it turns O(1) into O(n). The top lives at the back of the list. If in doubt, go back to the list cost table from module 1.
Using pop when you only meant to look: if you need the top again after "looking" at it, you have destroyed information. Query = peek (my_list[-1]); extraction = pop.
Returning None on an empty stack "to keep it simple": you end up with if result is not None scattered all over the code, and bugs whenever None is a valid value. Exception, period.
Forgetting that pop returns the element: writing stack.pop() and then trying to read the top with peek to find out "what was popped" — too late, it was the return value of that very pop.
Tip: when writing or debugging sequences of operations, draw the trace in a table like the ones in this lesson (operation → returns → state). Two minutes of table save twenty of debugger.

Exercises

Exercise 1: full trace

Starting from an empty stack, build the trace table (operation, returned value, stack state, size) for this sequence:

push(10)
push(20)
peek()
push(30)
pop()
pop()
push(40)
peek()
pop()
pop()
pop()

Indicate at which step (if any) an IndexError is raised, according to our design decision.

Exercise 2: the safe "undo everything"

Using a list as a provisional stack, write a function undo_all(history) that takes the stack of actions (a list of strings) and returns a list of the messages "Undoing: <action>" in the correct undo order, leaving the stack empty. The function must never fail, not even if it receives an already-empty stack. Write two versions: one in LBYL style (check first) and one in EAFP style (try/except).

Exercise 3: spot the broken implementation

A colleague has written these "stack operations" on top of list. Point out all the errors with respect to this lesson's contract and invariants, and fix them:

def push(stack, element):
    stack.insert(0, element)

def pop(stack):
    if len(stack) == 0:
        return None
    return stack.pop(0)

def peek(stack):
    return stack.pop(0)

Solutions

Solution 1:

Step	Operation	Returns	Stack (top up)	Size
1	`push(10)`	—	`10`	1
2	`push(20)`	—	`20`, `10`	2
3	`peek()`	`20`	`20`, `10`	2
4	`push(30)`	—	`30`, `20`, `10`	3
5	`pop()`	`30`	`20`, `10`	2
6	`pop()`	`20`	`10`	1
7	`push(40)`	—	`40`, `10`	2
8	`peek()`	`40`	`40`, `10`	2
9	`pop()`	`40`	`10`	1
10	`pop()`	`10`	(empty)	0
11	`pop()`	`IndexError`	(empty)	0

Step 11 raises IndexError: the stack is empty and we chose exception, not None.

Solution 2:

# LBYL version: check before popping
def undo_all(history):
    messages = []
    while len(history) > 0:            # guard: only pop if not empty
        action = history.pop()         # removes the top (the most recent)
        messages.append(f"Undoing: {action}")
    return messages

# EAFP version: try, and catch the exception
def undo_all_eafp(history):
    messages = []
    while True:
        try:
            action = history.pop()
        except IndexError:             # stack exhausted: we're done
            break
        messages.append(f"Undoing: {action}")
    return messages

Both return the messages in reverse insertion order (the correct undo order) and leave history empty. With an already-empty stack, the first version's while never runs and the second version's try breaks the loop on the first pass: neither fails.

Solution 3: there are four errors.

push uses insert(0, ...): it pushes at the front of the list → O(n) due to the array shift. It breaks the contract's cost.
pop uses pop(0): same problem, O(n). (Curiously, the combination "insert and remove at the front" preserves LIFO order, so it works... extremely slowly. The performance bug is the most treacherous kind, because correctness tests don't catch it.)
pop returns None on an empty stack: it contradicts the design decision; it should let the exception fly (or raise it explicitly).
peek does pop(0): it removes the element! It violates invariant 4 (peek modifies nothing). It must be read-only.

Corrected version:

def push(stack, element):
    stack.append(element)        # top = back of the list: O(1)

def pop(stack):
    return stack.pop()           # removes from the back: O(1); IndexError if empty

def peek(stack):
    return stack[-1]             # read-only: O(1); IndexError if empty

Conclusion

You now command the full mechanics of the stack ADT: push covers the previous top, pop removes and returns in a single gesture, peek observes without modifying, and is_empty/size make everything else safe. You have made a reasoned design decision (an IndexError exception on an empty stack, just like Python's own list), formulated the invariants any implementation must satisfy, and traced real TaskFlow undo sessions operation by operation. You also have a provisional stack running on a list — always at the back, never the front — though it lacks the essential piece: a boundary that prevents bypassing the contract. In the next lesson we will build that boundary twice: a Stack class on top of list and a LinkedStack on the nodes from module 2, we will measure both with timeit, and we will assemble TaskFlow's real ActionHistory.

Basic Stack Operations

Contents

`push`: stacking step by step

`pop`: unstacking step by step

`peek`: look, don't touch

`is_empty` and `size`: the state queries

The empty-stack case: exception vs `None`

Invariants of the stack ADT

Sequences of operations: TaskFlow's undo

Guided mini-practice: `list` as a provisional stack

Common Mistakes and Tips

Exercises

Exercise 1: full trace

Exercise 2: the safe "undo everything"

Exercise 3: spot the broken implementation

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Basic Stack Operations

Contents

push: stacking step by step

pop: unstacking step by step

peek: look, don't touch

is_empty and size: the state queries

The empty-stack case: exception vs None

Invariants of the stack ADT

Sequences of operations: TaskFlow's undo

Guided mini-practice: list as a provisional stack

Common Mistakes and Tips

Exercises

Exercise 1: full trace

Exercise 2: the safe "undo everything"

Exercise 3: spot the broken implementation

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

`push`: stacking step by step

`pop`: unstacking step by step

`peek`: look, don't touch

`is_empty` and `size`: the state queries

The empty-stack case: exception vs `None`

Guided mini-practice: `list` as a provisional stack