DATA·II Data structures Chapter 15 of 65
Stacks, queues and a calculator
A calculator, built one part at a time. First it works like the HP-35, a 1972 pocket calculator with no “=” key; then Dijkstra’s recipe teaches it brackets and operator precedence. Along the way we find the same kind of calculator inside Python, and a queue of keystrokes that runs in a circle.
Data structures
- 13 Complexity
- 14 Arrays
- 15 Stacks, queues you are here
- 16 Hash tables
- 17 Trees
- 18 Heaps
- 19 Graphs
Builds on: 14 · How a list lives in memory
What you will take away
- spot the problems that call for a stack, and write undo, a bracket checker and a traversal without recursion
- turn ordinary expressions into reverse Polish notation and evaluate them, which is to say, write a calculator of your own
- choose between a stack, a queue and a deque, and build a queue on a ring buffer
At the end of the last chapter we noticed how many things hand back the most recent item first. The Back button in a browser returns you to the page you opened last. Ctrl+Z undoes the last action, then the one before it. Functions return in the reverse order of their calls. We already have the right tool: a list we touch only at its end, where, as we found out, adding and removing both cost $O(1)$.
Out of such tools we will build a machine that works: a calculator. It will understand 2 * (3 + 4) - 5, brackets and operator precedence included, tell you when the brackets are wrong, and keep its keystrokes in a queue that runs in a circle. It has five parts, and each of them is a data structure.
Part one: a stack of plates
Picture a stack of plates in a cafeteria. A clean plate goes on top, and you take one from the top as well. You can’t get at the bottom plate without lifting off the ones above it. The last plate put down is the first to go: last in, first out, or LIFO.
That discipline is what a stack is. It has three operations: put something on top (push), take the top item off (pop), and look at the top without taking it (peek). Nothing else: no reading by position, no inserting in the middle. The poverty of the interface is the whole point. A program that uses a stack is guaranteed never to reach into the middle or get the order mixed up.
Python has no separate stack type: an ordinary list does the job. append puts an item on top, pop() takes it off, a[-1] peeks, and all of it is $O(1)$, because the top of the stack is the end of the array, where there is room to spare and nothing has to shift. Here is the stack everyone knows, the Undo button.
Before it changes the text, every action puts the previous state on the stack. Ctrl+Z takes the top state off and rolls back one action, the most recent. Press “Steps” and watch the undo stack grow over three words and shrink over two undos.
The description of a stack says nothing about how it is built inside. You can build it on an array, as here, or on the linked list from the last chapter, with the head as the top, and push and pop are $O(1)$ there too. A description of a structure by its operations, with nothing said about its construction, is called an abstract data type. Stacks, queues and dictionaries are abstract types; arrays and linked lists are ways of making them.
Back and forward
A browser has two buttons, Back and Forward, and it has two stacks. When you go back, the current page doesn’t disappear: it goes onto the forward stack. And what happens to the forward stack if, after going back, you click a new link? Guess before you check.
A new link empties the forward stack down to the bottom: the future you turned away from is gone. That is also why, in a text editor, once you undo and then type something new, Redo (Ctrl+Y) has nothing left to bring back.
A stack you already had
You have been working with a stack since Chapter 5, where it went by the name of the call stack. A function call pushes a frame, and a return pops it. The function called last finishes first: LIFO in its purest form. And the stack overflow we ran into in Chapter 9 is a stack that grew taller than allowed.
Back in Chapter 9 we said that any recursion can be rewritten as a loop, but then you have to keep the stack of unfinished business yourself. Now we can. Here is the flattening of nested lists from that chapter, without a single recursive call, on a stack of our own.
Our own stack lives in an ordinary list, and its only limit is memory. The call stack is limited to a thousand frames. And reversed is there because a stack hands back the last thing put on it first: to take the first item out first, you have to push from the end.
Part two: a calculator with no “=”
Why HP’s engineers wanted a keyboard like that becomes clear from the expression $(3 + 4) \times (5 + 6)$. While an ordinary calculator works on the second bracket, it has to remember the multiplication still waiting and know that multiplication outranks addition. A notation that puts the numbers first and the operation after them has none of these worries. In it the expression looks like this:
$$3\ \ 4\ \ +\ \ 5\ \ 6\ \ +\ \ \times$$There is one rule for evaluating it. Read from left to right. A number goes onto the stack. An operator takes the top two numbers off the stack, does its arithmetic on them and puts the result back. Three, four: two numbers on the stack. The plus turns them into seven. Five, six: the stack holds seven, five, six. Plus: seven and eleven. Times: seventy-seven. No brackets and no precedence: the order of operations is written into the order of the symbols.
This notation is called reverse Polish notation, or RPN for short, and the familiar one, with the operator between the numbers, is infix notation. Try the calculator below: it behaves like an HP-35, except that its stack is on show.
A calculator in ten lines
The rule for evaluating RPN goes into Python almost word for word. The operations fit neatly into a dictionary whose values are the lambdas from Chapter 10.
One subtlety: the second operand comes off the stack first. For addition and multiplication the order doesn’t matter, but 8 3 - has to give five, not minus five. Check it yourself by swapping a and b.
This calculator is too trusting. Give it 3 +, and stack.pop() crashes with an IndexError, a message that tells the user nothing. Give it 3 4, and it quietly returns four, forgetting about the three. Teaching it to tell a well-formed expression from a broken one is the first task of the chapter, eval-rpn; the raise from Chapter 11 will come in handy.
Part three: are the brackets right?
Reverse Polish notation suits a machine, but people write 2 * (3 + 4). A calculator for people has to understand brackets, and before anything else it has to check that they are in the right places. For parentheses alone a counter would do: an opening one adds one, a closing one subtracts one, the counter may never drop below zero and must end at zero. But expressions and programs also have square brackets and curly braces, and then counters are no help. In ([)] each kind of bracket is in order on its own, and together they are nonsense.
The rule that works is different: a closing bracket must close the most recent opening bracket that is still open. Most recent means a stack.
This is how Python itself checks brackets before it runs a program. In Chapter 1 it complained about an unclosed quote; about brackets it has even more to say. Run the cell and see which bracket it names.
The message “closing parenthesis ')' does not match opening parenthesis '['” describes the moment in our function when stack.pop() returned the wrong bracket. The matching-bracket highlight in a code editor works the same way. In the balanced task we will teach the function to say where the error is and to ignore brackets inside strings, as the interpreter does.
Part four: the shunting yard
An infix expression is a train of cars, numbers mixed in with operators. It has to be rearranged into reverse Polish notation, where every operator comes after its numbers. The yard has three tracks: the incoming track on the right, the outgoing track on the left, and a dead-end siding running down. Numbers go straight through to the output without stopping. Operators pull into the siding and wait, and the siding is a stack: the only car that can leave it is the one that came in last.
The whole art lies in when to let the operators out of the siding. Say the input is 3 + 4 * 2. The three goes to the output, the plus into the siding, the four to the output. Now the times sign comes up. It outranks addition, so it must be carried out first, which means it must come before the plus in the RPN. So the plus stays where it is, and the times pulls into the siding on top of it. The two goes to the output, the input runs out, and the siding empties from the top: first the times, then the plus. What comes out is 3 4 2 * +.
Here are all the rules of the yard. A number goes straight to the output. An operator first lets out of the siding every operator that outranks it or ranks the same, and only then pulls in itself. An opening bracket pulls into the siding and acts as a wall: no operator leaves past it. A closing bracket lets out everything down to the opening one, and both brackets vanish. When the input runs out, the siding lets out whatever is left in it. This recipe is called the shunting-yard algorithm.
Operators of the same rank are let out too, and 8 - 3 - 2 shows why. Subtraction goes from left to right: $(8 - 3) - 2 = 3$. So the first minus has to reach the RPN before the second: 8 3 - 2 -. If equals stayed in the siding, the result would be 8 3 2 - -, which is $8 - (3 - 2) = 7$. Compare 8 - 3 - 2 and 8 - (3 - 2) in the yard.
Every token enters the siding and leaves it at most once, so the whole yard runs in $O(n)$, a single pass over the expression, like evaluating the RPN.
What about powers?
In Chapter 1 we saw that 2 ** 3 ** 2 is 512: powers are worked out from right to left, $2^{(3^2)}$. For the yard this means that two powers of equal rank do not let each other out of the siding, or else we would get $(2^3)^2 = 64$. Operators that are evaluated from right to left are called right-associative, and for them “outranks or ranks the same” becomes “strictly outranks.” Teaching the yard about powers is the third task of the chapter. Unary minus, as in -2 ** 2, is another trap: you have to tell it apart from subtraction by what stands to its left.
The calculator, assembled
One small thing is left: turning the string "2*(3+4)" into a list of tokens. Digits that follow one another are glued into a number, operators and brackets become tokens of their own, and spaces are skipped. Then we connect the three parts in a row.
Sixty lines, and you have a calculator that understands brackets and precedence. Splitting text into tokens, translating it into a form the machine finds convenient and evaluating it on a stack: that, in miniature, is how every interpreter is built. In Chapter 50 we will build a parser for a whole language, and in Chapter 51 an interpreter.
The calculator inside Python
Python evaluates expressions the way the HP-35 did. Before it runs a program, it translates it into instructions for its own virtual machine, and that machine is a stack machine. The dis module shows the instructions.
Read the column of instructions from top to bottom: push a, push b, add, push c, multiply. That is a b + c *, reverse Polish notation. LOAD puts a value on the stack, and BINARY_OP takes the top two off and puts the result back. Every time you run a cell in this course, the arithmetic on the server is done by a stack machine, a distant relative of the pocket HP-35. We will take a closer look at these instructions in Chapter 33.
Part five: a queue of keystrokes
The calculator is assembled, but now it has a new worry. Fingers can be faster than the program: while it computes, a person manages to press three more keys. Those keystrokes mustn’t be lost, and they have to be handled in the order they were pressed. A stack won’t do here, since it would hand back the last keystroke first. What we need is a queue: first come, first served, or FIFO (first in, first out).
Making a queue out of a list is easy and wrong: append at the tail, pop(0) from the head. We already know that pop(0) shifts all the remaining items and costs $O(n)$, and in the race of the last chapter we saw what that looks like on a hundred thousand items. A queue built on list.pop(0) is a classic cause of slow Python programs. We have seen the right tool too: collections.deque.
The name deque is short for double-ended queue, and a deque (say “deck”) is a queue with both ends open for business. It can be a stack (you work with one end) or a queue (you put in at one end and take from the other).
A queue in a circle
Inside the computer itself, where there is no deque and no garbage collector and the memory for the queue is set aside once and for all, keystrokes go into a ring buffer. Take an array of fixed length and two indices: the head, where items are taken from, and the tail, where they are put. Put an item in, and the tail moves on one slot. Take one out, and the head moves. Nothing else has to shift. When the tail reaches the end of the array, it jumps to the beginning, into the slots the head has already freed: the array is bent into a ring, and the index of the next slot is the remainder after dividing by the length.
After two calls to pop and two to push, the array looks odd: ['T', 'Y', 'E', 'R']. But the head is at slot 2, and reading round the ring from there gives “ERTY”, the last four letters of QWERTY in the order they were typed. The last line shows an overflow: the fifth keystroke didn’t fit, and push returned False. The size field isn’t there for decoration. The head and the tail alone are not enough, because when they coincide, the buffer may be either empty or full. So you either store the size, as here, or always keep one slot free, and then “the head equals the tail” can only mean “empty.”
On the IBM PC, the BIOS set aside 32 bytes for the queue of keystrokes, sixteen slots of two bytes each, and two pointers, to the head and to the tail; when the pointers met, the queue was empty. The same design lives on in sound cards, network adapters and event logs: wherever data flows without a pause and memory is limited.
A queue from two stacks
The last part is a puzzle. Suppose you have only stacks and you need a queue. You can build one out of two stacks. New items go onto the first, the inbox. You take items from the second, the outbox. And when the outbox is empty, you move the whole inbox onto it, and the order flips over: the oldest item ends up on top.
Moving can take a while, $O(n)$ at a time. But remember the coins from the last chapter. In its whole life, each item is pushed onto the inbox once, moved to the outbox once and popped from the outbox once. That is three actions per item, however many items there are, so each queue operation costs $O(1)$ amortized. Building such a queue is the last task of the chapter. The puzzle has a practical side too: in functional languages, where the cheapest structure is an immutable list that works as a stack, this is how queues are made.
Which structure would you take for each job: (1) check that the tags in an HTML page are closed properly; (2) serve requests to a server in the order they arrive; (3) keep the last 50 actions for Undo, throwing away the oldest?
Tags are like brackets: the last one opened has to close first, so you need a stack. Requests in order of arrival: a queue. Undo with a limited memory is a stack at one end and a place to throw out old items at the other: a deque with maxlen=50. That is one way to build an undo history of limited depth.
Tasks
Four parts of the calculator, and each needs finishing: one has to learn to spot errors, another to understand powers, and the bracket checker must not get lost in quotes. The tests check the edges too: empty input, a lone bracket, long expressions.
Write eval_rpn(expr) to evaluate an expression in reverse Polish notation whose tokens are separated by spaces. The numbers are integers or decimals and may be negative (-3, 2.5); the operations are + - * /. If the expression is malformed (an operation lacks numbers, more than one number is left on the stack at the end, an unknown token turns up, or the string is empty), raise ValueError with a clear message.
Before taking two operands off, check len(stack) < 2. After the loop, check that a single number is left on the stack.
An unknown token: float("abc") raises ValueError by itself, but its message talks about float and means little to the user. Better to catch it with try/except and raise a ValueError of your own with a clear message.
The number -3 doesn’t get mixed up with the minus operation: split keeps it as a single token, "-3", and there is no such key in OPS. The HP-35 had a separate change-sign key for this, CHS: the sign of a number and subtraction are different things.
Write bracket_error(code) to check the brackets () [] {} in a line of a program. It returns -1 if everything is in order, and otherwise the index of the error, much like the one Python shows in a SyntaxError message:
- for a closing bracket that has nothing to close or doesn’t match the last open one, its index;
- if the string has ended and some brackets are still open, the index of the first of them (Python shows the last one in this case).
The catch: brackets inside string literals, between two single or two double quotes, don’t count. In print(")") everything is in order. Quotes inside quotes of the other kind are ordinary characters; the tests have no escapes like \".
To return the index of an unclosed bracket, the stack has to hold its index along with the bracket itself: stack.append((ch, i)). The first unclosed bracket lies at the bottom of the stack.
For quotes, keep a variable quote: None while you are outside a string, or the quote character itself while you are inside one. Inside a string, skip everything but the quote that closes it.
The variable quote is a little automaton with three states: “outside a string,” “in a single-quoted string” and “in a double-quoted string.” Python reads the text of a program with an automaton of the same kind, only with more states: escapes, triple quotes, comments. Automata are waiting for us in Chapter 54.
Write to_rpn(expr), which takes a string with an infix expression and returns a list of tokens in reverse Polish notation. The expression holds non-negative integers (possibly with several digits), the operations + - * / **, brackets, and spaces in any number. Precedence is as in Python: ** outranks * /, which outrank + -; ** is evaluated from right to left, the rest from left to right. If the brackets don’t pair up, raise ValueError.
For example, to_rpn("2*(3+4)**2") → ['2', '3', '4', '+', '2', '**', '*'], and to_rpn("2 ** 3 ** 2") → ['2', '3', '2', '**', '**'].
Start with the tokenizer: as it stands, ** turns into two * tokens. When you meet an asterisk, look at the next character.
For ** the rule for leaving the siding is different: only operators that strictly outrank it leave, and equals stay put. A set of right-associative operators comes in handy: RIGHT = {"**"}.
Unpaired brackets: a closing bracket with no opening one in the siding is an error, and so is an opening bracket still in the siding at the end.
The whole difference between left and right associativity is one comparison: “outranks or ranks the same” against “strictly outranks.” And in ALGOL 60, the language Dijkstra invented the yard for, powers were evaluated from left to right: 2↑3↑2 meant $(2^3)^2 = 64$ there. The order of operations is an agreement made by a language, not a law of nature.
Write a class Queue with the methods push(x), pop() (take the oldest item; an empty queue raises IndexError) and __len__. Inside, only two lists are allowed, and they are used as stacks: only append, pop() without an argument, len and the test for emptiness. No pop(0), no insert, no slices and no deque. The tests mix a hundred and fifty thousand operations under a time limit.
Always take items from outbox. If it is empty, move everything from inbox into it, taking the items off the top one at a time.
Move items only when outbox is empty, not on every pop. Otherwise the order gets scrambled and the time becomes quadratic.
Each item makes the trip “into the inbox, into the outbox, out” only once, so $n$ operations cost $O(n)$ in total, even though a single pop sometimes moves thousands of items. It is the same amortization as with append on a list: the expensive steps are rare and paid for in advance.
What next
The HP-35 had one more key, STO: it stored a number in a separate memory register, to be fetched later with RCL. There was one register. Suppose we want our calculator to remember variables by name, x = 5, rate = 0.07, and soon there are lots of them. In a list of name–value pairs, finding a name costs $O(n)$: with a million variables, every lookup would go through a million entries. A stack can’t find things by name, and neither can a queue or an array. Yet a Python dictionary finds a name among a million in a single operation. In the next chapter we will build a structure like that ourselves, and then try to break it.