Module F-6 — Stacks: LIFO, the Call Stack, and Expression Parsing
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.
typescript
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.
typescript
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.
typescript
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.
typescript
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.
typescript
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.
typescript
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 (Module F-1's error-reading section) 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 access a wider variety of questions and get notified when new practice sets are added to this module.
classStack<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{returnthis.items.pop();// O(1) — removing from the end never shifts anything}peek():T|undefined{returnthis.items[this.items.length -1];// O(1) — direct index access}isEmpty():boolean{returnthis.items.length ===0;}}
functioninfiniteRecursion(n:number):number{returninfiniteRecursion(n +1);// no base case — every call pushes another frame, forever}infiniteRecursion(0);// RangeError: Maximum call stack size exceeded
functionisBalanced(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}elseif(char ===')'|| char ===']'|| char ==='}'){if(stack.pop()!== pairs[char])returnfalse;// wrong bracket type, or nothing left to match}}return stack.length ===0;// every opening bracket must have been matched and popped}isBalanced('({[]})');// trueisBalanced('({[}])');// false — the `]` never closes the `[` it's nested insideisBalanced('(()');// false — one unmatched opening bracket remains
// Evaluates a simple postfix (Reverse Polish Notation) expression: "3 4 +" means 3 + 4functionevalPostfix(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
// For each element, find the next element to its right that is strictly greaterfunctionnextGreaterElement(nums:number[]):number[]{const result =newArray(nums.length).fill(-1);const stack:number[]=[];// stores indices, kept in decreasing value orderfor(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]