↩ back to Linear

Stack

A stack holds a sequence of items with one rule: you can only add to, or remove from, one end — the top. That makes it last in, first out (LIFO): whatever you pushed most recently is the first thing that comes back out. It's the same shape as a stack of plates, a pile of browser tabs you keep undoing, or the trail of function calls your program is currently inside of.

Try it

Push values on, pop them off, or peek at the top without removing it. The highlighted block is always the top — the only element a stack lets you touch directly.

Core operations

A stack has a small, deliberate interface — that restriction is the whole point, not a limitation:

• push(x) — add x to the top.
• pop() — remove and return the top item.
• peek() (or top()) — return the top item without removing it.
• isEmpty() — whether there's anything to pop or peek.

Notice what's missing: there's no get(i), no way to reach into the middle. If you find yourself needing that, you don't have a stack anymore — you have a list that's pretending to be one.

Reference implementation

class Stack {
  #items = [];

  push(x) {
    this.#items.push(x);
  }

  pop() {
    if (this.isEmpty()) throw new Error('pop on empty stack (underflow)');
    return this.#items.pop();
  }

  peek() {
    if (this.isEmpty()) throw new Error('peek on empty stack');
    return this.#items[this.#items.length - 1];
  }

  isEmpty() {
    return this.#items.length === 0;
  }
}

This wraps a JavaScript array, whose own push/pop already operate on the end of the array in O(1) amortized time — so the wrapper's only real job is refusing to pop or peek an empty stack instead of returning undefined silently. A linked list with a head pointer works just as well and avoids the array's occasional resize, at the cost of one extra pointer per element.

Pitfalls

Underflow. Popping or peeking an empty stack is the classic bug. Some languages throw, some return a sentinel like null or -1, and some — like a raw JavaScript array's .pop() on an empty array — quietly hand back undefined with no error at all. Always check isEmpty() first, or know exactly what your stack does when it's empty. The demo above logs the underflow instead of throwing, on purpose, so you can see what it looks like.

Overflow. A stack backed by a fixed-size array, or a call stack backed by a fixed region of memory, can run out of room. Uncontrolled recursion hitting a "stack overflow" is exactly this: every call pushes a new frame, and if the recursion never bottoms out, the frames eventually exceed whatever memory was reserved for the call stack.

Confusing it with a queue. LIFO and FIFO look similar in code — both are "add at one end, remove near one end" — but push/pop (stack) and enqueue/dequeue (queue) give opposite orderings. Using an array's push() + shift() pair, for instance, gives you queue behavior even though push sounds like a stack operation. Check which end you're removing from, not just the method name.

Where stacks show up

• The call stack. Every function call pushes a frame (its local variables, return address); returning pops it. Recursion is stack usage made visible.
• Undo/redo. Each action pushes onto an undo stack; undoing pops it (and often pushes onto a redo stack).
• Matching brackets. Push an opening bracket, pop and compare on a closing one; the input is balanced only if the stack ends empty. This is the standard way to validate (){}[] nesting or parse expressions.
• Depth-first search. DFS is a graph/tree traversal built on a stack (explicit, or implicit via recursion using the call stack) — visit a node, push its unvisited neighbors, repeat. Swap the stack for a queue and the same skeleton becomes breadth-first search instead.
• Monotonic Stack. The same push/pop primitive with one added rule — pop anything that breaks a chosen order before every push — turns an O(n²) all-pairs check into an O(n) scan for "what's the next larger value to the right," for every position at once.

Complexity

Time: push, pop, and peek are all O(1) (amortized, for the array-backed version — occasional resizes average out). Searching for an arbitrary element is O(n), since the only sanctioned access point is the top. Space: O(n) for n stored items. The tradeoff for that single-ended discipline is real speed and simplicity — a stack is one of the cheapest structures there is, precisely because it refuses to do more than push and pop.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.