Stacks and queues

What you will be able to do

After this lesson you can

• use a list as a stack, with push, pop and peek,
• check balanced brackets with a stack,
• use collections.deque as a queue, and
• say which structure fits which job.

Why structures?

You know lists, dictionaries, tuples and sets. They are general. But for some jobs, a simpler shape is better, because its rules keep you from doing the wrong thing, and say clearly what the program does. A data structure is a way of organising data together with the actions that are allowed on it. In this chapter you meet five. The first two are the simplest: the stack and the queue.

The stack: last in, first out

Think of a pile of plates. You put a plate on top, and you take a plate from the top. The last plate that you put on is the first that comes off. This is LIFO: last in, first out.

A Python list is a good stack. append pushes onto the top, and pop() takes the top off.

Predict first. What do the two pop() calls show, and what does the empty stack do? Then run it.

• push is stack.append(x). pop is stack.pop(), which removes the last item and gives it back. peek is stack[-1]: look at the top without removing.
• while stack: is a short way to say "while the stack is not empty", because an empty list is False.
• stack.pop() on an empty stack raises an IndexError. Always check, or catch it.
• Reverse a text: push every letter, and pop them all. They come out in the opposite order: stack becomes kcats.
• Undo: before each change, push the old text. To undo, pop. The program makes Hello there! and then undoes twice, getting back Hello there and then Hello. This is how the Undo button in every editor works.

A classic job: balanced brackets

How does a computer check that (a + b) * [c - d] has its brackets in order, and that {[(])} does not? A stack does it.

Test: ((a) leaves one ( open: False. a)( has a closing bracket with nothing to close: False. {[(])} has ] where ) is expected: False. An empty text, and a text with no brackets, are balanced: True. A compiler uses this idea to check every program that you write.

The queue: first in, first out

A waiting line at a bus stop is a queue. The person who came first is served first. This is FIFO: first in, first out. New arrivals join at the back, and the person at the front leaves.

A list is a poor queue, because list.pop(0) takes the first item, and then every other item moves one place forward. For a long list, that is slow. Python has a better tool: collections.deque (say "deck": a double-ended queue). It is fast at both ends.

A readout of 0 means the structure is empty: the next pop() or popleft() would fail.

Which one?

Ask: "which item should come out next?" The newest: a stack. The oldest: a queue.

Common mistakes

• Popping from an empty stack or queue. An IndexError. Test first.
• Using list.pop(0) for a big queue. It is slow. Use deque.
• Using the wrong end. A stack uses the same end for push and pop. A queue uses opposite ends.
• Forgetting that pop() also removes. Use stack[-1] to only look.
• Leaving a bracket on the stack and forgetting the final check that it is empty.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the lab Stack tools. You write balanced, and the checker tries good and bad texts.
2. Build. Open the problem Reverse with a stack and the problem Serve in order.
3. Stretch. Open the problem Stack or queue? and decide for six jobs.

Remember these

• A stack is LIFO: push and pop at the same end. A list does it.
• A queue is FIFO: join at the back, serve from the front. deque does it, with append and popleft.
• Balanced brackets: push the openings, match each closing with the top, and the stack must be empty at the end.
• Ask which item must come out next: the newest (stack) or the oldest (queue).

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. After pushing A, B and C on a stack, what does pop() give?

2. After joining A, B and C in a queue, who is served first?

3. Why is a deque better than a list for a queue?