📚 Stacks

init

Try it: Push tokens onto the tower; pop them off. Then below: feed any bracketed string into the parens game — the stack is the parser.

Why it matters

Stacks are everywhere: function calls, undo/redo, expression parsing, backtracking algorithms. Understanding stacks means understanding how programs execute and how to solve problems that require 'remembering' and 'undoing'.

The idea

Think of a stack of plates in a cafeteria. You can only add or remove from the top. The last plate placed is the first one taken.

Last In, First Out (LIFO).

This simple constraint is incredibly powerful:

• Function calls: When function A calls B, B's context goes on top. When B returns, it's popped off, and A continues.
• Undo: Each action pushes onto the stack. Undo pops the last action.
• Matching parentheses: Push '(', pop when you see ')'. If balanced, stack is empty at the end.

All operations are O(1) - you only ever touch the top.

Key takeaways

• Push, pop, and peek are all O(1)
• LIFO order - last in, first out
• Used in function call stacks, expression evaluation, backtracking
• Can be implemented with array or linked list

Going deeper

The call stack is why recursive functions work — each call's local variables are pushed onto the stack and popped when returning. Stack overflow happens when recursion goes too deep. Stacks are also key to converting infix to postfix notation (shunting-yard algorithm) and evaluating postfix expressions in a single pass.

In the wild

• CPU call stack. Every function call your program makes pushes a stack frame (return address + locals + saved registers). The hardware stack pointer is one register on every modern CPU. When you crash with a stack trace, you're reading the stack from top to bottom.
• Browser undo/redo. Two stacks: one for past actions, one for redo. Every editor (Photoshop, VS Code, Figma) is built on this pattern.
• DFS via explicit stack. Recursion is implicit stack use; on deep graphs you keep an explicit stack array to avoid blowing the call stack. See the graphs lesson — its DFS frontier is a stack.
• Recovery state in robotics. Pushing the previous "safe" state before a risky action, popping back to it on failure — the foundation of try/except-style recovery in motion planners.
• Compilers. Every parser uses a stack: shift/reduce parsing, expression parsing, scope tracking. Your code becomes an AST via stack-driven recognition of nested structure.

Math details

Time Complexity

Push: O(1)

Pop: O(1)

Peek: O(1)

Search: O(n)

Space

O(n) for n elements

Implementation

Stack Operations

let mut stack = Vec::new();

stack.push(1);  // Push onto top
stack.push(2);
stack.push(3);  // Stack: [1, 2, 3] (3 is top)

let top = stack.pop();  // Returns Some(3)
let peek = stack.last(); // Returns Some(&2)

Classic Applications

• Balanced parentheses checking
• Function call stack
• Undo/redo functionality
• Expression evaluation
• DFS traversal

Practice

Three classic stack problems — each one is a different way of using the LIFO discipline:

• Min Stack — easy · parallel auxiliary stack tracks the running minimum so getMin is O(1)
• Next Greater Element — medium · monotonic stack of "waiting" indices, amortized O(n)
• Evaluate Postfix Expression — medium · stack as a computer; how every RPN calculator and JVM bytecode VM evaluates expressions

→ Browse all practice problems