Stacks: last-in-first-out for reversible edits

Last updated: 5 Oct 20269 min read

tutorial

A stack exposes push, peek, and pop at one end. Its last-in-first-out order makes it suitable for nested parsing, depth-first traversal, and undo records. The invariant is order, not storage form: a resizable array can implement a stack with amortized O(1) push and O(1) pop from the end. An undo stack should hold inverse operations or enough prior state to restore them; storing only human-readable action names cannot reverse a mutation. Decide whether failed operations enter the history and what an empty pop means before exposing the API.

Operational case

A shipment editor changes S-47 from 'queued' to 'held' and then from 'held' to 'reviewed.' To undo the latest edit, it restores 'held'; another undo restores 'queued.' The stack stores prior states in commit order, so two pops retrieve them backward. If an edit fails after partially changing external systems, a local stack is not an authoritative transaction log. The example is a local state demonstration, and a real workflow would reconcile server receipts before offering undo.

Working Python program

shipment_state = "queued"
undo_states = []
for next_state in ("held", "reviewed"):
    undo_states.append(shipment_state)
    shipment_state = next_state
shipment_state = undo_states.pop()
print(shipment_state, undo_states)

Output

held ['queued']

Time, space, and tradeoff

For m edits, the stack uses O(m) space. Each shown push is amortized O(1), and pop is O(1); history retention still needs a bound if sessions can run indefinitely. Using list.pop(0) would move remaining entries and break the intended constant-time end operation. A stored reference to mutable state may change later, so capture an immutable value or controlled copy when the undo record must represent the earlier state.

Common Mistakes

Do not pop an empty stack without an explicit result or error policy.
Do not store only the new value when undo needs the old value.
Do not assume local undo reverses a remote side effect.

Connected lessons

data structures

stacks-and-queues