Stack

A stack is a last-in, first-out (LIFO) collection: you push onto the top and pop from the top, like a pile of plates.

An empty stack

top

empty

A stack is last in, first out (LIFO): you can only add or take from the top — like a pile of plates.

Step 1 / 12
Size
0
  1. push(3)
  2. push(7)
  3. push(1)
  4. peek()
  5. pop()
  6. push(9)
  7. pop()
  8. pop()

What's happening?

  1. push puts a value on top; pop removes and returns the top value; peek looks at it without removing it.
  2. Only the top is ever touched, so every operation is O(1).
  3. In the bracket checker, each opener waits on the stack and each closer must match the most recent opener — the top.

Complexity

Time
O(1) push, pop and peek
Space
O(n)

Where you'll meet it

Undo in editors, the browser Back button, the call stack that runs every function, expression parsing, and checking brackets in code and JSON.

Common mistake

Popping without checking that the stack is empty — an underflow error, or a crash.

FAQ

Stack vs queue?

A stack takes from the end it added to (LIFO); a queue takes from the other end (FIFO).

How do you check balanced brackets?

Push every opener; on each closer, the top must be its matching opener — pop it. At the end the stack must be empty.

What is a stack overflow?

When the call stack — the stack of running function calls — runs out of room, usually from recursion with no base case.