Stacks

A stack hands back the most recent thing it was given. That one rule, last in, first out, is exactly what nesting needs: the bracket opened last must close first, the function called last must return first, the edit made last is the first to undo, and in an arithmetic expression the operator still waiting with the tightest grip must apply first. This page defines the stack as an abstract data type, builds it three ways (on a Python list, in a fixed array with a top index, and from linked nodes) and measures what growing an array costs. It then puts the stack to work: checking brackets of several kinds, converting expressions between infix, prefix and postfix with the shunting-yard algorithm, evaluating both forms, building expression trees, making the call stack visible and turning recursion into a loop, and finally the min-stack and the monotonic stacks behind several well-known linear-time algorithms. Afterwards you will be able to trace any of these by hand with the stack written out after every step, implement them with correct handling of precedence, associativity, unary minus, underflow and overflow, and choose between a Python list, collections.deque and queue.LifoQueue. It builds on Arrays and dynamic arrays and Linked lists, and leads to Trees and traversals, Recursion and Breadth-first and depth-first search.

The structures and algorithms need only the standard library; to run the plots and the notebook install the base group.

Intuition

Picture a pile of papers on a desk. A new sheet goes on top, and when you need one, you take the top sheet, because the others are underneath it. Nobody pulls a sheet from the middle of the pile. That pile is a stack, and the order it imposes, the newest first, turns out to be the natural order of anything nested.

Read the text {[a(b)c](d)} from left to right. When the ) after b arrives, which bracket must it close? Not the { that opened first, but the ( that opened last. Each closing bracket belongs to the most recent bracket still open, so a reader only ever needs the open brackets as a pile, checking and removing the top one. The same thing happens when a function calls another function: the one called last finishes first, and the caller resumes where it left off. And it happens in arithmetic: in 6 - 2 * 3 the multiplication is met second but must happen first, so the subtraction waits underneath it.

The diagram shows the contract on the left, three implementations in the middle and, in the filled boxes on the right, the jobs this page and the rest of the handbook give a stack. The Python list, the outlined box in the middle, is the implementation used in practice; the other two show what it hides.

How it works

The stack abstract data type

A stack holds a sequence of items and offers five operations:

• push(x) puts x on top.
• pop() removes the top item and returns it.
• peek() returns the top item without removing it.
• is_empty() says whether there are no items.
• len() says how many items there are.

Its behaviour is pinned down by a few equations. Pushing and then popping gives back the same stack and the same item, peeking after a push sees the item just pushed, and a new stack is empty:

Popping or peeking at an empty stack is an error called underflow. A stack built in a fixed amount of memory can also overflow, when a push finds it full. Equally important is what a stack does not offer: there is no way to look below the top, no search and no indexing. Every algorithm on this page works through push, pop and peek alone, and that restriction is what makes a stack fast, simple and easy to reason about.

This page writes a stack bottom to top as a Python list, so [6, 4, 2] has 2 on top. That is the order in which a Python list stores a stack, and every trace below uses it.

A stack on a Python list

A Python list keeps its items in one contiguous array, and appending to the end or removing from the end costs O(1), while inserting or removing at the front shifts every other item. So the top of the stack is the end of the list: ArrayStack.push is list.append and ArrayStack.pop is list.pop. The class adds three things to the bare list: an exception named for the stack's own error, StackUnderflow, a counter of pushes, pops and peeks, and an optional capacity that makes the stack refuse a push, with StackOverflow, once it holds that many items. Iterating over any stack in the package runs from the top down, the order in which pops would return the items; as_list() gives them bottom to top.

A fixed array with a top index

Below Python's list there is always a plain array of fixed size. BoundedStack makes that visible: an array of capacity slots and an integer top, the index of the topmost item. An empty stack has top = −1; a push first checks for overflow, then increments top and writes the item there; a pop first checks for underflow, then reads the slot at top, clears it and decrements top.

The invariant is the line above: slots 0 to top hold the items, bottom to top, and every slot above top is empty. Clearing the slot on a pop matters in a garbage-collected language, because otherwise the array keeps a reference to an item the stack no longer holds and the item can never be freed.

Each frame shows the array after one operation of the worked example, with the new item filled and the slot that refused a push outlined. The overflow at push 64 changes nothing, so the pop after it returns 11, the last item that did get in.

There are two common ways to define the index. This page uses top as the index of the top item, so empty means −1 and full means capacity − 1. The other convention keeps the index of the next free slot, which equals the size, so empty means 0 and full means capacity. Both are correct; mixing them is not. A stack that starts at −1 but tests for empty with 0 refuses to pop its last item, and one that tests for full with capacity writes past the end of the array.

A linked stack

A singly linked list is a stack waiting to be used: keep a pointer top to the first node, push by linking a new node in front of it, and pop by moving top to the second node. Both are O(1) in the worst case, and there is nothing to grow, so the only way to overflow is to run out of memory.

A push sets two pointers, the dashed ones, and their order matters: the new node's next must point at the old top before top moves to the new node, or the only reference to the rest of the stack is lost. Python frees a popped node by itself once nothing refers to it, so there is no explicit free. The price of the links is memory: each item lives in a node object of 48 bytes in CPython on a 64-bit machine, plus the 8-byte pointer to it, where a list slot is just the 8-byte pointer.

Growing a full array

A Python list never overflows because it grows: when a push finds the array full, a larger array is allocated and every item is copied across. How much larger decides the cost. GrowableStack implements three growth rules and counts every copy:

• Doubling: the new capacity is twice the old one.
• CPython's rule for lists: the new size plus an eighth of it plus 6, rounded down to a multiple of 4, so a list grows to 4, 8, 16, 24, 32, 40, 52, 64 and so on, about 12.5 percent each time.
• A constant increment: add the same number of slots, say 16, every time.

The first two grow geometrically, and the cost section shows that a push then costs O(1) amortized: the rare expensive pushes are paid for by the many cheap ones before them. The third makes pushes quadratic in total. An array that shrinks must not shrink at the same threshold where it grows, or a push and a pop at the boundary would each copy everything; halving the capacity only when the stack falls to a quarter full avoids that.

Reversing and reaching below the top

Because a stack only gives up its items from the top, popping everything out reverses the order. That is often the point: pushing a word letter by letter and popping it back spells it backwards, which is what reversed_by_stack does. Reaching an item below the top through push and pop alone takes a second stack. To bring the bottom item to the top, bottom_to_top pours every item into a temporary stack, which puts the old bottom on the temporary stack's top, sets that item aside, pours the rest back, which restores their order, and finally pushes the item it set aside. For n items that costs 2n pushes and 2n pops, so it is O(n) like the single items.append(items.pop(0)) it would be on the underlying list; the point of the exercise is that it needs nothing but the contract, which matters for code that must not depend on how a stack is stored.

Balanced brackets

A text is balanced when its brackets nest properly: every closer matches the most recent unmatched opener, of the same kind, and nothing stays open. The check reads the text once with a stack of openers:

• An opener is pushed, with its index.
• A closer pops the top opener and checks that the two are partners, such as ( and ).
• Other characters are skipped.
• At the end the stack must be empty.

The invariant behind it is that after each character the stack holds exactly the openers that are still unmatched, in the order they were opened. A closer must belong to the most recent of them, which is on top. So there are exactly three ways to fail, and check_brackets reports each with the index at fault: a closer of the wrong kind (a mismatch), a closer with nothing open (the stack is empty when it arrives), and an opener never closed (the stack is not empty at the end).

With a single kind of bracket a stack is more than needed. A counter of open brackets does the job: it must never go negative and must end at zero.

With several kinds, the counter cannot tell ([)] from ([]): both keep the depth non-negative and end at zero, but in the first the ) arrives while [ is the most recent opener. Only a stack remembers which kind is on top. How many balanced texts are there? With m pairs of one kind, the Catalan number of m, and with k kinds each pair can be any of them:

The tests enumerate all strings of several lengths, up to ten brackets, and confirm both counts, and compare the checker on thousands of random texts with a slow reference that repeatedly deletes adjacent pairs such as () until nothing changes.

Infix, prefix and postfix

The usual way of writing arithmetic puts each binary operator between its operands: a - b. That is infix notation. Prefix notation, also called Polish notation, puts the operator first: - a b. Postfix notation, or reverse Polish notation, puts it last: a b -. In prefix and postfix the order of the tokens alone fixes the order of the operations, so neither needs parentheses or rules about which operator binds tighter: a b c * - and a b - c * can only mean a − b·c and (a − b)·c.

Infix needs both. Without them, an infix expression with m operators can be read in as many ways as there are binary trees with m internal nodes, which is again the Catalan number of m. The expression 10 - 4 - 3 - 2 has three operators and five readings, whose values are 1, 7, 11, 7 and 5. The rules that choose one reading are precedence, which decides between different operators, and associativity, which decides how a chain of equally strong operators groups:

The package's operators, from the loosest to the tightest:

• + and -, left-associative.
• * and /, left-associative.
• Unary minus, written neg in prefix and postfix, which applies to the operand on its right.
• ^, exponentiation, right-associative.

Unary minus binds tighter than multiplication and looser than exponentiation, as in mathematics and in Python, so -2 ^ 2 is −4 and 2 ^ -1 is one half.

The shunting-yard algorithm

Dijkstra's shunting-yard algorithm, named after the railway yards where wagons wait on a siding, converts infix to postfix in one pass with a stack of operators. Operands go straight to the output, because their order never changes. Operators wait on the stack until it is clear that nothing to their right should apply first:

• An operand is appended to the output.
• An operator o first pops to the output every operator t on top of the stack that must apply before it, then is pushed.
• A ( is pushed; it stops any popping, so the operators outside the parentheses wait.
• A ) pops operators to the output until the matching (, which is popped and discarded.
• At the end of the input every remaining operator is popped to the output.

Which operators must apply before o is the pop rule:

The rule is the whole algorithm. An operator on the stack has a complete left operand in the output, and its right operand is being built. When o arrives and t binds tighter, t's right operand is complete, so t goes out. With equal precedence, left associativity means the earlier operator applies first, so t goes out too; right associativity means the later one applies first, so t waits under o. At every moment the output holds the postfix form of the completed subexpressions, in order, and inside each pair of parentheses the operators on the stack get strictly tighter from bottom to top, except for runs of equal right-associative operators.

Every column is the state after one token of the worked example, with what that token added filled. The * is the busy moment: it pops both ^ and then the /, which has the same precedence, before it is pushed.

Unary minus, functions and errors

A minus sign means negation where an operand may start: at the beginning, after an operator, after ( and after a comma. The tokenizer tracks exactly that and turns such a minus into neg. In the parser, unary minus is a prefix operator whose operand has not been read yet, so nothing on the stack can be complete before it: it is pushed without popping anything, and the pop rule handles it later like any other operator. That is how -2 ^ 2 becomes 2 2 ^ neg and 2 ^ -1 becomes 2 1 neg ^, the same orders Python's own parser produces.

Functions extend the algorithm a little. A name followed by ( is a function and is pushed; a comma pops operators back to the ( and counts one more argument; the ) that closes the call pops the function to the output with its number of arguments, since postfix has no parentheses left to show it. So max(1, 2 * x, abs(-y)) becomes 1 2 x * y neg abs:1 max:3.

A parser should also say what is wrong with bad input. The package's parser alternates between expecting an operand and expecting an operator, and every token that arrives in the wrong state is an error with the index where it happened: an operator missing its left operand, an operand right after another (a missing operator), a ) with no (, a ( never closed, a comma outside a function call, an empty pair of parentheses and an expression that ends with an operator.

Evaluating postfix

Postfix is evaluated left to right with a stack of values. An operand is pushed. An operator pops its operands, applies itself and pushes the result. At the end exactly one value remains. The trap is the order of the operands: the value pushed last is popped first, and it is the right operand.

The stack's size also tells whether a postfix expression is valid at all. Each operand adds one value and each operator of arity k removes k and adds one, so the running size is a rank that must never be too small for the next operator and must end at exactly one:

So 3 + fails at the +, which finds one value where it needs two, and 3 4 fails at the end with two values left: an operator is missing. The evaluation of the worked example shows the rank as the height of each stack:

The stack reaches its greatest size, five values, just before the two exponentiations, when 6, 4, 2, 1 and 3 are all waiting. The package evaluates with exact fractions by default and can also use floating point or two kinds of integer division, which round down (as Python's // does) or towards zero (as integer division in C and Java does).

Infix to prefix, and evaluating prefix

Prefix is the mirror image of postfix: reading a prefix expression from right to left gives the postfix form of the expression written backwards. So infix converts to prefix by running the shunting-yard algorithm on the mirror image of the expression: scan the tokens from right to left, let ) open a group and ( close it, and reverse the output at the end. Every rule is mirrored, including associativity:

Seen from the right, the chain 8 - 3 - 2 arrives as 2, −, 3, −, 8. The grouping (8 − 3) − 2 means the minus met second must apply first, so an equal operator already on the stack must stay there: only strictly tighter operators pop. For the right-associative ^ the opposite holds. Some books describe the method as "reverse the infix string, swapping the parentheses, convert to postfix, reverse the result"; that is the same computation, and it is correct only if the conversion in the middle uses this mirrored rule. With the ordinary postfix rule, 8 - 3 - 2 comes out as - 8 - 3 2, which is 8 − (3 − 2) = 7 instead of 3. Unary minus, which stands left of its operand, becomes in the mirrored scan an operator whose operand is already complete, so it pops only the operators that bind tighter, which belong inside its operand, and goes straight to the output.

A prefix expression is evaluated from right to left with a stack of values, exactly like postfix with one difference: now the first value popped is the left operand, as the formula on operand order above shows.

Expression trees

An expression tree has the operators as internal nodes and the operands as leaves, with each operator's operands as its children. Building it from postfix is the evaluation algorithm with subtrees in place of values: an operand is pushed as a leaf, and an operator pops the subtrees of its operands and pushes a new node with them as children. Reading the tree back gives every notation: preorder gives prefix, postorder gives postfix, and inorder gives infix once parentheses are added where precedence and associativity require them. A left operand needs parentheses when it binds more loosely than its operator, or equally under a right-associative one; a right operand when it binds more loosely, or equally under a left-associative one.

The tree has height 6, and the two powers on the right show the right associativity: 2 is raised to the result of 1 ^ 3. The traversals themselves, and rebuilding a tree from two of them, are the subject of Trees and traversals.

The call stack

Every running program uses a stack it never declares. When a function calls another, the caller's state, its local variables and the point where it must resume, is saved in a frame on the call stack, and returning pops that frame. A recursive function therefore uses as many frames as its recursion is deep. Evaluating an expression tree recursively, evaluating the children and then the node, needs one frame per level of the path being followed:

Python stops a recursion at about a thousand frames with RecursionError, and a tree from an expression such as 1 - (1 - (1 - ...)) is as deep as it is long. The cure is to keep the frames in an explicit stack. evaluate_iterative keeps one frame per node being evaluated, holding the node and the values of the children finished so far; the number of those values is the resume point, the part of a real frame that says where the caller continues. The top frame either pushes a frame for its next child, which is a call, or has all its values, computes its own, pops itself and hands the value to the frame below, which is a return.

The stack is deepest, seven frames, when the evaluation reaches the leaves of the inner power, and the frames on the way record what each pending operator already knows, such as / has 4. A recursive evaluation goes through exactly the same seven frames on Python's own call stack.

The Towers of Hanoi show the conversion for a function that does work between its two calls: to move k disks, move k − 1 out of the way, move disk k, then move the k − 1 back on top. Its frames need a stage, 0 before the first call and 1 after it, so the loop knows whether to make the first call or to move the disk. The second call is the last thing the function does, a tail call, so the frame is simply replaced and nothing is pushed to return to.

How recursion works in general, recursion trees and Python's recursion limit are covered in Recursion; depth-first search on a graph is the other classic loop with an explicit stack, in Breadth-first and depth-first search.

A stack with its minimum

Can a stack report its smallest item in O(1)? Searching is O(n), but the minimum of a stack can only change at the top, so it is enough to remember, for every position, the minimum of the items from the bottom up to it:

MinStack stores each item with that running minimum: a push compares once with the minimum below, a pop costs nothing extra, and minimum() reads the top. LeanMinStack saves space with a second stack that only receives an item that is at most the current minimum. The "at most" matters: with two copies of the minimum on the stack, popping one must leave the other as the minimum, so the second stack needs both copies. The same idea with the comparison reversed gives a max-stack.

Monotonic stacks

A monotonic stack is a stack of indices whose values stay ordered from bottom to top. It answers questions of the form "for every element, find the nearest element to one side that is larger, or smaller" in linear time instead of quadratic.

For the next greater element, scan from left to right. The stack holds the indices still waiting for an answer, and their values never increase from bottom to top, because a larger value would already have popped the smaller ones below it. A new value is the answer for every waiting index with a smaller value, and those are all on top, so it pops them until the top is at least as large, then waits itself. Every index is pushed once and popped at most once.

The stock span of day i is the number of consecutive days ending at day i whose price is at most that day's price. The days that can still limit a future span are those not beaten by a later higher or equal price, which is a stack with strictly falling prices; the day left on top after popping is the previous higher price.

The largest rectangle under a histogram is the third classic. A rectangle as tall as bar i extends left and right until the first lower bar on each side:

So the answer needs, for every bar, the nearest lower bar on both sides. Scanning left to right with a stack of bars whose heights never fall from bottom to top, a lower bar ends every taller bar on top: the popped bar's nearest lower bar to the right is the new one, and to the left it is the bar now below it on the stack. A final bar of height 0 empties the stack.

The tallest bars are not the answer: the bars 6, 5 and 7 together allow a rectangle of height 5 and width 3, area 15, more than the 14 of height 2 across all seven bars. The same pattern finds the nearest smaller value, the previous greater element and the maximum of every window, and it is the core of several algorithms for strings and geometry.

Cost

Every operation

For a stack of n items:

• Python list and ArrayStack: peek and pop are O(1); push is O(1) amortized and O(n) in the worst case, when the list must grow and copy every item. CPython may also shrink a list after many pops, which is again amortized O(1).
• BoundedStack: push, pop and peek are O(1) in the worst case, at the price of a fixed capacity and overflow.
• LinkedStack: push, pop and peek are O(1) in the worst case, with one node object per item, about seven times the memory of a list slot.
• Balanced brackets, the conversions to postfix and prefix, both evaluations and building an expression tree: O(n) time for n tokens, and stack space proportional to the deepest nesting.
• Monotonic stacks: O(n) for a whole pass, although a single new element can pop O(n) indices.
• The min-stack: every operation O(1), with up to twice the memory.

The difference between worst case and amortized cost is real here. A list push that triggers a resize copies every item, which matters to code with a deadline per operation; a bounded or linked stack never has such a pause. Over a whole sequence of pushes, though, the list wins comfortably, as the next section counts, and it is faster in practice by a wide margin.

Growing an array, counted

Suppose an array that starts with one slot doubles whenever a push finds it full. Pushing n items triggers a resize at 1, 2, 4 and so on up to the last power of two below n, and each resize copies as many items as the array held:

So n pushes cost n writes and fewer than 2n copies, fewer than three operations per push on average. Any growth by a constant factor r > 1 works the same way, because the capacities before the resizes form a geometric series whose largest term is below n:

For doubling the bound is 2n; for CPython's rule, which grows by at least a factor of 9/8, it is 9n. Growing by a constant s instead copies s, 2s, 3s and so on, which adds up quadratically:

The potential method gives the same answer for each push separately. Charge each push three units and keep the surplus in a potential that grows with the size and falls when the capacity grows:

The example stack_implementations.py pushes 4096 items under each rule and divides the counted copies by n after every push.

The counts equal the values predicted from the growth rules at every n. At n = 4096 doubling has copied 0.9998 items per push, CPython's rule 7.6455 and the constant increment 127.5000, and the last keeps growing linearly. CPython accepts more copies than doubling in exchange for wasting less memory, at most about an eighth of the list, and the C function that copies the pointers is fast; it can often extend the block in place without copying at all, which this count does not model.

Expressions in linear time

The shunting-yard algorithm pushes every operator, function and opening parenthesis exactly once and pops it exactly once. Each comparison in its popping loop either pops an operator or ends the loop for one binary operator. For n tokens, o of them operators or functions, q opening parentheses and b binary operators:

Evaluating postfix pushes one value for every token and pops the operands of every operator, and a valid expression leaves one value, so a postfix expression of m tokens costs exactly m pushes and m − 1 pops:

The example expression_conversions.py counts both on random expressions of 1 to 478 tokens.

Both are straight lines, the signature of linear time. The conversion never needed more than 1.1667 stack operations per infix token; the evaluation needs 2m − 1 for the m postfix tokens, which are fewer than the infix tokens because the parentheses are gone.

Monotonic stacks are linear

In every monotonic-stack pass each index is pushed once and popped at most once, and each comparison either pops an index or ends the popping for the current element:

The example monotonic_stacks.py compares the stack methods with the obvious quadratic scans, each on inputs that are hard for the scan.

At n = 4096 the stack methods need at most 1.9998 comparisons per element, while the scans need 2047.5000 for the span and the next greater element and 4095.0000 for the rectangle on equal heights. On random heights the rectangle scan needs only 16.9236, because a random bar rarely extends far, but its worst case is the quadratic one.

Space: depth, not length

A stack's memory is set by how deeply the input nests, not by how long it is. The bracket checker holds one entry per open bracket. The shunting-yard algorithm holds the operators still waiting: 1 - 1 - ... - 1 with 2000 operators never holds more than one, while 1 - (1 - (1 - ...)) with 2000 parentheses holds two entries per level. The postfix evaluation of the first never holds more than two values, and of the second 2001. The recursive tree evaluator always needs height + 1 frames, which is why the explicit stack matters for deep input; the sample project below draws these peaks for thousands of random expressions.

Worked example

Every step below is printed by examples/worked_example.py and asserted by tests/test_worked_example.py. Stacks are written bottom to top, so the top is the rightmost item.

A bounded stack of capacity four

A BoundedStack with four slots starts empty with top = −1:

• push 31: top = 0, stack [31].
• push 7: top = 1, stack [31, 7].
• pop returns 7: top = 0, stack [31].
• push 19: top = 1, stack [31, 19].
• push 52: top = 2, stack [31, 19, 52].
• push 11: top = 3, stack [31, 19, 52, 11], now full.
• push 64: top = 3 = capacity − 1, so the push overflows and the stack stays [31, 19, 52, 11].
• pop returns 11: top = 2, stack [31, 19, 52].
• peek returns 52 and changes nothing.
• pop returns 52: top = 1, stack [31, 19].
• pop returns 19: top = 0, stack [31].
• pop returns 31: top = −1, stack [].
• pop: top = −1, so the pop underflows.

Checking brackets

The text {[a(b)c](d)} has three kinds of brackets. The letters are skipped:

• { at index 0: push, stack [{].
• [ at index 1: push, stack [{, [].
• ( at index 3: push, stack [{, [, (].
• ) at index 5: pop (, its partner, stack [{, [].
• ] at index 7: pop [, its partner, stack [{].
• ( at index 8: push, stack [{, (].
• ) at index 10: pop (, stack [{].
• } at index 11: pop {, stack [].

The stack is empty at the end, so the text is balanced, after 4 pushes, 4 pops and 4 kind checks, with three brackets open at the deepest point. Each kind of failure in one short text:

• {[a(b]c)}: the ] at index 5 pops the ( from index 3, which needs ). A mismatch.
• [a]b): the ) at index 4 finds the stack empty. A closer with nothing open.
• ({a}: the stack still holds the ( from index 0 at the end. An opener never closed.

Infix to postfix

The expression is 6 - (5 - 1) / 2 ^ 1 ^ 3 * 3 + 4. After each token the operator stack and the output are:

• 6: output 6.
• -: the stack is empty, push. Stack [-].
• (: push. Stack [-, (].
• 5: output 6 5.
• -: the ( on top stops any popping, push. Stack [-, (, -].
• 1: output 6 5 1.
• ): pop - to the output, then pop and discard (. Stack [-], output 6 5 1 -.
• /: the - below binds less tightly, push. Stack [-, /].
• 2: output 6 5 1 - 2.
• ^: the / binds less tightly, push. Stack [-, /, ^].
• 1: output 6 5 1 - 2 1.
• ^: equal precedence, but ^ is right-associative, so the first ^ waits. Stack [-, /, ^, ^].
• 3: output 6 5 1 - 2 1 3.
• *: pop ^ and ^, which bind tighter, then /, which has equal precedence while * is left-associative; the - binds less tightly and stays. Push. Stack [-, *], output 6 5 1 - 2 1 3 ^ ^ /.
• 3: output 6 5 1 - 2 1 3 ^ ^ / 3.
• +: pop *, which binds tighter, then -, equal and left-associative. Push. Stack [+], output 6 5 1 - 2 1 3 ^ ^ / 3 * -.
• 4: output 6 5 1 - 2 1 3 ^ ^ / 3 * - 4.
• End: pop +.

The postfix form is 6 5 1 - 2 1 3 ^ ^ / 3 * - 4 +, after 8 pushes, 8 pops and 9 precedence comparisons. Seven operators and one opening parenthesis were each pushed and popped once, as the cost section says.

Evaluating the postfix form

Reading 6 5 1 - 2 1 3 ^ ^ / 3 * - 4 + from the left, the value stack after each token is:

• 6: push, stack [6].
• 5: push, stack [6, 5].
• 1: push, stack [6, 5, 1].
• -: pop 1, then 5, push 5 − 1 = 4. Stack [6, 4].
• 2: push, stack [6, 4, 2].
• 1: push, stack [6, 4, 2, 1].
• 3: push, stack [6, 4, 2, 1, 3].
• ^: pop 3, then 1, push 1 ^ 3 = 1. Stack [6, 4, 2, 1].
• ^: pop 1, then 2, push 2 ^ 1 = 2. Stack [6, 4, 2].
• /: pop 2, then 4, push 4 / 2 = 2. Stack [6, 2].
• 3: push, stack [6, 2, 3].
• *: pop 3, then 2, push 2 · 3 = 6. Stack [6, 6].
• -: pop 6, then 6, push 6 − 6 = 0. Stack [0].
• 4: push, stack [0, 4].
• +: pop 4, then 0, push 0 + 4 = 4. Stack [4].

The value is 4, after 15 pushes and 14 pops. Had ^ been treated as left-associative, the subexpression would be (2 ^ 1) ^ 3 = 8, the division would give 1/2 and the result 17/2.

Infix to prefix

The same expression scanned from the right, with the mirrored pop rule:

• 4: output 4.
• +: push. Stack [+].
• 3: output 4 3.
• *: the + binds less tightly, push. Stack [+, *].
• 3: output 4 3 3.
• ^: push. Stack [+, *, ^].
• 1: output 4 3 3 1.
• ^: equal precedence and ^ is right-associative, so the mirrored rule pops the first ^, then pushes. Stack [+, *, ^], output 4 3 3 1 ^.
• 2: output 4 3 3 1 ^ 2.
• /: pop ^, which binds tighter; the * has equal precedence and / is left-associative, so it stays. Push. Stack [+, *, /], output 4 3 3 1 ^ 2 ^.
• ): opens a group, push. Stack [+, *, /, )].
• 1: output 4 3 3 1 ^ 2 ^ 1.
• -: the ) stops the popping, push. Stack [+, *, /, ), -].
• 5: output 4 3 3 1 ^ 2 ^ 1 5.
• (: pop -, then discard the ). Stack [+, *, /], output 4 3 3 1 ^ 2 ^ 1 5 -.
• -: pop / and *, which bind tighter; the + is equal and stays. Push. Stack [+, -], output 4 3 3 1 ^ 2 ^ 1 5 - / *.
• 6: output 4 3 3 1 ^ 2 ^ 1 5 - / * 6.
• End: pop - and +, output 4 3 3 1 ^ 2 ^ 1 5 - / * 6 - +.
• Reverse the output.

The prefix form is + - 6 * / - 5 1 ^ 2 ^ 1 3 3 4, again after 8 pushes, 8 pops and 9 comparisons.

Evaluating the prefix form

Reading + - 6 * / - 5 1 ^ 2 ^ 1 3 3 4 from the right, the first value popped is the left operand:

• 4: push, stack [4].
• 3: push, stack [4, 3].
• 3: push, stack [4, 3, 3].
• 1: push, stack [4, 3, 3, 1].
• ^: pop 1, then 3, push 1 ^ 3 = 1. Stack [4, 3, 1].
• 2: push, stack [4, 3, 1, 2].
• ^: pop 2, then 1, push 2 ^ 1 = 2. Stack [4, 3, 2].
• 1: push, stack [4, 3, 2, 1].
• 5: push, stack [4, 3, 2, 1, 5].
• -: pop 5, then 1, push 5 − 1 = 4. Stack [4, 3, 2, 4].
• /: pop 4, then 2, push 4 / 2 = 2. Stack [4, 3, 2].
• *: pop 2, then 3, push 2 · 3 = 6. Stack [4, 6].
• 6: push, stack [4, 6, 6].
• -: pop 6, then 6, push 6 − 6 = 0. Stack [4, 0].
• +: pop 0, then 4, push 0 + 4 = 4. Stack [4].

The value is 4 again.

The tree and the call stack

Building the tree from the postfix form pushes 15 subtrees, and the last one is the whole expression; reading it back in order gives 6 - (5 - 1) / 2 ^ 1 ^ 3 * 3 + 4, with the parentheses restored exactly where they are needed. The tree has height 6. The recursive evaluator makes 15 calls and is at most 7 frames deep, and the explicit stack of evaluate_iterative also peaks at 7 frames: [+, - has 6, *, / has 4, ^ has 2, ^, 1].

Next greater element

For the values 5, 2, 8, 3, 1, 4, 9, 6 the stack of waiting values, written as values rather than indices, evolves as:

• 5: push, [5].
• 2: 5 is not smaller, push, [5, 2].
• 8: pop 2 and 5, whose next greater element is 8; push, [8].
• 3: push, [8, 3].
• 1: push, [8, 3, 1].
• 4: pop 1 and 3, answered by 4; 8 stays; push, [8, 4].
• 9: pop 4 and 8, answered by 9; push, [9].
• 6: push, [9, 6].

The answers are 8, 8, 9, 4, 4, 9 and none for 9 and 6, which are left on the stack, after 8 pushes, 6 pops and 11 comparisons.

The code

The package stacks is plain Python, one idea per module. Importing it needs only the standard library; Matplotlib is imported by plotting.py alone.

• adt.py holds the Stack protocol, StackUnderflow and StackOverflow, and operations written against the contract alone: bottom_to_top, reversed_by_stack and drain.
• array_stack.py holds ArrayStack on a Python list and BoundedStack with its top index; growable.py holds GrowableStack with its three growth rules and the predicted copy counts; linked_stack.py holds LinkedStack and its Node.
• brackets.py holds check_brackets, which returns a BracketReport, matching_pairs, the slow reference balanced_by_reduction and the generators of random balanced and corrupted texts.
• tokens.py holds the operator table, Token, tokenize, which decides when a minus is unary, and ExpressionError with the index of every error.
• shunting_yard.py holds infix_to_postfix and the pop rule; prefix.py holds infix_to_prefix with the mirrored rule.
• arithmetic.py holds the four number modes, the operators and functions applied to values and EvaluationError; evaluation.py holds evaluate_postfix, evaluate_prefix and evaluate.
• expression_tree.py holds ExprNode, the trees built from postfix and prefix with a stack of subtrees, iterative traversals and postfix_to_infix with minimal parentheses.
• call_stack.py holds the recursive and iterative evaluators of a tree, DepthMeter and the Towers of Hanoi both ways.
• min_stack.py holds MinStack and LeanMinStack; monotonic.py holds next_greater, stock_span and largest_rectangle with their quadratic counterparts.
• counting.py holds OperationCounter, whose fields are pushes, pops, peeks, comparisons and copies, and CountedKey; trace.py holds the Step record, format_trace and rows, which turns a trace into the token-by-token tables printed above.
• invariants.py holds stack_violation, is_stack and check_stack for every stack in the package, monotonic_violation and postfix_violation, the rank condition.
• workloads.py holds the worked example's inputs, random operation sequences that grow and drain the stack, random values and random expressions.
• drawing.py returns deterministic Graphviz text with every node pinned to a computed position, for stack states standing upright, single, before and after, or in a grid; strip_drawing.py draws a whole run of an algorithm as columns of upright stacks; tree_drawing.py draws the linked stack and the expression tree, which layout.py places with a tidy tree layout that keeps every left operand on the left.
• comparisons.py runs the same operations on a list, a deque and a LifoQueue, and reads expressions with Python's ast module and its bytecode; pitfalls.py holds deliberately broken versions for the pitfalls below; plotting.py draws every figure in the handbook's colours.

Counting and tracing never change what the code does. The heart of the shunting-yard algorithm is the loop that applies the pop rule:

incoming = token.operator
while stack and stack[-1].kind == "operator":
    counter.comparisons += 1
    top = stack[-1].operator
    if not pops_before(top, incoming):
        break
    pop_to_output(position, pop_reason(top, incoming))
push(token, position, stay_reason(stack[-1] if stack else None, incoming))

The examples run in a few seconds each from the repository root:

• examples/worked_example.py prints every step of the worked example and writes the six generated diagram sources.
• examples/stack_implementations.py runs every stack against a list, a deque and a LifoQueue, counts the copies of the three growth rules, compares them with CPython's own list and times the stacks roughly.
• examples/expression_conversions.py converts in every direction, checks thousands of random expressions against Python's ast module and exact fractions, and counts the stack operations.
• examples/recursion_and_explicit_stacks.py evaluates ever deeper expressions recursively and with an explicit stack, and solves the Towers of Hanoi both ways.
• examples/monotonic_stacks.py traces the stock span and the largest rectangle, runs the min-stacks and counts the comparisons against the quadratic scans.
• examples/common_mistakes.py runs every broken version from pitfalls.py next to the correct code.
• examples/practice.py prints fresh exercises with their solutions; --seed gives a new set.

python linear-structures/stacks/examples/worked_example.py
python linear-structures/stacks/examples/stack_implementations.py
python linear-structures/stacks/examples/expression_conversions.py
python linear-structures/stacks/examples/recursion_and_explicit_stacks.py
python linear-structures/stacks/examples/monotonic_stacks.py
python linear-structures/stacks/examples/common_mistakes.py
python linear-structures/stacks/examples/practice.py --seed 7

The sample project, project/calculator.py with its helpers project/language.py and project/fuzzing.py, is a calculator for arithmetic with variables and functions, built from the package's tokenizer, shunting-yard parser and postfix evaluator. A line is an expression or an assignment statement such as rate = 3 / 8; the value of the last expression is kept as ans, vars lists the variables, and every error comes back as a message with a caret under the place it was found. Exact mode computes with fractions and offers abs, min and max; float mode adds sqrt, exp, ln, sin and cos. The default run works through a short demonstration script, then checks 20000 random expressions with variables and functions against references that share no code with the calculator: Python's ast module parses each one, and a separate walk over that tree computes the value exactly with fractions. It also corrupts 20000 operator-only expressions, deleting, repeating or swapping tokens, and checks that the calculator rejects exactly the lines Python's parser rejects. --interactive reads lines from the keyboard, --batch FILE runs a file, --mode chooses the arithmetic, --fuzz and --seed change the check, and --figures writes the PNG elsewhere; the default run takes a few seconds.

python linear-structures/stacks/project/calculator.py
python linear-structures/stacks/project/calculator.py --interactive --mode float

All 20000 values agree, 19763 of them as numbers and 237 as a division by zero reported by both, and all 20000 corrupted lines are accepted or rejected exactly as Python's parser does, 16250 of them rejected. The project also measures the peak sizes of both stacks:

Over the random expressions the operator stack never held more than 18 entries and the value stack more than 11, while the nested expression of 641 tokens needed 320 and 161: the space a stack algorithm needs is set by the nesting, not by the length.

The notebook stacks.ipynb follows this page: the implementations and their growth, the bracket checker, every conversion and evaluation of the worked example, the call stack, the monotonic stacks, the comparison with Python's own tools and a short session with the calculator. The tests in tests check the worked example value by value, the invariants after thousands of random operations, the cost bounds on counts and the agreement with the built-in stacks, Python's ast module and exact fractions, and run in a few seconds:

python -m pytest linear-structures/stacks

All data are synthetic, generated from seeds by workloads.py, brackets.py and project/fuzzing.py, so nothing is downloaded and no licence is involved.

In practice

Python's list, deque and LifoQueue

In Python a stack is a list: append pushes, pop pops and items[-1] peeks, with an IndexError on an empty list. collections.deque works the same way with append and pop, and the package's stacks behave identically. The example stack_implementations.py runs one sequence of 20000 random operations, 17 of them on an empty stack, on every stack in the package, on a list, on a deque and on a queue.LifoQueue, and all of them return the same results:

import collections

from stacks import LinkedStack, random_operations, run_on_list, run_on_stack

operations = random_operations(20000, seed=4)
expected = run_on_list(operations)
assert run_on_list(operations, collections.deque) == expected
assert run_on_stack(LinkedStack(), operations) == expected

In wall-clock time the pure-Python ArrayStack takes three to four times as long as the bare list and LinkedStack about ten times, while a deque is about as fast as a list for pushes and pops at its end, often slightly faster; the ratios vary from run to run and machine to machine. When to use which:

• Use a list for a stack in Python. It is the fastest and the most compact, and its occasional resize is amortized away.
• Use collections.deque when the same structure also needs O(1) operations at the other end, as a queue or a double-ended queue does; it never copies all its items at once, because it grows in fixed-size blocks.
• Use queue.LifoQueue only to pass work between threads; it is a list behind a lock, with blocking put and get and no peek.
• Write a bounded stack when the capacity is part of the problem, such as a fixed buffer or an undo history that keeps only the last hundred steps; in that case the oldest item usually falls off the bottom, which is a deque with a maxlen.
• Never use list.insert(0, x) and list.pop(0) as push and pop: both shift every item.

Python's own parser and the ast module

Python does not parse with the shunting-yard algorithm. Since version 3.9 CPython uses a PEG parser generated from a grammar in which every precedence level is its own rule, and it builds an abstract syntax tree, available through the ast module. Its precedences agree with this page: ** is right-associative and binds tighter than a unary minus on its left, so -2 ** 2 is −4. The package's ast_postfix reads an expression with ast.parse, after writing ^ as **, and walks the tree in postorder; on thousands of random expressions it gives exactly the postfix the shunting-yard algorithm gives, and ast_value evaluates the same tree exactly with fractions. Neither uses eval, and nothing here should: eval runs arbitrary code, and in Python 2 ^ 3 is the exclusive or of the bits, 1, not 8.

CPython's parser is itself recursive, and its tokenizer refuses more than 200 nested parentheses with "too many nested parentheses". The package's parser and evaluator use explicit stacks and handle a nesting of 5000 levels without complaint, which recursion_and_explicit_stacks.py shows.

Postfix inside the interpreter

The CPython interpreter is a stack machine: its bytecode pushes operands onto a value stack and applies operators to the top items. Compiling an expression therefore produces it in postfix order. bytecode_postfix disassembles an expression with the dis module: for a - b * c ^ d it finds the loads of a, b, c and d followed by the operators ^, * and -, the same as infix_to_postfix. The Java virtual machine, the .NET runtime and WebAssembly are stack machines too, and PostScript and Forth are programming languages written directly in postfix, as are the keystrokes of calculators that use reverse Polish notation.

Elsewhere

Java's legacy java.util.Stack extends the synchronized Vector, and its documentation recommends the Deque interface, usually ArrayDeque, instead. C++'s std::stack is an adaptor over another container, a std::deque by default, with push, pop and top, where pop returns nothing. Rust uses Vec::push and Vec::pop, which returns an Option, and Go uses a slice with append and reslicing. Beyond expressions, stacks run the undo history of every editor, the back button of a browser (two stacks, one for back and one for forward), depth-first search and backtracking, the matching of tags in HTML and XML parsers, and the operator precedence parsers inside many compilers and query engines.

Pitfalls

• Mixing the two conventions for the top index. If top is the index of the top item, empty is −1; testing for empty with top == 0 strands the last item, as common_mistakes.py shows with three items of which only two come out. Pick one convention, top item or next free slot, and use it in every test.
• Forgetting what an overflow leaves behind. A push that overflows changes nothing, so the next pop returns the last item that did get in, not the one that was refused. In the worked example the pop after the failed push 64 returns 11.
• Popping or peeking without checking for an empty stack. On a Python list pop() and [-1] raise IndexError; a bracket checker that pops blindly crashes on a) instead of reporting a closer with nothing open.
• Comparing the popped opener with the closer itself. A ( is never equal to a ), so such a checker rejects every text that contains a bracket pair. Compare the opener with the partner of the closer.
• Forgetting the final test that the stack is empty, which accepts ((, or counting depth instead of keeping a stack, which accepts the crossed pairs of ([)] when there are several kinds of brackets.
• Using the wrong pop rule. Popping only strictly higher precedence makes left-associative operators group from the right: 8 - 3 - 2 becomes 8 3 2 - -, worth 7 instead of 3. Popping equal precedence for ^ makes it left-associative: 2 ^ 1 ^ 3 becomes 2 1 ^ 3 ^, worth 8 instead of 2. When tracing by hand, write the precedence and the associativity of the incoming operator before deciding.
• Popping past a (, or forgetting to empty the operator stack at the end, which loses the waiting operators: 1 + 2 * 3 comes out as 1 2 3.
• Converting to prefix by reversal with the ordinary postfix rule. Reversing the expression mirrors associativity too, so the conversion must use the mirrored rule; otherwise 8 - 3 - 2 gives - 8 - 3 2, which is 7.
• Taking the operands in the wrong order. In postfix the first value popped is the right operand, so 8 3 - is 5, not −5; in prefix, read from the right, the first value popped is the left operand. Subtraction, division and exponentiation expose the mistake, addition and multiplication hide it.
• Treating every minus as binary. Then -3 + 4 and 2 * -3 are syntax errors; decide by context, and give unary minus its own precedence, between multiplication and exponentiation, so that -2 ^ 2 is −4.
• Assuming integer division rounds the same way everywhere. Python's // rounds down, so −7 // 2 is −4, while C and Java round towards zero and give −3. Say which one a trace uses, or compute exactly with fractions.
• Calling eval on an expression. It executes arbitrary code, and its syntax is Python's, where ^ is exclusive or. Parse with the algorithm on this page, or with ast.parse and a walk over the tree.
• Recursing on input that can be deep. A tree built from 2000 nested parentheses needs 2001 frames, more than Python's default limit of about a thousand; raising the limit with sys.setrecursionlimit trades a clean RecursionError for a possible crash of the interpreter. Use an explicit stack, as evaluate_iterative does.
• Keeping only strictly smaller items in a lean min-stack. With 5, 3 and 3 pushed, popping one 3 also removes the only 3 from the second stack and the minimum wrongly becomes 5.
• Getting the strictness of a monotonic stack wrong. The stock span counts days with a price at most today's, so equal prices must be popped: popping only strictly lower prices gives spans 1, 1, 2, 4 instead of 1, 1, 3, 4 for prices 30, 20, 30, 40. The next greater element needs a strictly greater value, so equal values must stay: popping them reports 7 as greater than 7.

Further reading

• K. Samelson and F. L. Bauer, "Sequential formula translation", Communications of the ACM 3(2), 76-83, 1960. The stack principle for translating and evaluating formulas.
• E. W. Dijkstra, "Algol 60 translation: an Algol 60 translator for the X1 and making a translator for Algol 60", report MR 35/61, Mathematisch Centrum, Amsterdam, 1961. The shunting-yard algorithm.
• C. L. Hamblin, "Translation to and from Polish notation", The Computer Journal 5(3), 210-213, 1962. Reverse Polish notation and its evaluation with a stack.
• D. E. Knuth, The Art of Computer Programming, volume 1, Fundamental Algorithms, third edition, section 2.2.1, Addison-Wesley, 1997. Stacks, queues and deques, with their history.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, fourth edition, chapters 10 and 16, MIT Press, 2022. Array stacks and the amortized analysis of growing tables with the potential method.
• R. Sedgewick and K. Wayne, Algorithms, fourth edition, section 1.3, Addison-Wesley, 2011. Resizing-array and linked stacks, and Dijkstra's two-stack evaluation of expressions.
• A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman, Compilers: Principles, Techniques, and Tools, second edition, chapter 4, Addison-Wesley, 2006. Operator precedence and the grammars behind parsers.
• O. Berkman, B. Schieber and U. Vishkin, "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms 14(3), 344-370, 1993. The all nearest smaller values problem that monotonic stacks solve.
• The Python documentation: "Using lists as stacks" in the tutorial, and the collections, queue, ast and dis modules.