Stacks

A LIFO (Last-In, First-Out) data structure. The last element added is the first one to be removed.

What is it?

A stack operates on a "Last-In, First-Out" (LIFO) principle. The classic example is the Undo functionality in any text editor like VS Code or Google Docs. Every time you perform an action (like typing a word or deleting a line), that action is "pushed" onto a stack. When you press Ctrl+Z, the most recent action is "popped" off the stack, and the editor reverses it. If you press Ctrl+Z again, the next most recent action is popped and reversed. This structure is perfect for managing history that needs to be unwound in reverse chronological order. The core operations, push and pop, are extremely fast (O(1)).

Time Complexity

AccessO(n)

SearchO(n)

InsertionO(1)

DeletionO(1)

Implementation Example

const stack = [];

// Push (add an element)
stack.push(10);
stack.push(20);

// Pop (remove the top element)
const topElement = stack.pop(); // 20
console.log(topElement);

// Peek (view the top element)
const peekElement = stack[stack.length - 1]; // 10
console.log(peekElement);

Stacks

Stacks Deep Dive

Stacks model the natural flow of nested work—from function frames to browser history—because LIFO order mirrors the way humans unwind tasks.

?But why does this matter?

Most runtimes expose both implicit stacks (call stack) and explicit stacks you manage yourself for control.

Visual Flow

How it actually moves

Push

O(1)

Append to the end of the underlying buffer or update top pointer.

Pop

O(1)

Removes the last element and decreases size.

Peek

O(1)

Reads the last element without mutation.

Balanced parentheses check

Create an empty stack.

Scan the string: push opening brackets, pop when a matching closing bracket appears.

If a closing bracket doesn’t match the stack’s top or the stack is empty, the string is invalid.

After the scan, the stack must be empty for the string to be balanced.

Watch the best explainer

Data structures: Introduction to Stack

mycodeschool

Clear LIFO fundamentals with array and linked-list implementations.

Stack plates in a cafeteria

Guests take the top plate and new clean plates are placed on top. Reaching the bottom plate would require removing everything above it.

Real-world analogy

Code editors implement ctrl+Z by pushing actions on a stack and popping them when the user undoes.

Takeaway

Stacks capture “last thing done is first undone,” which is why nesting and backtracking problems map cleanly to them.

Practical applications

• Browser history and IDE navigation (jump back/forward).
• Parsing expressions, evaluating ASTs, and powering compilers.
• Backtracking problems such as DFS, maze solving, or undo flows.

Technical insights

• Array-backed stacks outperform linked implementations because pushes/pops are contiguous.
• Bounded stacks guard against runaway recursion by limiting depth explicitly.
• Lock-free stacks use atomic CAS, but ABA problems require tagged pointers.

When to reach for it

• Expression evaluation
• Depth-first traversal
• Command pattern implementations

Operations Breakdown

Push

O(1)

Append to the end of the underlying buffer or update top pointer.

Pop

O(1)

Removes the last element and decreases size.

Peek

O(1)

Reads the last element without mutation.

Best practices

• Prefer iterative solutions with explicit stacks when recursion depth is user-controlled.
• Expose stack snapshots for debugging complex interpreter flows.
• Use typed stacks (generics) to prevent mixing sentinel values or nulls.

Common pitfalls

• Unbounded stacks can grow without limit and exhaust memory.
• Leaking references by failing to clear popped slots prevents GC.
• Lock-free stacks need ABA mitigation to stay correct under contention.

Every kind of Stacks

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 4

Plain LIFO Stack

→ full page

Push and pop from one end. Anything with "most recent first" semantics — undo, nesting, backtracking — is a stack.

What to know

Matching brackets: push openers, pop and compare on closers.
Iterative DFS replaces the call stack with an explicit one.
Backed by a dynamic array (fast) or linked list (no resize).

Algorithms to reach for

Valid parentheses matching

O(n)

Check nesting of brackets/tags (LeetCode 20)

Iterative DFS

O(V + E)

Depth-first traversal without recursion limits

Undo/redo pair of stacks

O(1) per op

Editor history navigation

In the wild: Call stacks, browser history, undo systems, JSON/XML parsers.

Practice problems — hints, approach & solution on their own pages

Valid ParenthesesEasy Simplify PathMedium Decode StringMedium

Type 2 of 4

Monotonic Stack

→ full page

A stack kept strictly increasing or decreasing — pushed elements evict everything they dominate. Turns brute-force O(n²) "nearest greater/smaller" scans into O(n).

What to know

Each element is pushed and popped at most once — that is the amortized O(n) proof.
Decreasing stack answers "next greater element"; increasing stack answers "next smaller".
Largest Rectangle in Histogram is the boss fight: widths come from pop-time index gaps.

Algorithms to reach for

Next greater element

O(n)

For each item, first larger item to the right

Daily temperatures

O(n)

Days until a warmer day (indices on the stack)

Largest rectangle in histogram

O(n)

Max rectangular area under bars (LeetCode 84)

Trapping rain water (stack variant)

O(n)

Water volume between bars

In the wild: Stock span indicators, skyline problems, compiler expression bounds analysis.

Practice problems — hints, approach & solution on their own pages

Daily TemperaturesMedium Next Greater Element IEasy Largest Rectangle in HistogramHard Trapping Rain WaterHard

Type 3 of 4

Min / Max Stack

→ full page

A stack that also answers "what is the current minimum?" in O(1) by carrying the running extreme alongside every entry.

What to know

Store (value, minSoFar) pairs, or keep a second stack of minimums.
Pop keeps both stacks in sync automatically.
Same trick generalizes to max, and to queues via two stacks.

Algorithms to reach for

MinStack ops

O(1)

push/pop/top/getMin all O(1) (LeetCode 155)

Queue from two stacks

O(1) amortized

Amortized O(1) FIFO using LIFO parts

In the wild: Sliding-window financial stats, constraint tracking in games, interpreter scopes.

Practice problems — hints, approach & solution on their own pages

Min StackMedium Implement Queue using StacksEasy

Type 4 of 4

Expression / Call Stack

→ full page

The stack as an evaluator: operators and operands are pushed, precedence decides when to reduce. Every interpreter and calculator works this way.

What to know

Shunting-yard converts infix to postfix (RPN) using an operator stack.
Postfix evaluation needs only one operand stack — no precedence left.
Recursion depth limits are simply call-stack capacity limits.

Algorithms to reach for

Shunting-yard

O(n)

Infix → postfix respecting precedence/parentheses

RPN evaluation

O(n)

Evaluate postfix expressions (LeetCode 150)

Basic calculator

O(n)

Evaluate strings with +−×÷ and parens (LeetCode 224)

In the wild: Compilers, calculators, SQL/JSON expression engines, the JVM operand stack.

Practice problems — hints, approach & solution on their own pages

Evaluate Reverse Polish NotationMedium Basic Calculator IIMedium Basic CalculatorHard

Pseudo Code • Balanced parentheses check

Flow Diagram

Create an empty stack.
Scan the string: push opening brackets, pop when a matching closing bracket appears.
If a closing bracket doesn’t match the stack’s top or the stack is empty, the string is invalid.
After the scan, the stack must be empty for the string to be balanced.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function isBalanced(expression) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];

  for (const ch of expression) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (pairs[ch]) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}