Module F-6·12 min read

LIFO structure, the call stack, and balanced-bracket and expression-parsing patterns.

Written by Jatin Jain Saraf · Architect of SupraScan

Module F-6 — Stacks: LIFO, the Call Stack, and Expression Parsing

Q: Why does `push()`/`pop()` at the end of an array (as used inside the `Stack` class) stay O(1), the same reasoning established for arrays back in Module F-2?

Because operating only at the end of the array means no other elements ever need to shift position to keep the array contiguous — the same reasoning that made `array.push()`/`array.pop()` O(1) and `array.unshift()`/`array.shift()` O(n) in Module F-2. — The module explicitly frames the stack as "a thin wrapper" over the array from Module F-2, restricted to exactly the operations (append/remove at the end) that never require shifting other elements. This is the identical reasoning from Module F-2 explaining why `push`/`pop` are O(1) while `unshift`/`shift` are O(n) — a stack's discipline of only touching one end is what preserves that O(1) property. Option A is false — the module is explicit that a stack is not a new memory layout, just a constrained way of using an array. Option C fabricates an engine-level special case that doesn't exist and isn't mentioned. Option D invents an arbitrary and incorrect size threshold; O(1) here holds regardless of stack size.

Q: In `isBalanced`, why does the function return `false` for the input `"(()"` even though every character in the string is a valid, correctly-typed bracket?

Two opening brackets are pushed but only one closing bracket appears to pop and match one of them — after the loop finishes, the stack still contains one unmatched opening bracket, and the final `stack.length === 0` check catches that it was never resolved. — Walking through `"(()"`: both `(` characters get pushed (stack now holds two entries), then the single `)` pops and matches the most recently pushed `(`, leaving one `(` still on the stack when the string ends. The function's final check, `stack.length === 0`, specifically exists to catch exactly this case — brackets that were opened but never closed. Option A incorrectly asserts the function is buggy; returning `false` here is the correct behavior for an unbalanced expression. Option C invents a length-based rule the function does not implement — it only ever inspects bracket characters, not string length. Option D is incorrect — `pairs` is only consulted when a closing bracket is encountered (to look up which opener it should match), not for opening brackets, so no lookup failure occurs here.

Q: The module states that `nextGreaterElement` is O(n) overall, "despite the nested-looking `while` inside a `for`." What is the reasoning behind that claim?

Each index is pushed onto the stack exactly once and popped at most once across the entire run, so even though the `while` loop appears nested inside the `for` loop, the total number of pop operations across all iterations combined cannot exceed n — making the overall work O(n), not O(n²). — The key insight the module gives is to count total operations across the entire run, not per outer-loop iteration in isolation: every index is pushed exactly once (inside the `for` loop) and can be popped at most once (inside the `while` loop, across all iterations combined) — so the combined number of pushes and pops is bounded by 2n, not n². This "amortized across the whole run" reasoning is exactly the same kind of argument used for dynamic array resizing (Module F-2) and hash map rehashing (Module F-4). Option A is false — the `while` loop can and does run multiple times on a single outer-loop iteration (e.g., when several smaller previous elements get popped at once); the point is that this doesn't happen an unbounded number of times overall. Option C fabricates a nonexistent JavaScript engine optimization. Option D directly contradicts the module's explicit and correctly-reasoned O(n) claim.

What this module covers: A stack is one of the simplest structures in this course — and it's already running underneath every function call you've ever written, whether you knew it or not. This module covers the stack as an abstract data type, how it's built on top of the array from Module F-2, the call stack that governs recursion and stack overflows, and the balanced-bracket and expression-parsing patterns a stack solves cleanly.

The Stack: Last-In, First-Out

A stack supports exactly three operations, all O(1): push (add to the top), pop (remove from the top), and peek (look at the top without removing it). You can only ever interact with the most recently added item — everything below it is inaccessible until the items above it are popped off.

class Stack<T> {
  private items: T[] = [];
 
  push(item: T): void {
    this.items.push(item); // O(1) — Module F-2: appending at the end never shifts anything
  }
 
  pop(): T | undefined {
    return this.items.pop(); // O(1) — removing from the end never shifts anything
  }
 
  peek(): T | undefined {
    return this.items[this.items.length - 1]; // O(1) — direct index access
  }
 
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

Notice this is just a thin wrapper around the array from Module F-2 — a stack isn't a new memory layout, it's a discipline about which operations you allow. Restricting yourself to push/pop/peek at one end is precisely what keeps every operation O(1): those are exactly the array operations that never require shifting other elements.

Analogy: A stack is a pile of plates. You put a new plate on top (push), and you take the top plate off (pop). You cannot pull a plate from the middle without first removing everything stacked above it — the same constraint the data structure enforces.

The Call Stack: Where Your Functions Actually Live

Every time you call a function, the runtime pushes a stack frame — the function's local variables, its arguments, and the address to return to — onto the call stack. When the function returns, its frame is popped, and execution resumes exactly where the caller left off.

function three() { console.log('three'); }      // pushed last, popped first
function two() { three(); }                      // pushed second
function one() { two(); }                        // pushed first
one();
// Call stack grows: one() -> two() -> three()
// Call stack unwinds: three() returns -> two() returns -> one() returns

This is a real stack, following the exact same LIFO rule as the Stack class above — the last function called is the first one to return, because it's sitting on top of everyone waiting on it. This is also why deep, unbounded recursion causes a stack overflow: each recursive call pushes another frame, and if the recursion never reaches its base case, frames pile up until the call stack — a fixed-size region of memory — runs out of room.

function infiniteRecursion(n: number): number {
  return infiniteRecursion(n + 1); // no base case — every call pushes another frame, forever
}
 
infiniteRecursion(0);
// RangeError: Maximum call stack size exceeded

Module P-1 (Recursion and the Call Stack) goes deep on this — how the call stack grows and shrinks with correct, base-cased recursion, and how to reason about how many frames a given recursive function will actually push.

Balanced Parentheses

The single most common interview and real-world use of a stack: checking whether brackets in an expression are properly nested and closed.

function isBalanced(expression: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
 
  for (const char of expression) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char); // an opening bracket — remember it, we'll need to match it later
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.pop() !== pairs[char]) return false; // wrong bracket type, or nothing left to match
    }
  }
 
  return stack.length === 0; // every opening bracket must have been matched and popped
}
 
isBalanced('({[]})'); // true
isBalanced('({[}])'); // false — `}` arrives while `[` is on top of the stack, not `{`
isBalanced('(()');    // false — one unmatched opening bracket remains

The insight is that "most recently opened, must be closed first" is exactly the LIFO property a stack enforces automatically — you never need to explicitly track nesting depth or bracket types beyond "what's currently on top."

Expression Evaluation

Stacks are also the standard tool for evaluating expressions with operator precedence and parentheses — (1 + 2) * 3 needs to compute the parenthesized part first, and a stack naturally holds "pending" values and operators until they're ready to be resolved.

// Evaluates a simple postfix (Reverse Polish Notation) expression: "3 4 +" means 3 + 4
function evalPostfix(tokens: string[]): number {
  const stack: number[] = [];
 
  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      stack.push(Number(token));
    } else {
      const b = stack.pop()!;
      const a = stack.pop()!;
      const result = token === '+' ? a + b
                    : token === '-' ? a - b
                    : token === '*' ? a * b
                    : a / b;
      stack.push(result);
    }
  }
 
  return stack.pop()!;
}
 
evalPostfix(['3', '4', '+', '2', '*']); // (3 + 4) * 2 = 14

Postfix notation sidesteps parentheses and precedence rules entirely — operators always apply to the two most recent values, which is exactly what a stack gives you for free. This is also, not coincidentally, how many calculators and older interpreters actually evaluate expressions internally: parse the human-readable infix form (1 + 2) into postfix once, then evaluate the postfix form with a simple stack pass.

A Preview: The Monotonic Stack

One more pattern worth naming here, because it reappears later in this course: a monotonic stack keeps its elements in increasing (or decreasing) order at all times, popping elements that violate the ordering before pushing a new one.

// For each element, find the next element to its right that is strictly greater
function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // stores indices, kept in decreasing value order
 
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop()!;
      result[idx] = nums[i]; // nums[i] is the "next greater" element for this popped index
    }
    stack.push(i);
  }
 
  return result;
}
 
nextGreaterElement([2, 1, 3, 4]); // [3, 3, 4, -1]

Each element is pushed once and popped at most once, so despite the nested-looking while inside a for, this is O(n) overall, not O(n²) — every index does a constant amount of total work across the whole run. This exact shape — pop while the top violates an ordering, then push — is the backbone of several problems in Module A-1 (Heaps) and shows up again wherever "find the next X that's bigger/smaller" appears.

Where This Shows Up in Your Stack

Browser history: the back button is a stack — visiting a new page pushes it on top; going back pops the most recent one off, revealing the page beneath it.
Undo/redo in editors and design tools: each action pushed onto an "undo stack"; undoing pops it off and (often) pushes it onto a parallel "redo stack."
Every stack trace you've ever read is a direct printout of the call stack at the moment of a crash — most recent call at the top, exactly matching the LIFO order this module describes.
BullMQ and other job queues support a LIFO processing mode specifically for cases where the most recently queued job is the most relevant one to process next (e.g., "always show the freshest result," discarding stale in-flight work) — the opposite default of the FIFO queue covered in Module F-7.
JSON parsers and compilers use a stack internally to track nested structures (objects inside arrays inside objects) — the same bracket-matching logic as isBalanced, just applied to {, [, and their string/number contents instead of bare brackets.

Summary

A stack is push/pop/peek, all O(1), built as a thin, discipline-enforcing wrapper over the array from Module F-2.
LIFO — last in, first out. You can only access the most recently added item until it's removed.
The call stack is a real stack: every function call pushes a frame, every return pops one, and unbounded recursion without a base case exhausts it — a stack overflow.
Balanced-bracket checking is the canonical stack problem: push openers, pop-and-match on closers, and check the stack is empty at the end.
Postfix expression evaluation sidesteps parentheses and precedence entirely by always operating on the two most recent stack values.
A monotonic stack (push while maintaining order, popping violators first) solves "next greater/smaller element" problems in O(n), not O(n²) — a pattern that reappears in later modules.

The next module, Queues: FIFO, Circular Queues, and Job Scheduling, covers the structure that enforces the opposite ordering — first in, first out — and the reason job schedulers and message brokers are built on it instead of a stack.

Knowledge Check

Why does push()/pop() at the end of an array (as used inside the Stack class) stay O(1), the same reasoning established for arrays back in Module F-2?

In isBalanced, why does the function return false for the input "(()" even though every character in the string is a valid, correctly-typed bracket?

The module states that nextGreaterElement is O(n) overall, "despite the nested-looking while inside a for." What is the reasoning behind that claim?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule F-5: Bit Manipulation: Flags, Permissions, and Fast Math Next Module F-7: Queues: FIFO, Circular Queues, and Job Scheduling

Discussion

Join the discussion

Loading comments...