Data structure 6 of 12

Stacks

A stack only lets you touch the top: add to the top, look at the top, take from the top. The last thing in is the first thing out, which is exactly what you need for undo, nesting and recursion.

A 2-minute conversation: Sam asks, Priya explains

0:00 / 2:16

Follow along on the page Pause on “your turn” questions

Sam Stacks. Push and pop?
Priya And peek. A stack only lets you touch the top. The last thing in is the first thing out, which is exactly what undo, nesting and recursion need.
Priya A pile of trays in a canteen. You put a clean one on top and take the top one. Nobody pulls a tray from the middle.
Sam When do I reach for one?
Priya Whenever the most recent unfinished thing is the one to deal with next: the last bracket opened, the last action to undo, the function that called this one.
Sam Do I need a special class?
Priya No. The end of a list is a perfect top, because adding and removing at the end are constant. And your program already uses a stack: every function call pushes a frame onto the call stack, and returning pops it.
Sam Costs?
Priya Push, pop, peek and "is it empty?" are all constant. Searching inside isn't what a stack is for.
Priya Your turn. Push one, push two, push three, then pop. What comes out?
Priya Three. Last in, first out.
Sam Language differences?
Priya In Python and TypeScript, a plain list or array. In Java, use ArrayDeque; the old Stack class is slow. And always check the stack isn't empty before you pop or peek.
Sam The three players?
Priya Push everything then pop everything, which reverses a list. Undo, by typing with backspace: each letter is pushed and each backspace pops. And the call stack of a recursive function, sum to three, where frames pile up and then finish in reverse order.
Sam What happens without a base case?
Priya Frames pile up until the stack runs out of room. In Python, that's a RecursionError at about a thousand frames.
Sam Memory hook?
Priya The tray pile. Push, peek, pop, and check it's not empty first.
Sam Problems?
Priya Remove all adjacent duplicates: each letter either cancels the top or goes on the pile. And removing stars from a string, where each star is a backspace.
Sam Mistakes?
Priya Popping an empty stack. Using the front of a list as the top. Java's Stack class. Forgetting to check what's left at the end. And very deep recursion.
Sam Next?
Priya Lesson seven, queues and deques: first in, first out.

1. What it is

A pile of trays in a canteen. You put a clean tray on top and you take the top one; nobody pulls a tray from the middle. The tray you added last is the first one used.

A stack is a collection with one open end, the top. This rule is called LIFO: last in, first out. Three operations, all O(1):

push(x): put x on top.
pop(): remove and return the top.
peek(): look at the top without removing it.

Whenever the most recent unfinished thing is the one to deal with next (the last opened bracket, the last action to undo, the function that called this one), a stack is the tool.

2. How it sits in memory

You don't need a special class: the end of an array is a perfect top, because adding and removing at the end are O(1).

Your program already uses a stack you never see. Each function call pushes a frame (its arguments and local variables) onto the call stack; returning pops it. Recursion is just many frames of the same function piled up.

3. Operations and what they cost

Operation	Python (a list)	Cost
Push	`stack.append(x)`	`O(1)` amortised
Pop	`stack.pop()`	`O(1)`
Peek	`stack[-1]`	`O(1)`
Is it empty?	`not stack`	`O(1)`
Search inside	`x in stack`	`O(n)`: not what a stack is for

Always check before poppingPopping or peeking an empty stack is an error. Write if stack: first; many interview bugs are exactly this.

4. In Python, TypeScript and Java

The top of the stack is the end of a list or array. In Java, use ArrayDeque; the old Stack class is slower and discouraged.

stack = []
    stack.append(1)      # push → [1]
    stack.append(2)      # push → [1, 2]
    top = stack[-1]      # peek → 2
    x = stack.pop()      # pop  → 2, stack is [1]
    if stack:            # check before popping
        stack.pop()

const stack: number[] = [];
    stack.push(1);                    // [1]
    stack.push(2);                    // [1, 2]
    const top = stack[stack.length - 1];   // 2
    const x = stack.pop();            // 2
    if (stack.length) stack.pop();

Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1);                    // top is 1
    stack.push(2);                    // top is 2
    int top = stack.peek();           // 2
    int x = stack.pop();              // 2
    if (!stack.isEmpty()) stack.pop();

5. Core operations, step by step

Three ways stacks appear: reversing, undoing, and the hidden stack behind recursion.

A · Push everything, pop everything (reverse)

What it doesPushes items in order, then pops them: they come out reversed.

Picture itStack trays labelled 1, 2, 3; take them off and they come back 3, 2, 1.

CostO(n) time and space.

The code. The simplest proof of last in, first out.

def reverse(items):
    stack = []
    for x in items:
        stack.append(x)
    out = []
    while stack:
        out.append(stack.pop())
    return out

function reverse(items: number[]): number[] {
  const stack: number[] = [];
  for (const x of items) {
    stack.push(x);
  }
  const out: number[] = [];
  while (stack.length) {
    out.push(stack.pop()!);
  }
  return out;
}

static List<Integer> reverse(int[] items) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int x : items) {
        stack.push(x);
    }
    List<Integer> out = new ArrayList<>();
    while (!stack.isEmpty()) {
        out.add(stack.pop());
    }
    return out;
}

Line by line.

Line	What it does	Why
`stack.append(x)`	Push onto the top.	The end of the list is the top.
`while stack:`	Until the stack is empty.	An empty list is false in Python.
`stack.pop()`	Take the top.	The most recently pushed item comes out first.

Watch it run. [1, 2, 3, 4].

Watch out for:

stack.pop(0). That takes from the bottom (and costs O(n)). The top is the end.

B · Undo: typing with backspace

What it doesEach letter is pushed; each # (backspace) pops the most recent letter.

Picture itWriting on a pile of sticky notes: backspace throws away the newest note.

CostO(n) time and space.

The code. Undo always means "take back the most recent thing": pop.

def typed(s):
    stack = []
    for c in s:
        if c == "#":
            if stack:
                stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

function typed(s: string): string {
  const stack: string[] = [];
  for (const c of s) {
    if (c === "#") {
      if (stack.length) {
        stack.pop();
      }
    } else {
      stack.push(c);
    }
  }
  return stack.join("");
}

static String typed(String s) {
    StringBuilder stack = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '#') {
            if (stack.length() > 0) {
                stack.deleteCharAt(stack.length() - 1);
            }
        } else {
            stack.append(c);
        }
    }
    return stack.toString();
}

Line by line.

Line	What it does	Why
`if c == "#"`	A backspace?
`if stack: stack.pop()`	Undo the most recent letter, if there is one.	Backspace on an empty line does nothing; popping an empty stack would crash.
`stack.append(c)`	A normal letter: push it.

Watch it run. Type "ab#c##d".

Watch out for:

Popping without checking. Two backspaces at the start would crash.

C · The call stack (recursion)

What it doesEach recursive call pushes a frame; each return pops one and hands its answer back.

Picture itA pile of sticky notes, one per unfinished question. You can only answer the top note; then you throw it away and carry its answer down.

CostO(n) frames for depth n: recursion uses memory, not just time.

The code. sum_to(n) is n plus sum_to(n − 1), until the base case.

def sum_to(n):
    if n == 0:
        return 0
    rest = sum_to(n - 1)
    return n + rest

function sumTo(n: number): number {
  if (n === 0) {
    return 0;
  }
  const rest = sumTo(n - 1);
  return n + rest;
}

static int sumTo(int n) {
    if (n == 0) {
        return 0;
    }
    int rest = sumTo(n - 1);
    return n + rest;
}

Line by line.

Line	What it does	Why
`if n == 0: return 0`	The base case: stop recursing.	Without it the stack grows until the program crashes (stack overflow).
`rest = sum_to(n - 1)`	Push a new frame and wait for it.	This frame stays on the stack, paused, until the call returns.
`return n + rest`	Finish this frame with the answer from below.	Frames finish in reverse order: last called, first done.

Watch it run. sum_to(3).

Watch out for:

No base case, or one that is never reached. Infinite recursion: Python stops at about 1,000 frames with RecursionError.
Very deep recursion. Even a correct recursion 100,000 deep overflows. Rewrite it with your own stack.

6. How to remember it

Memory hook: "The tray pile"You can only add to the top, look at the top, or take the top. The last tray in is the first tray out.

Picture

A spring-loaded tray dispenser in a canteen.

Chant

"Push, peek, pop. Check it's not empty first."

Key rule

Need the most recent unfinished thing? Stack. Need the oldest? Queue (next page).

7. Problems solved with it

Two easy problems where each new item may cancel the one on top.

LC 1047 · Remove All Adjacent Duplicates In String

The problemRepeatedly remove two adjacent equal letters until none are left. Return the final string.

What it doesPushes each letter; if it equals the top, they cancel and the top is popped instead.

CostO(n).

The code. The top of the stack is the letter just to the left of the current one.

def remove_duplicates(s):
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

function removeDuplicates(s: string): string {
  const stack: string[] = [];
  for (const c of s) {
    if (stack.length && stack[stack.length - 1] === c) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.join("");
}

static String removeDuplicates(String s) {
    StringBuilder stack = new StringBuilder();
    for (char c : s.toCharArray()) {
        int n = stack.length();
        if (n > 0 && stack.charAt(n - 1) == c) {
            stack.deleteCharAt(n - 1);
        } else {
            stack.append(c);
        }
    }
    return stack.toString();
}

Line by line.

Line	What it does	Why
`if stack and stack[-1] == c`	Same as the letter on top?	Check the stack isn't empty before peeking.
`stack.pop()`	They cancel.	Popping can expose a new top that matches the next letter ("abba").

Watch it run. "abbaca".

Watch out for:

Removing pairs with string replace in a loop. Each pass is O(n) and you may need n passes: O(n²).

LC 2390 · Removing Stars From a String

The problemEach * removes itself and the closest non-star letter to its left. Return the result.

What it doesOperation B with * as backspace.

CostO(n).

The code. The input guarantees there's always a letter to remove, but checking costs nothing.

def remove_stars(s):
    stack = []
    for c in s:
        if c == "*":
            if stack:
                stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

function removeStars(s: string): string {
  const stack: string[] = [];
  for (const c of s) {
    if (c === "*") {
      if (stack.length) stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.join("");
}

static String removeStars(String s) {
    StringBuilder stack = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '*') {
            if (stack.length() > 0) stack.deleteCharAt(stack.length() - 1);
        } else {
            stack.append(c);
        }
    }
    return stack.toString();
}

Line by line.

Line	What it does	Why
`if c == "*": stack.pop()`	A star removes the nearest letter on the left.	The nearest letter on the left is the top of the stack.

Watch it run. "leet**cod*e".

Watch out for:

Deleting from a string directly. Strings are immutable; each deletion copies. The stack is O(n) in total.

More practice, solved on the pattern pages

#	Problem	Level	Where
20	Valid Parentheses	Easy	Solved step by step on 17 · Stack
682	Baseball Game	Easy	Solved step by step on 17 · Stack
155	Min Stack	Medium	Solved step by step on 17 · Stack
150	Evaluate Reverse Polish Notation	Medium	Solved step by step on 17 · Stack
739	Daily Temperatures	Medium	Solved step by step on 06 · Monotonic Stack

8. Common mistakes

Popping an empty stack[].pop() raises IndexError; stack[-1] on an empty list too. Check if stack: first.

Using the front as the topinsert(0, x) and pop(0) are O(n). The top is the end of the list.

Java's Stack classIt is synchronised and slow. Use ArrayDeque with push, pop and peek.

Forgetting what's left at the endMany problems need a final check: leftover items on the stack can mean the answer is false (unclosed brackets).

Deep recursionThe call stack is a real stack with a limit. For very deep inputs, write the loop with your own stack.

9. Self-check quiz

Push 1, push 2, push 3, then pop. What comes out?

Last in, first out.

Where is the top of a stack built on a Python list?

append and pop at the end are O(1); at the front they are O(n).

A recursive function has no base case. What happens?

Every call pushes a frame; the stack runs out of room (RecursionError in Python).

An editor's undo button should undo the most recent action first. Stack or queue?

Most recent first is LIFO.

10. Where it shows up next

17 · Stack: brackets, postfix expressions and the min stack.
06 · Monotonic Stack: a stack kept in order to find the next greater or smaller element.
10 · Binary Tree Traversal and 11 · DFS: recursion, or an explicit stack, to go deep first.
14 · Backtracking: the call stack remembers each choice so you can undo it.

Next structure: 07 · Queues and deques, first in, first out.