Stacks

You are editing a document. You type a word, make a line bold, then delete a paragraph. Now you press undo three times. The paragraph comes back first, then the bold goes away, then the word disappears. Undo always reverses the most recent change that has not been undone yet.

The editor does not search its history to work out what to undo. It keeps the changes in a pile, puts each new change on top, and takes from the top when you press undo. That pile is a stack.

#The idea: one open end

A stack is a collection where you can only touch one end, called the top. Think of a stack of plates: you put a plate on top and you take the top plate off. The plate you added last is the first one out, so a stack is called last in, first out (LIFO).

A stack has three operations, and each one is O(1):

• push: put an item on top.
• pop: remove the top item and return it.
• peek: look at the top item without removing it.

You rarely need a special class. The end of an array is already a perfect top, because adding and removing at the end never shifts anything. In JavaScript, use push, pop and stack[stack.length - 1] to peek. In Python, use append, pop and stack[-1]. Push is amortized O(1), as in Arrays: once in a while the array grows and copies itself, but the average stays constant. The head of a linked list works too: push means "insert at the head", pop means "remove the head".

#When to reach for a stack

Use a stack when the newest unfinished thing must be finished before anything older. That is exactly the shape of anything nested: brackets inside brackets, folders inside folders, function calls inside function calls.

A code editor wants to warn you about broken brackets. The text {x: [1, (2)]} is fine. The text ([)] is not: the [ opened after the (, so it must close first.

The rule falls straight out of a stack. Read the text left to right. Push every opening bracket. When you meet a closing bracket, the most recent unclosed opener must be its partner, and the most recent opener is the top of the stack. Pop it and compare.

for each character ch:  if ch is an opener: push ch  else if ch is a closer:    if stack is empty: return false    if pop() is not ch's partner: return falsereturn stack is empty

The code has three ways to fail, one for each kind of broken text. A closer with an empty stack means it closes nothing, as in ()). A closer that does not match the top is closing in the wrong order, as in ([)]. And openers still on the stack at the end were never closed, as in ((.

const PAIRS = { ")": "(", "]": "[", "}": "{" };
 
function isBalanced(text) {
  const stack = [];
  for (const ch of text) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch); // an opener waits for its closer
    } else if (ch in PAIRS) {
      if (stack.length === 0) return false;        // closes nothing
      if (stack.pop() !== PAIRS[ch]) return false; // wrong kind
    }
  }
  return stack.length === 0; // anything left was never closed
}
 
isBalanced("{x: [1, (2)]}"); // true
isBalanced("([)]");          // false

PAIRS = {")": "(", "]": "[", "}": "{"}
 
def is_balanced(text):
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)  # an opener waits for its closer
        elif ch in PAIRS:
            if not stack:
                return False  # closes nothing
            if stack.pop() != PAIRS[ch]:
                return False  # wrong kind
    return not stack  # anything left was never closed
 
is_balanced("{x: [1, (2)]}")  # True
is_balanced("([)]")           # False

#Stacks you already use

You already use stacks in these places:

• The call stack. Every function call is pushed, and returning pops it. Recursion traced exactly this. When recursion goes too deep, you get a "stack overflow".
• Undo and the back button. The newest action or page is the first one you return to.
• Depth-first search. To explore a maze or a graph as deep as possible before backing up, keep the places still to explore on a stack. See Depth-First Search.
• Turning recursion into a loop. If recursion would be too deep, push the work you would have recursed on onto your own stack and loop until it is empty.

#Common mistakes

#Check yourself

#What to practise next

Practise the bracket check on Nesting Gift Boxes, then use a stack as a calculator on Vintage Calculator Tape. A stack serves the newest item first. To serve the oldest first, like a line at a counter, you need the other classic structure: Queues and Deques. After that, Monotonic Stack shows a stack that keeps its items in order and answers "what is the next bigger value?" for every item in one pass.