Stacks: Last In, First Out

A stack is a pile of plates: you put new plates on top and you take plates off the top. The last thing in is the first thing out (LIFO).

  push 3 ->  | 3 |  <- top (pop / peek here)
             | 2 |
             | 1 |
             +---+

In Python you don't need a special class: a plain list is a great stack, as long as you only work at the end:

• push: stack.append(x) - O(1)
• pop: stack.pop() - O(1)
• peek: stack[-1] - O(1)
• empty?: if not stack: - O(1)

When is a stack the right tool? Whenever the most recent unfinished thing must be dealt with first. That is exactly what nesting looks like:

{ [ ( ) ] }
    └─┘        ( closes first: it opened last
  └─────┘
└─────────┘

Every closing bracket must match the most recent opener that is still open. Push openers; on a closer, pop and compare. At the end the stack must be empty (otherwise something was never closed).

Brute force would repeatedly delete "()" pairs from the string until nothing changes: O(n²). The stack does it in one pass: O(n) time, O(n) space.

Recognising stack problems in an interview. Look for words like valid / balanced / nested, undo / backspace, most recent, simplify a path, evaluate an expression, or any time you process items left to right and a new item can "cancel" or "resolve" the previous ones.