Stacks

A stack is the simplest structure in this course, and one of the most useful. It is a list that you promise to use from one end only: you add at the end, and you take from the end. That small promise is enough to check that brackets match, to undo a mistake, to work out an arithmetic expression, and to answer a question about every item of a long list in a single pass. This module builds all four.

Before this, you can: add to and take from the end of a list, and loop while a condition holds; keep pairs in a list, and say when two names refer to one list; write a function from its contract and test it with asserts.

By the end you will be able to use a list as a stack, guard against an empty one, match pairs that nest, keep a history to go back through, evaluate an expression with a stack, let items wait on a stack until their answer arrives, and count the work a loop does when counting the loops is misleading.

Before you read on, decide what this prints:

plates = []
plates.append("red")
plates.append("blue")
plates.append("green")
plates.pop()
plates.append("white")
print(plates.pop(), plates.pop(), plates.pop())

white blue red

Green went on third and came off first. Then white went on, and came off before blue and red, which had been waiting longer. Whatever was added most recently is what you get back. That is the whole idea.

Last in, first out

A stack is a list used with two operations. append puts a value on top: that is a push. pop takes the top value off and hands it back.

stack = []
stack.append(3)
stack.append(8)
stack.append(5)
print(stack)
top = stack.pop()
print(top, stack)

[3, 8, 5]
5 [3, 8]

The end of the list is the top of the stack. Nothing here is new Python: you met append and pop in Lists. What is new is the discipline. You never look in the middle, never insert at the front, never remove by value. The reward is that you always know which item comes next, the newest, and that neither operation has to touch the rest of the stack, however tall it is. (Now and then an append finds the list's memory full, and Python moves the whole list to a bigger piece, which takes longer. It makes the new piece generously bigger, so this happens more and more rarely as the list grows, and the cost averaged over many appends stays small and steady. When this module counts work, it counts pushes and pops.)

The order has a name, last in, first out. It is the order of a pile of plates, of the Back button in a browser, and of the calls in progress when you step through a program: the function called last is the one that returns first.

Looking without taking

Often you need to see the top without removing it. The top is the last item, so it is at position -1:

stack = [3, 8, 5]
print(stack[-1])
print(stack)

5
[3, 8, 5]

An empty stack has no top. Both ways of asking for it are errors:

stack = []
print(stack.pop())

  File "your_program.py", line 2
    print(stack.pop())
IndexError: pop from empty list

Nearly every bug in a program that uses a stack is this one: a pop or a stack[-1] on a stack that has run out. So the top is always asked for behind a guard. An empty list counts as false in an if or a while, and a list with anything in it counts as true, which gives the guard its usual short form:

stack = []
if stack:
    print("top is", stack[-1])
else:
    print("nothing on the stack")

nothing on the stack

if stack: reads as "if there is anything on the stack". while stack: is "as long as there is".

Matching pairs

Brackets in a program must match: every opener needs its closer, and pairs must nest, never cross. ([]) is right. ([)] is wrong, although it has one of each.

Counting cannot check this. ([)] has as many openers as closers of each kind. What matters is which opener a closer belongs to, and the answer is always the most recent opener that is still waiting. Most recent first: that is a stack.

The method is to read left to right. Push each opener. When a closer arrives, the opener on top of the stack must be its partner; if it is, pop it, and if it is not, the text is wrong.

PARTNER = {")": "(", "]": "[", "}": "{"}

def matched(text):
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in PARTNER:
            if not stack or stack[-1] != PARTNER[ch]:
                return False
            stack.pop()
    return not stack

print(matched("([])"), matched("([)]"), matched("(()"), matched("())"))

True False False False

There are three ways to fail, and the function has a place for each. ([)] fails at the ): the top of the stack is [, the wrong partner. ()) fails at the last ): the stack is empty, so not stack is true, and Python never evaluates stack[-1], which would have been an error. (() gets through the loop and fails at the end: an opener is still waiting, so the stack is not empty.

That last line is the one people forget. A loop that finds no fault has not proved the text right. The stack must also be empty.

Going back

Undo is a stack of what things were. Before each change, push the state as it is. To undo, pop the last one and put it back.

words = []
history = []

history.append(words.copy())
words.append("once")
history.append(words.copy())
words.append("upon")
print(words)

words = history.pop()
print(words)
words = history.pop()
print(words)

['once', 'upon']
['once']
[]

The .copy() matters, for the reason you met in References and Grids. history.append(words) would push the list itself, not a picture of it, and every entry in the history would be the same list, changing whenever words changes. Undo would then hand back the present.

Undo comes off in the reverse of the order things were done, the most recent change first. Any time a problem says "the most recent one that is still open", "go back to where you were" or "in reverse order", reach for a stack.

Operands that wait

We write arithmetic with the operator between its numbers: (3 + 4) * 2. That needs brackets and rules about which operator goes first. There is another way of writing it that needs neither: put each operator after its two numbers.

3 4 + 2 * means: 3, then 4, then add them; then 2, then multiply. Read left to right, with a stack:

• a number is pushed;
• an operator pops two numbers, works out the result, and pushes it.

At the end, one number is left, and it is the answer.

def add_only(expression):
    stack = []
    for token in expression.split():
        if token == "+":
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)
        else:
            stack.append(int(token))
    return stack.pop()

print(add_only("3 4 +"), add_only("1 2 3 + +"), add_only("10 20 + 30 +"))

7 6 60

The numbers wait on the stack until their operator arrives. In 1 2 3 + + three numbers are waiting when the first + comes; it takes the two newest, 2 and 3, and leaves 5 in their place.

Notice the order of the two pops. The first pop gives the right-hand number, because it was pushed last. For addition that makes no difference. For subtraction it decides the answer: 7 2 - is 7 − 2, and a function that pops them into the wrong names gives −5.

Waiting for an answer

Here is a question about every item of a list. People stand in a line, all facing the front, and each can see forward until someone taller stands in the way. For each person, who is the first taller person ahead of them?

The plain way uses two loops: for each person, look along the people ahead until one is taller. In a line where everybody is shorter than the person behind them, each person looks at everyone ahead and finds nobody: for a thousand people, close to half a million comparisons to learn nothing.

A stack does it in one pass, by turning the question round. Do not go looking for each person's answer. Let each person wait on a stack, and let the answer come to them. Walk along the line from the back. When you reach a new person, they are the answer for every waiting person who is shorter than they are, and those people are on top of the stack.

def blockers(heights):
    pairs = []
    waiting = []
    for height in heights:
        while waiting and waiting[-1] < height:
            pairs.append((waiting.pop(), height))
        waiting.append(height)
    return pairs

print(blockers([170, 160, 150, 175, 165, 180]))

[(150, 175), (160, 175), (170, 175), (165, 180), (175, 180)]

Each pair is a person and the person who blocks them. Follow it through. The first three are 170, 160 and 150: each is shorter than the one before, so none of them blocks anybody, and all three wait. Then comes 175, taller than all of them. It pops 150, then 160, then 170, and makes a pair with each; then it waits itself. 165 blocks nobody. 180 pops 165 and then 175. Nobody is taller than 180, so 180 is still on the stack at the end and is in no pair.

Look at what the stack holds at any moment: heights that never rise, from the bottom to the top. It must be so, because anyone shorter than a person who came later has been popped by them. Two people of the same height can both be waiting, one above the other: the test is <, and someone your own height does not block your view. This shape is why the people a newcomer can answer are always together on top, and why the loop can stop at the first person it cannot answer.

This function reports its answers as pairs of heights, in the order they are found. Often you want something else: an answer for each position in the list, or how far ahead the answer was. Then heights alone on the stack are not enough, and you have to decide what should wait there. The lab asks you to work that out.

Counting the work

That function has a while loop inside a for loop, and a loop inside a loop usually means the work grows with the square of the input: twice the people, four times the work. Not here, and the reason is worth being able to state.

Count what happens to each person, not how the loops are nested. Each person is pushed once, by the last line of the for. Each person is popped at most once, because once popped they are gone. So for n people there are exactly n pushes and at most n pops, however the pops happen to be shared out among the turns of the outer loop. One turn may pop many people; then those people are not there for any later turn to pop.

def count_work(heights):
    pushes = 0
    pops = 0
    waiting = []
    for height in heights:
        while waiting and waiting[-1] < height:
            waiting.pop()
            pops = pops + 1
        waiting.append(height)
        pushes = pushes + 1
    return pushes, pops

print(count_work([170, 160, 150, 175, 165, 180]))
print(count_work(list(range(1000))))

(6, 5)
(1000, 999)

A thousand people, about two thousand stack operations, where the two plain loops could make close to half a million comparisons. This is a count of pushes and pops. It says the work keeps in step with the number of people; it does not say that every single push takes the same time, for the reason given at the start.

When a loop inside a loop looks expensive, ask what each item can do in its whole life. If the answer is "be added once and removed once", the work is in step with the number of items.

In the lab

You will trace pushes and pops, write a bracket checker that says where the first fault is, build an editor with undo, write a calculator for expressions with the operator last, work out how long each day waits for a warmer one and draw the answer, and count the work. Then four assignments: tidy a file path, find the nearest taller building, repair a checker that says yes too often, and one problem that does not tell you a stack is the way in.