Stacks & Execution Frames: The Invisible Engine of Compilers, Runtimes, and Undo Systems

Every time you press Ctrl+Z in an editor, write a nested mathematical formula, or trigger a RangeError: Maximum call stack size exceeded in production, you are interacting with the simplest—and most unforgiving—data structure in computer science.

---

In the third week of my undergraduate Data Structures course, I introduce the Stack. Compared to self-balancing trees or graph algorithms, students initially find the Stack almost suspiciously simple. It has only three primary operations:

1. push(item): Place an item on top of the stack in $O(1)$ time.
2. pop(): Remove and return the top item in $O(1)$ time.
3. peek(): Inspect the top item without removing it in $O(1)$ time.

Yet I always tell my class: "If you took away Binary Search Trees tomorrow, we could survive for a while with sorted arrays. If you took away the Stack, every CPU, compiler, programming language runtime, and web browser on Earth would halt within a microsecond."

Why does a strict LIFO (Last-In, First-Out) constraint give this humble structure such extraordinary power? Because LIFO is the mathematical mirror of nested context: the most recently opened scope, function call, or user action is always the very first one that must be closed, returned, or undone.

---

1. The Academic Foundation: LIFO Invariants and Hardware Call Stacks

A Stack is an Abstract Data Type (ADT) governed by the LIFO invariant: given a sequence of elements pushed at times $t_1 < t_2 < \dots < t_k$, the element popped first is strictly the element pushed at $t_k$.

How the CPU Hardware Stack Actually Works (RSP and RBP)

When you call a function in C, Rust, Python, or JavaScript, how does the computer remember where to return when the function finishes, and where do local variables live?

At the hardware level (such as x86-64 or ARM64), the CPU dedicates a special register called the Stack Pointer (RSP / SP) that points to the top of a contiguous region of RAM called the Call Stack. When Function A() calls Function B(), which in turn calls Function C(), the runtime pushes Activation Records (Stack Frames) onto the call stack:

flowchart TB
    subgraph CallStack["Process Call Stack in RAM (Grows Downward Toward Lower Addresses)"]
        direction TB
        F1["Frame 1: main()<br/>Return Addr: OS Loader<br/>Locals: config = {...}"] -->|"Calls calculateInvoice()"| F2["Frame 2: calculateInvoice(orderId = 402)<br/>Return Addr: main() + 0x18<br/>Locals: subtotal = 120.00"]
        F2 -->|"Calls applyTax()"| F3["Frame 3: applyTax(amount = 120.00, rate = 0.08)<br/>Return Addr: calculateInvoice() + 0x42<br/>Locals: tax = 9.60  <-- RSP (Top of Stack)"]
    end

1. When applyTax() finishes executing return 9.60, the CPU pops Frame 3 simply by adding the frame size back to the Stack Pointer register (RSP)—an $O(1)$ single-cycle instruction—and jumps back to Return Addr: calculateInvoice() + 0x42.
2. What causes a Stack Overflow (RangeError: Maximum call stack size exceeded)? Because the OS pre-allocates a fixed contiguous slice of virtual memory for each thread's call stack (typically $1\text{ MB}$ to $8\text{ MB}$, which you can convert to bytes using our Data Size Converter), an infinite or deeply nested recursion keeps pushing frames until RSP crosses the guard page boundary!

Time & Space Complexity of Stack Operations

Operation	Array-Backed Stack	Linked-List-Backed Stack	Notes
push(item)	$O(1)$ amortized	$O(1)$ worst-case	Array-backed wins on CPU L1 cache locality
pop()	$O(1)$	$O(1)$	Decrements top index; zero memory movement
peek()	$O(1)$	$O(1)$	Reads buffer[length - 1]
Auxiliary Space	$O(n)$	$O(n)$	Linked list adds pointer overhead per node

---

2. Two Classic University & Production Algorithms Powered by Stacks

Case Study A: Dual-Stack Undo/Redo State Engine

How do rich text editors, Figma, Photoshop, and Redux DevTools implement limitless Undo (Ctrl+Z) and Redo (Ctrl+Y)? They pair two stacks together: an undoStack and a redoStack.

stateDiagram-v2
    [*] --> Idle
    Idle --> ActionExecuted: execute(newState)
    ActionExecuted --> Idle: Push current to undoStack\nClear redoStack!
    Idle --> Undone: undo()
    Undone --> Idle: Pop from undoStack\nPush current to redoStack
    Idle --> Redone: redo()
    Redone --> Idle: Pop from redoStack\nPush current to undoStack

Notice the critical invariant in execute(newState): whenever a user performs a brand-new edit after undoing three steps, the redoStack must be cleared so history never branches into inconsistent timelines.

Case Study B: Edsger Dijkstra's Shunting-Yard Expression Evaluator

How does a spreadsheet engine, SQL query planner, or calculator evaluate an infix mathematical expression like "3 + 4 * 2 / ( 1 - 5 ) ^ 2" while respecting operator precedence (PEMDAS), parentheses, and right-associative exponentiation—without using unsafe eval()?

In 1961, Turing Award laureate Edsger Dijkstra invented the Shunting-Yard Algorithm, which uses an Operator Stack to convert human-readable infix notation into Reverse Polish Notation (Postfix / RPN), followed by an Operand Stack to evaluate the RPN tokens in a single linear $O(n)$ pass.

---

3. Under the Hood: Testable Undo/Redo Engine & Shunting-Yard Evaluator

Below is a complete, production-ready TypeScript implementation of both a Generic Dual-Stack Undo/Redo State Manager and Dijkstra's Shunting-Yard Mathematical Expression Evaluator.

Copy and execute this code directly in the JS/TS Playground:

/**
 * 1. Generic O(1) Array-Backed LIFO Stack
 */
class Stack<T> {
  private readonly items: T[] = [];

  public push(item: T): void {
    this.items.push(item);
  }

  public pop(): T | undefined {
    return this.items.pop();
  }

  public peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  public get size(): number {
    return this.items.length;
  }

  public isEmpty(): boolean {
    return this.items.length === 0;
  }

  public clear(): void {
    this.items.length = 0;
  }
}

/**
 * 2. Production Dual-Stack Undo/Redo State History Manager
 */
class UndoRedoHistory<State> {
  private currentState: State;
  private readonly undoStack = new Stack<State>();
  private readonly redoStack = new Stack<State>();
  private readonly maxHistory: number;

  constructor(initialState: State, maxHistory: number = 100) {
    this.currentState = initialState;
    this.maxHistory = maxHistory;
  }

  public get state(): State {
    return this.currentState;
  }

  public commit(nextState: State): void {
    this.undoStack.push(this.currentState);
    this.currentState = nextState;
    // Any new branch of edits invalidates the redo timeline
    this.redoStack.clear();
  }

  public undo(): State {
    const previous = this.undoStack.pop();
    if (previous === undefined) {
      return this.currentState;
    }
    this.redoStack.push(this.currentState);
    this.currentState = previous;
    return this.currentState;
  }

  public redo(): State {
    const next = this.redoStack.pop();
    if (next === undefined) {
      return this.currentState;
    }
    this.undoStack.push(this.currentState);
    this.currentState = next;
    return this.currentState;
  }

  public status() {
    return {
      current: this.currentState,
      canUndo: !this.undoStack.isEmpty(),
      canRedo: !this.redoStack.isEmpty(),
      undoDepth: this.undoStack.size,
      redoDepth: this.redoStack.size,
    };
  }
}

/**
 * 3. Dijkstra's Shunting-Yard Expression Parser & Postfix (RPN) Evaluator
 * Evaluates arithmetic expressions with +, -, *, /, ^ and parentheses safely without eval().
 */
interface OperatorMeta {
  precedence: number;
  associativity: "LEFT" | "RIGHT";
  apply: (a: number, b: number) => number;
}

const OPERATORS: Record<string, OperatorMeta> = {
  "+": { precedence: 1, associativity: "LEFT", apply: (a, b) => a + b },
  "-": { precedence: 1, associativity: "LEFT", apply: (a, b) => a - b },
  "*": { precedence: 2, associativity: "LEFT", apply: (a, b) => a * b },
  "/": {
    precedence: 2,
    associativity: "LEFT",
    apply: (a, b) => {
      if (b === 0) throw new Error("Division by zero");
      return a / b;
    },
  },
  "^": { precedence: 3, associativity: "RIGHT", apply: (a, b) => Math.pow(a, b) },
};

function tokenizeExpression(expr: string): string[] {
  const regex = /\d+(?:\.\d+)?|[+\-*/^()]/g;
  return expr.match(regex) ?? [];
}

function infixToPostfix(infix: string): string[] {
  const tokens = tokenizeExpression(infix);
  const outputQueue: string[] = [];
  const opStack = new Stack<string>();

  for (const token of tokens) {
    if (/^\d+(?:\.\d+)?$/.test(token)) {
      outputQueue.push(token);
    } else if (token in OPERATORS) {
      const currentOp = OPERATORS[token];
      while (!opStack.isEmpty()) {
        const topToken = opStack.peek()!;
        if (!(topToken in OPERATORS)) break;
        const topOp = OPERATORS[topToken];

        const shouldPop =
          (currentOp.associativity === "LEFT" && currentOp.precedence <= topOp.precedence) ||
          (currentOp.associativity === "RIGHT" && currentOp.precedence < topOp.precedence);

        if (shouldPop) {
          outputQueue.push(opStack.pop()!);
        } else {
          break;
        }
      }
      opStack.push(token);
    } else if (token === "(") {
      opStack.push(token);
    } else if (token === ")") {
      while (!opStack.isEmpty() && opStack.peek() !== "(") {
        outputQueue.push(opStack.pop()!);
      }
      if (opStack.isEmpty()) {
        throw new SyntaxError("Mismatched closing parenthesis ')'");
      }
      opStack.pop(); // Discard '('
    }
  }

  while (!opStack.isEmpty()) {
    const op = opStack.pop()!;
    if (op === "(" || op === ")") {
      throw new SyntaxError("Mismatched opening parenthesis '('");
    }
    outputQueue.push(op);
  }

  return outputQueue;
}

function evaluatePostfix(rpnTokens: string[]): number {
  const evalStack = new Stack<number>();

  for (const token of rpnTokens) {
    if (token in OPERATORS) {
      const right = evalStack.pop();
      const left = evalStack.pop();
      if (left === undefined || right === undefined) {
        throw new SyntaxError("Malformed expression: insufficient operands");
      }
      evalStack.push(OPERATORS[token].apply(left, right));
    } else {
      evalStack.push( Number(token) );
    }
  }

  if (evalStack.size !== 1) {
    throw new SyntaxError("Malformed expression: leftover operands");
  }
  return evalStack.pop()!;
}

// ============================================================================
// Verification & Execution
// ============================================================================
// Test 1: Undo/Redo State Engine
const editorHistory = new UndoRedoHistory<string>("Hello");
editorHistory.commit("Hello World");
editorHistory.commit("Hello World!");
console.log("Current Editor Text:", editorHistory.state); // "Hello World!"
console.log("After 1st Undo:", editorHistory.undo());     // "Hello World"
console.log("After 2nd Undo:", editorHistory.undo());     // "Hello"
console.log("After 1st Redo:", editorHistory.redo());     // "Hello World"

// Test 2: Shunting-Yard Compiler & RPN Evaluator
const formula = "3 + 4 * 2 / ( 1 - 5 ) ^ 2";
const rpn = infixToPostfix(formula);
const result = evaluatePostfix(rpn);
console.log("Infix Formula:", formula);
console.log("Compiled Postfix (RPN):", rpn.join(" ")); // "3 4 2 * 1 5 - 2 ^ / +"
console.log("Evaluated Result:", result);              // 3.5 (3 + 8 / 16)

---

4. Where Stacks Live in Modern Production Systems

1. WebAssembly (Wasm) and the JVM: Stack Machines

Have you ever wondered how WebAssembly runs C++, Rust, and Go code inside your browser at near-native speed across Intel, Apple Silicon, and Android chips?

WebAssembly is designed as a Virtual Stack Machine. Instead of assuming the host CPU has 16 or 32 physical registers, Wasm bytecode instructions (i32.const 10, i32.const 20, i32.add) push operands onto an implicit evaluation stack and pop them to push the result. Because every instruction's input and output types are statically known on the stack, browser JIT compilers (like V8's Liftoff and TurboFan) can validate Wasm modules in a single linear pass and map virtual stack slots directly onto physical CPU registers.

2. Compilers, JSON Parsers, and HTML/JSX AST Builders

When you paste a deeply nested configuration file into our JSON Formatter or write JSX in a React component, how does the parser verify that every { matches a }, every [ matches a ], and every <div className="card"> closes with </div> in the exact reverse order they were opened?

Every Pushdown Automaton (PDA) and recursive descent parser uses a Stack to track open lexical scopes. If an opening token arrives, it is pushed onto the syntax stack; when a closing token arrives, the parser pops the stack and asserts a match.

3. Converting Deep Recursion into Iterative Loops in Production

In university assignments, we write tree and graph Depth-First Search (DFS) recursively because it takes 5 lines of code. In production backend code, however, if a user uploads a deeply nested JSON document or AST with 50,000 levels of nesting, a recursive function will crash the Node.js or Python process with a StackOverflowError.

Senior engineers replace the implicit call stack with an explicit heap-allocated Stack<Node> inside a while (!stack.isEmpty()) loop. Because the heap can grow to gigabytes while the call stack is capped at a few megabytes, an explicit stack processes 50,000-deep structures effortlessly without crashing.

---

5. The Professor's Architecture Cheat Sheet

When to Choose a Stack:

• Reversing or Backtracking Workflows: Undo/Redo histories, browser back/forward navigation stacks, and maze/Constraint Satisfaction backtracking.
• Parsing & Lexical Validation: Matching delimiters, evaluating arithmetic/boolean expressions, and building Abstract Syntax Trees (ASTs).
• Eliminating Recursive Call Stack Overflows: Turning deep recursive DFS traversals into resilient iterative loops on the heap.
• Monotonic Stack Problems: Finding the "next greater element", stock span analysis, or largest rectangle in a histogram (which you can visualize with our Histogram Tool) in linear $O(n)$ time instead of $O(n^2)$.

When NOT to Choose a Stack:

• Fair Task Scheduling: A LIFO stack will starve older requests sitting at the bottom if new requests keep arriving! Whenever fairness or arrival-order processing is required, you need a Queue—the subject of our next article.