Skip to content

Stacks

Lesson 5 of 7 in Foundations · 30 min · Beginner

Last in, first out — a pile of plates.

Introduction

You type a word, delete a line, paste a block. Then you press Ctrl+Z, and the editor undoes the paste. Press it again and the delete is undone. How does it always know the last thing you did?

The editor could keep a long history and search it for the newest action every time. But that would get slower as you work, and undo feels instant even after an hour of typing.

Think about what undo actually needs: the most recent action, then the one before it, then the one before that. Never one from the middle. What would you keep your actions in so the newest is always right there?

Lesson overview

This lesson will show you how to:

  • Explain why a stack only lets you touch the newest item.
  • Trace push and pop as a last-in, first-out sequence.
  • Match brackets by pushing openers and popping on each closer.
  • Use a monotonic stack to find each item's next greater element.
  • Choose a queue instead when items must leave in arrival order.

The picture

492top6top: the only doorbottom: waits longestpush lands on topStack stack with 3 items, bottom to top: 4, 9, 2. Top is 2. Capacity 6. Pushing value 6. Marked: index 2 focus.

Mental model

Picture a pile of clean plates in a canteen. A new plate goes on top of the pile, and a plate is taken from the top too. To reach the plate at the bottom, every plate above it has to come off first.

A stack only lets you touch the newest item, so the last thing in is always the first thing out.

Words to know

push
Put a new item on top of the stack.
pop
Remove the top item and hand it back to you.
peek / top
Look at the top item without removing it. The stack stays exactly as it was.
LIFO
Last in, first out: the item pushed most recently is the first one popped.
underflow
Trying to pop or peek an empty stack. There is nothing to give back, so check for empty first.
call stack
The stack your program uses to remember where each function call should return to. Recursion is a stack at work.
monotonic stack
A stack kept in order (never rising, say) by popping every item that can no longer matter before pushing the next one.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The newest unfinished thing has to be dealt with first: the last bracket opened, the last action to undo.
  • Yes: You match things that nest: brackets, tags, quotes, or a path with ".." in it.
  • Yes: For every item you need the nearest bigger or smaller item to its left or right.
  • Yes: You keep the previous state and go back to it later: undo, back button, backtracking.

Not this when

  • No: Items must be served in the order they arrived (first in, first out): that is a queue.
  • No: You need the smallest or largest item at any moment, not the newest: that is a heap.
  • No: You need an item by position or by value, not just the top: an array or a hash map reaches it directly.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given a string of ( ) [ ] { } characters, decide whether every opening bracket is closed by the right kind, in the right order.

  2. Which pattern? 2 of 5

    Customers join a line at a ticket desk. Serve them in the order they arrived.

  3. Which pattern? 3 of 5

    For each day's temperature, find how many days you must wait until a warmer day.

  4. Which pattern? 4 of 5

    List every subset of the numbers [1, 2, 3].

  5. Which pattern? 5 of 5

    Return the first character in a string that appears only once.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1stack = empty
  2. for each character ch in s:
  3. if ch is an opener:
  4. 2push ch
  5. else (ch is a closer):
  6. 3if stack is empty or top is not ch's partner: return false
  7. 4pop the top (that pair is matched)
  8. 5return stack is empty

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack
Time · O(n)Space · O(n)
  • Each character is pushed at most once and popped at most once, so one pass takes O(n) time. In the worst case (all openers) the stack holds n items, so space is O(n).
  • Check for empty before you pop or peek. Popping an empty stack is an underflow: Python and Java throw an error, and in C++ it is undefined behaviour.
  • In Java, use ArrayDeque, not java.util.Stack. Stack is an old class built on Vector, which locks on every call, and the Java docs themselves recommend Deque instead. ArrayDeque's push, pop and peek work on the top like a stack should.
  • In C++, std::stack::pop() returns nothing. Read top() first if you need the value, as the Daily Temperatures code does.
  • A monotonic stack keeps its items in order by popping whatever can no longer matter. The while loop looks nested, but every item is pushed once and popped once, so the whole pass is still O(n).
  • Push indices instead of values when you need distances or positions: temps[index] gives the value back, and i - j gives the gap.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given a string s containing just the characters ( ) { } [ ], determine whether it is valid: every open bracket is closed by the same type, and in the correct order.

Input

s = "()[]{}"

Output

true

Approach

  1. Read left to right. An opener has not found its closer yet, so push it.
  2. A closer must match the opener on top of the stack, because that is the one opened most recently. If the stack is empty or the top is a different kind, return false.
  3. If it matches, pop the opener: that pair is done.
  4. At the end the stack must be empty. Any opener left on it was never closed.
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack
Time · O(n)Space · O(n)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. Start with an empty stack. Push 4, push 9, push 2, pop, push 7, pop. Which value is on top now?
  2. Why can't Valid Parentheses just count the openers and closers?
  3. What happens if you pop an empty stack?
  4. In Daily Temperatures, why does the stack hold indices rather than temperatures?
  5. The monotonic stack code has a while loop inside a for loop. Why is it still O(n) overall?

Question 1 of 5

Start with an empty stack. Push 4, push 9, push 2, pop, push 7, pop. Which value is on top now?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Implement Queue using Stacks (opens in a new tab) (LeetCode, easy)

    Hint: Pouring one stack into another reverses the order. What does reversing twice give you?

  2. Solve Remove All Adjacent Duplicates In String (opens in a new tab) (LeetCode, easy)

    Hint: The top of the stack is the last letter you kept. Compare each new letter with it before deciding.

  3. Solve Next Greater Element I (opens in a new tab) (LeetCode, easy)

    Hint: It is the same pop-when-bigger pass as Daily Temperatures, but you record the value instead of the gap, and look answers up by number.

  4. Solve Evaluate Reverse Polish Notation (opens in a new tab) (LeetCode, medium)

    Hint: Numbers wait on the stack, and an operator uses the two most recent ones. Mind the order for subtraction and division.

  5. Solve Removing Stars From a String (opens in a new tab) (LeetCode, medium)

    Hint: A star deletes the character kept just before it, and the stack top is exactly that character.

  6. Solve Simplify Path (opens in a new tab) (LeetCode, medium)

    Hint: Split the path on slashes: a folder name goes on the stack, and a double dot undoes the most recent one.

  7. Solve Car Fleet (opens in a new tab) (LeetCode, medium)

    Hint: Sort cars by position, then compare arrival times starting from the car nearest the target. A slower car ahead holds up whoever catches it.

  8. Solve Largest Rectangle in Histogram (opens in a new tab) (LeetCode, hard)

    Hint: Keep bars on a stack in rising height. When a shorter bar arrives, each taller bar it pops has just found its right edge.

Additional resources