Skip to content

level 4 · Linear structures

Stack

Last in, first out. The undo button of data structures.

7 min 50 XP

what is it

Start here

A stack has exactly one rule: you can only touch the top. You add to the top (push), and you take from the top (pop). The item at the bottom is trapped until everything above it has gone.

That sounds restrictive, and it is — deliberately. The restriction is what makes it useful. Because you can only ever touch one end, both operations are instant, no matter how tall the pile grows.

You use stacks constantly without noticing. Ctrl+Z is a stack of your actions. The back button is a stack of pages. And when your code calls a function, the computer pushes that call onto a stack — which is exactly why an infinite recursion gives you a 'stack overflow'.

real-life analogy

Picture it

A stack of plates

Plates come out of the dishwasher and go on the pile. When you need one, you take the top plate — the one that went on most recently. Getting to the bottom plate means moving every plate above it first. Nobody pulls from the middle of a stack of plates.

interactive visualization

Watch it run

These get pushed one by one. Then we peek, and pop twice.

stack is empty

    bottom
    ←top

    A stack is a pile of plates. You add to the top, and you take from the top. The bottom plate is trapped until everything above it is gone.

    step 01/11

    • comparing
    • moving
    • found it
    1class Stack {
    2 constructor() { this.items = []; }
    3 push(value) {
    4 this.items.push(value);
    5 }
    6 pop() {
    7 if (this.isEmpty()) return null;
    8 return this.items.pop();
    9 }
    10 peek() {
    11 return this.items[this.items.length - 1];
    12 }
    13 isEmpty() {
    14 return this.items.length === 0;
    15 }
    16}

    variables right now

    size
    0
    comparisons 0moves 0

    the dry run · every step, in words

    11 steps

    complexity

    What it costs

    best case
    O(1) push
    average
    O(1) pop
    worst case
    O(1) peek
    extra memory
    O(n)

    Push, pop and peek all take the same time whether the stack holds 3 items or 3 million. Nothing has to shuffle, because nothing below the top ever moves.

    • O(1) · this one
    • O(log n)
    • O(n)
    • O(n log n)
    • O(n²)
    input size →work →

    common mistakes

    Common traps

    • Popping without checking whether the stack is empty.

      Popping an empty stack is a classic crash. Always ask isEmpty() first, or make pop return null.

    • Confusing peek with pop.

      peek looks at the top and leaves it there. pop takes it away. Using pop when you meant peek quietly destroys your data.

    • Trying to reach an item in the middle.

      You can't — not without popping everything above it. If you need that, a stack is the wrong structure and you probably want an array.

    quiz

    Check yourself

    Three questions. Get them all right to finish the lesson.

    +50 XP

    01You push 1, 2, 3, then pop once. What comes out?

    02Why is 'stack overflow' called that?

    03How long does it take to push onto a stack holding a million items?

    practice

    Solve it on LeetCode

    You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.