Stacks and queues

Picture a stack of plates in a kitchen. A clean plate goes on top. When you need a plate, you take it from the top too—the very one that was put there last. The bottom plate comes up only after all the others are gone.

Programs often need the same order. The Undo button in an editor first undoes the latest action, then the one before it. What is saved later comes out sooner.

An ordinary list gives this order if you add and remove elements only at its end:

history = []
history.append("type")
history.append("bold")
history.append("delete")
print(history[-1])  # delete
last = history.pop()
print(last, history)  # delete ['type', 'bold']

Let's walk through the example line by line:

1. Three append calls put the actions "type", "bold" and "delete" on the stack history. The last one ends up on top.
2. history[-1] looks at the top plate and prints delete without taking anything off.
3. history.pop() takes the top value off and stores it in last.
4. The last print prints delete ['type', 'bold']: the first two actions are left in the list.

A stack on a list

A stack is a collection of values that you add to and remove from at one end only. That end is called the top. The value put on last is taken off first, like the top plate.

In a list, the top is its end. A stack needs three actions:

• append(x) puts the value x on top;
• pop() with no argument takes the value off the top and returns it;
• stack[-1] only looks at the top and does not change the stack.

No other elements move. So append and pop() are equally fast on a list of any length.

The loop while stack: takes values off until the stack is empty: an empty list is falsy. The values come out in the reverse of the order in which they were put on:

words = ["one", "two", "three"]
stack = []
for w in words:
    stack.append(w)
out = []
while stack:
    out.append(stack.pop())
print(out)  # ['three', 'two', 'one']

The words went onto the stack as one, two, three and came out the other way around. The first plate put down always ends up at the very bottom.

This is where the analogy stops. A real stack won't give up its middle plate, but a list has no such rule: stack[0] reads the bottom element. A stack is an agreement: the program itself decides to touch only the top.

That is why a stack suits tasks where whatever opened last must close first. Nested brackets in an expression work this way.

A queue on a deque

A queue works the other way around: the value that came first is taken first, as in a line at a checkout. A list's pop(0) also takes the first element, but slowly. After it, every remaining element moves one position to the left. In a list of a million elements, each call moves almost a million values.

For a queue, the collections module has the type deque. It is like a list, but it adds and removes values quickly at both ends. The line from collections import deque loads the single name deque from the module:

from collections import deque

line = deque(["Ann", "Bob"])
line.append("Kim")
first = line.popleft()
print(first, line)  # Ann deque(['Bob', 'Kim'])
print(len(line), line[0])  # 2 Bob

Let's see what happens here:

1. deque(["Ann", "Bob"]) creates a queue with "Ann" at the front.
2. append("Kim") adds "Kim" at the end of the queue.
3. popleft() takes a value off the start, that is, the left end, and returns "Ann".
4. len and reading by index work the same as for a list: two people are in line, and Bob is first.

A deque has a pop() method too, and like a list's, it takes the last value.

Interviewers like to ask why a queue isn't built on a list. The answer: pop(0) shifts every remaining element, while a deque's popleft() takes the first element without any shifting.

Common mistake

A value is taken off an empty stack:

stack = []
stack.pop()  # ✗

IndexError: pop from empty list

There is nothing to take, and the program stops with an IndexError. popleft() on an empty deque raises an IndexError too. Before you take a value off, check that the collection is not empty—if stack: or while stack:, as in the loop above.

Key points

• A stack gives back first what was put on last; on a list, that is append and pop().
• stack[-1] looks at the top without taking it off.
• A queue gives back first what came first; it is built on a deque with append and popleft().
• pop() and popleft() on an empty collection raise IndexError, so check if stack: first.