Undo Mechanisms and Other Real-World Use Cases

Stacks are among the most elegantly practical data structures in computer science. At first glance, the concept of a last-in, first-out collection might seem abstract, but once you start looking for stacks in the software you use every day, they appear everywhere. From the undo button in a text editor to the way your web browser remembers where you have been, from the invisible machinery that makes function calls work to the algorithms that solve mazes, stacks are the silent engine powering an enormous range of familiar features. Understanding these real-world applications does more than satisfy curiosity — it gives developers a mental model for reasoning about performance, anticipating edge cases, and implementing or debugging features with confidence.

The single defining property of a stack — Last In, First Out (LIFO) — is precisely what makes it the right tool for all of these scenarios. In each case, the most recent thing that happened is the first thing that needs to be addressed. That insight is the thread connecting every application discussed below.

The Undo Operation: A Classic Stack Use Case

The undo feature is the textbook example of a stack in action, and for good reason: it maps almost perfectly onto the LIFO principle. Every time a user performs an action in an application — typing a character, deleting a word, changing a font, moving an object — a record of that action is created and pushed onto an action stack. The stack grows with each action, preserving the full ordered history of what the user has done.

When the user presses Ctrl+Z (or Cmd+Z on macOS), the application pops the top item from the action stack and reverses it. Because the stack is LIFO, the most recently performed action is always on top and is therefore always the first one undone. This guarantees that actions are reversed in the exact reverse order they were performed — which is exactly what users expect. If you typed "Hello", then bolded it, then changed the font size, pressing undo three times will reverse the font size change first, then remove the bold, then remove the typed text. Any other order would feel broken.

Consider a simplified representation of that sequence:

Action Stack after three operations:
┌─────────────────────────────┐
│  [TOP] Change font size     │  ← popped first on undo
│        Apply bold           │  ← popped second on undo
│        Type "Hello"         │  ← popped third on undo
└─────────────────────────────┘

A well-designed undo system also supports redo. When an action is popped off the action stack during an undo, it is not simply discarded — it is pushed onto a separate redo stack. This means the user can reapply an action that was just undone. Pressing Ctrl+Y (or Ctrl+Shift+Z) pops from the redo stack and pushes back onto the action stack, moving the application forward again.

There is one important nuance: if the user performs a new action after undoing some steps, the redo stack is typically cleared. This makes sense — the user has branched off in a new direction, so the previously undone future is no longer reachable. This behavior is a direct consequence of treating history as a linear stack rather than a tree of possibilities.

In code, a basic undo/redo manager might look like this:

class UndoManager:
    def __init__(self):
        self.action_stack = []   # Stores performed actions
        self.redo_stack = []     # Stores undone actions

    def perform(self, action):
        action.execute()
        self.action_stack.append(action)  # Push onto action stack
        self.redo_stack.clear()           # New action clears redo history

    def undo(self):
        if self.action_stack:
            action = self.action_stack.pop()   # Pop last action
            action.reverse()
            self.redo_stack.append(action)     # Push onto redo stack

    def redo(self):
        if self.redo_stack:
            action = self.redo_stack.pop()     # Pop from redo stack
            action.execute()
            self.action_stack.append(action)   # Push back onto action stack

Each action object knows how to execute itself and how to reverse itself. The two stacks work in concert to give the user full control over their history. This pattern is sometimes formalized as the Command design pattern in object-oriented programming, where each user operation is encapsulated as an object — but the stack mechanism underneath remains the same.

Browser History and Navigation

Web browsers provide another beautifully intuitive example of stack behavior. As you navigate from page to page, each new URL you visit is pushed onto a history stack. The stack at any given moment represents the sequence of pages you have visited, with the most recently visited page sitting on top.

When you click the Back button, the browser pops the current page off the stack and navigates to the page that is now on top — the one you visited immediately before. This is pure LIFO behavior. Clicking Back repeatedly continues popping pages in reverse order, retracing your navigation path exactly.

Many browsers implement this with two stacks, very much like the undo/redo pattern:

• Back stack: Holds the history of pages visited, with the current page on top.
• Forward stack: Holds pages that were visited but then navigated away from using the Back button.

When you press Back, the current page is popped from the back stack and pushed onto the forward stack. When you press Forward, the top of the forward stack is popped and pushed back onto the back stack. This is exactly analogous to the undo/redo stacks described above.

The critical moment that confirms the stack semantics is what happens when you navigate to a brand-new page after having pressed Back. The forward stack is cleared entirely. Just as with undo history, branching off in a new direction invalidates the previously accessible future. You cannot go forward to pages that are no longer part of your current navigation path.

Example navigation sequence:

Visit A → Visit B → Visit C
Back stack: [A, B, C]  (C is current, on top)
Forward stack: []

Press Back:
Back stack: [A, B]     (B is now current)
Forward stack: [C]

Press Back again:
Back stack: [A]        (A is now current)
Forward stack: [C, B]

Now visit NEW page D:
Back stack: [A, D]     (D is now current)
Forward stack: []      ← forward history is wiped

Modern browsers also expose this stack behavior programmatically through the History API in JavaScript, allowing single-page applications to push and replace entries on the history stack without full page reloads:

// Push a new state onto the history stack
history.pushState({ page: 'profile' }, 'Profile', '/profile');

// Replace the current top of the stack without adding a new entry
history.replaceState({ page: 'home' }, 'Home', '/');

// Navigate programmatically
history.back();    // equivalent to pressing Back
history.forward(); // equivalent to pressing Forward
history.go(-2);    // go back two entries

The Call Stack in Program Execution

Perhaps the most fundamental and universal use of a stack in computing is the call stack, also known as the execution stack or runtime stack. Every time a program calls a function, the runtime must keep track of where to return when that function finishes. The call stack is the mechanism that makes this possible.

When a function is invoked, a stack frame (also called an activation record) is pushed onto the call stack. This frame contains:

• The function's local variables
• The function's parameters
• The return address — the location in the calling function's code where execution should resume after this function returns
• Sometimes a reference to the calling frame (for debugging and stack unwinding)

When the function finishes executing, its frame is popped off the stack, and execution resumes at the return address stored in that frame — which puts control back in the function that made the call. This process repeats for every function call, no matter how deeply nested.

Consider this simple chain of function calls:

def main():
    result = add(3, 4)
    print(result)

def add(a, b):
    return multiply(a) + multiply(b)

def multiply(x):
    return x * 2

main()

The call stack evolves like this:

1. main() is called:
   Stack: [main]

2. main calls add(3, 4):
   Stack: [main, add]

3. add calls multiply(3):
   Stack: [main, add, multiply]

4. multiply(3) returns 6, frame popped:
   Stack: [main, add]

5. add calls multiply(4):
   Stack: [main, add, multiply]

6. multiply(4) returns 8, frame popped:
   Stack: [main, add]

7. add returns 14, frame popped:
   Stack: [main]

8. main finishes, frame popped:
   Stack: []

This is also why recursive functions can be dangerous if the recursion is too deep. Each recursive call adds a new frame to the stack. If the base case is never reached, or if the input is enormous, the stack eventually runs out of memory. This produces the infamous stack overflow error — a name that literally describes the stack overflowing its allocated memory space. The popular programming Q&A website Stack Overflow is named after this very phenomenon.

def infinite_recursion():
    return infinite_recursion()  # Each call pushes a frame, none are popped

infinite_recursion()
# RecursionError: maximum recursion depth exceeded

Understanding the call stack also helps explain concepts like stack traces in error messages. When an exception is raised, the runtime prints the current contents of the call stack — the sequence of function calls that led to the error — giving developers a precise map of how execution arrived at the problem.

Expression Evaluation and Syntax Parsing

Stacks are indispensable tools in the parsing and evaluation of expressions, appearing in tasks ranging from simple bracket matching to full arithmetic evaluation.

Bracket Matching

A very common programming interview problem — and a very real compiler task — is determining whether a string of brackets is properly balanced. The stack solution is elegant: scan the string from left to right, and whenever you encounter an opening bracket ((, [, or {), push it onto the stack. Whenever you encounter a closing bracket, pop the top of the stack and check whether it matches the closing bracket's corresponding opener.

• If the stack is empty when a closing bracket appears, there is no matching opener — the expression is invalid.
• If the popped opener does not match the closing bracket (e.g., you find ) but the top of the stack was [), the expression is invalid.
• If after scanning the entire string the stack is not empty, there are unmatched openers — the expression is invalid.
• Only if all closing brackets were matched and the stack is empty at the end is the expression valid.

def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    openers = set(matching.values())

    for char in expression:
        if char in openers:
            stack.append(char)          # Push opening bracket
        elif char in matching:
            if not stack or stack[-1] != matching[char]:
                return False            # Empty stack or mismatch
            stack.pop()                 # Pop matching opener

    return len(stack) == 0             # True only if all matched

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False — mismatch
print(is_balanced("((()"))     # False — unclosed openers remain

Operator Precedence and the Shunting Yard Algorithm

Evaluating arithmetic expressions like 3 + 4 * 2 correctly requires respecting operator precedence (multiplication before addition). The Shunting Yard Algorithm, devised by Edsger Dijkstra, uses a stack to hold operators while reordering an infix expression (the way humans write it) into postfix notation (also called Reverse Polish Notation), which is easier for computers to evaluate.

In the process, operators are pushed onto and popped from the stack according to their precedence. A higher-precedence operator that is already on the stack gets applied before a new lower-precedence operator is pushed. This ensures that * is applied before +, even though + appeared first in the expression.

The following table summarizes the stack state at each step for the expression 3 + 4 * 2:

The output 3 4 2 * + is postfix notation. Evaluating it with another stack yields (4 * 2) + 3 = 11, the correct result. Compilers and interpreters use variations of this technique to parse and evaluate source code expressions.

Backtracking Algorithms

Backtracking is a problem-solving strategy used when you need to explore multiple possible paths and retreat when a path proves unfruitful. Stacks are the natural mechanism for implementing backtracking, because they let you save your current state before exploring a new direction and restore it exactly if that direction fails.

The general pattern is:

• At each decision point, push the current state (position, partial solution, remaining choices) onto the stack.
• Explore one possible next step.
• If that step leads to a dead end, pop the last saved state from the stack and try a different option — this is the "backtrack" step.
• Continue until a solution is found or all possibilities are exhausted.

A maze solver is the classic illustration. Imagine navigating a grid where some cells are walls and others are open paths. Starting from the entrance, at each open cell you may be able to go in multiple directions. You pick one, move, and save your position. If you hit a dead end — a cell with no unvisited neighbors — you pop the stack to return to the last junction and try a different direction.

def solve_maze(maze, start, end):
    stack = [start]         # Begin with starting position
    visited = set()
    visited.add(start)
    parent = {start: None}  # Track path for reconstruction

    while stack:
        current = stack.pop()   # Pop current position

        if current == end:
            return reconstruct_path(parent, end)

        row, col = current
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:  # Four directions
            neighbor = (row + dr, col + dc)
            if is_valid(maze, neighbor) and neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                stack.append(neighbor)  # Push new position to explore

    return None  # No path found

This iterative approach using an explicit stack is equivalent to the recursive depth-first search, where the call stack itself serves as the implicit backtracking mechanism. In fact, any recursive backtracking algorithm can be rewritten using an explicit stack, and understanding this equivalence is a powerful insight.

Beyond maze solving, backtracking with a stack powers a wide variety of algorithms:

• Puzzle solvers: Sudoku, the N-Queens problem, and crossword generation all use backtracking to explore candidate placements and retreat when a contradiction is found.
• Constraint satisfaction problems (CSPs): Scheduling problems, graph coloring, and logic puzzles are solved by assigning values, detecting violations, and backtracking to try different assignments.
• Game tree search: Simple game AIs explore possible moves using a stack-based depth-first search, backtracking when a branch is evaluated or pruned.
• File system traversal: Walking a directory tree depth-first uses a stack to push subdirectories and pop them when their contents have been processed.

Connecting Abstract Concepts to Familiar Tools

A crucial insight for any developer is that abstract data structures are not theoretical curiosities invented for computer science textbooks — they are the hidden infrastructure behind the software features that billions of people use every day. The undo button in a word processor, the Back button in a browser, the error trace that appears when a program crashes, the way a compiler checks that your parentheses are balanced: all of these are stacks in disguise.

Recognizing a stack when you encounter one in a real application has several practical benefits:

• Reasoning about performance: Stack operations (push and pop) are O(1) — constant time — which means undo and redo operations are extremely fast regardless of how long the undo history is. Knowing this helps you set appropriate expectations and spot potential bottlenecks elsewhere (such as the storage cost of maintaining a very long history).
• Understanding limitations: A stack-based undo system is inherently linear — it does not support branching history. If you want a "version tree" where multiple alternative futures can coexist, you need a more complex data structure. Knowing the stack model's limitations tells you when to reach for something else.
• Implementing features correctly: If you are building an application that needs undo functionality, knowing the stack pattern means you can implement it systematically and correctly from the start, rather than reinventing it ad hoc.
• Debugging more effectively: When a call stack trace appears in an error message, understanding that it represents a stack of function frames lets you read it correctly — from the most recent call (top) back to the original entry point (bottom).

The following table summarizes the real-world applications covered and maps each to the corresponding stack operations:

The power of truly understanding a data structure is that you stop seeing it only as an abstract concept and start recognizing it as a tool with a specific shape — one that fits certain problems perfectly and fits others poorly. Stacks are the right shape for any problem where the most recent thing is the most important thing, where you need to reverse a sequence, or where you need to remember where you came from in order to find your way back. Once that shape becomes familiar, you will spot opportunities to use it — and opportunities to avoid misusing it — throughout your career as a developer.