Stacks That Carry State

Stacks & Monotonic Stacks, lesson 2 of 3

Stacks That Carry State

Push pairs to remember a running minimum, and evaluate expressions with a stack.

11 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Sometimes the item alone isn't enough: you also want a fact about everything underneath it - the minimum so far, a count, a position. The trick: push a tuple that stores the item and that fact.

Why does it work? While an entry sits on the stack, nothing below it can change. So a snapshot taken at push time stays correct until that entry is popped.

op       stack of (value, min so far)
push 5   [(5,5)]
push 3   [(5,5), (3,3)]
push 7   [(5,5), (3,3), (7,3)]   min = 3
pop      [(5,5), (3,3)]          min = 3
pop      [(5,5)]                 min = 5

Every operation stays O(1): no rescanning with min(stack).

Example

A stack that knows its minimum

Swap min for max and you have a max-stack. The same idea stores anything "so far": sums, counts, indices.

Quiz

What does this print?

Evaluating expressions. In Reverse Polish Notation (postfix) the operator comes after its two operands, so no parentheses are needed:

infix:    (3 + 4) * 2
postfix:  3 4 + 2 *

Scan left to right. A number is pushed. An operator pops the right operand first, then the left one, and pushes the result. At the end the answer is the only thing left on the stack.

Example

Postfix evaluation, traced

That's 5 + (1 + 2) * 4 - 3 = 14. Pop order matters for - and /: swap a and b and "9 2 -" would give -7 instead of 7.

Quiz

What does this print?

Exercise

Simplify a Unix path

Write simplify_path(path) for an absolute Unix path. Split on /, then for each part:

  • "" or ".": skip it
  • "..": go up one folder (if you're not at the root)
  • anything else: a folder name, go into it

Return "/" followed by the folders joined with /. Example: "/a/./b/../../c/" -> "/c".