Last in, first out

A stack is a pile of items where you can only reach the top one. You add to the top and take from the top. So the last item in is the first item out. This one rule turns out to fit a surprising number of problems.

What a stack is

A stack has three operations:

• push: put an item on top;
• pop: take the top item off and give it back;
• peek: look at the top item without taking it off.

There is no way to reach an item lower down, except by popping everything above it. This rule is called last in, first out, or LIFO for short.

A Python list is a stack

Python has no separate stack class, because a list already works as one. Treat the end of the list as the top: append pushes, pop() pops, and stack[-1] peeks. Step through a short run:

stack = []
stack.append('A')
stack.append('B')
stack.append('C')
stack.pop()   # gives 'C'
stack[-1]     # the top
stack.append('D')
stack.pop()   # gives 'D'
stack.pop()   # gives 'B'

All three operations work at the end of the list, so no other item moves. Each one is O(1). (append is O(1) on average: once in a while the list grows its block of memory, as BIGO-7 and ARRS-1 showed.)

Where stacks appear

• Undo: each change is pushed. Undo pops the most recent one.
• Function calls: Python keeps a stack of calls that have started but not finished (RECR-2). The function running now is on top.
• Nesting: brackets, tags in a web page, folders inside folders. The thing that was opened last must be closed first (lesson 2).
• Going back: a search that tries a path, and goes back one step when it cannot go on (depth-first search, in GRPH), keeps the path on a stack.

A good sign that a stack fits: you need to come back to things in the reverse of the order you met them.

The empty stack

pop() and stack[-1] on an empty list raise IndexError. Most stack bugs are one of these. Check first, using the fact that an empty list counts as false:

if stack:                # not empty
    top = stack.pop()
else:
    ...                  # decide what an empty stack means here

Often the empty case is an answer, not an error. In lesson 2, a closing bracket that arrives when the stack is empty means the text is not balanced.