Chapter 3: Stack
In the middle of the 1950s, a small group of mathematicians in Munich was trying to teach a machine to do something you do without thinking. Friedrich L. Bauer and Klaus Samelson wanted a computer to read an ordinary arithmetic expression — brackets, plus signs, multiplication signs and all — and work out its value correctly, in the order a human would.
The difficulty was not the arithmetic. It was the waiting. When you read an expression such as one bracket opening inside another, you meet operations you cannot perform yet, because their operands have not arrived. You hold them in your head, finish the inner work first, and then come back to them — and you always come back to the most recent one you set aside, never to the oldest.
Bauer and Samelson gave the machine a store built on exactly that rule. They called it a Keller — a cellar. Whatever went in last came out first, and nothing in the middle could be reached at all. It sounds like a crippling restriction. It turned out to be the reason the method worked: the cellar remembered postponed work in precisely the order the work had to be resumed.
That store is what this chapter calls a stack. You will meet it as a pile of plates, as a browser’s back button, and finally as the machine that unpicks an arithmetic expression.
Fig. 3.0 – A physical stack of plates and its software equivalent.
This chapter answers all five of these questions. Read it with them in mind, and check yourself against them when you reach the end.
3.1 Data Structures and Why They Matter
In Class XI you stored a student’s name in a string, a list of marks in a list, a fixed pair of coordinates in a tuple, a collection of distinct roll numbers in a set. Each time, you chose the type that suited the data. That choice was never only about what the values were — it was about what you intended to do with them.
Consider a simple example. A class teacher keeps the marks of forty students. If the marks sit in a list, finding the fifth student’s mark is instant, because a list is numbered and you can go straight to position 4. If the same forty marks sit in a set, that question cannot even be asked, because a set does not keep its elements in any position at all. The data is identical. The organisation is not, and the organisation decides which operations are possible and which are cheap.
That is the whole idea behind a data structure.
Data, organisation, operations
A data structure is not merely a heap of values. It is values plus an arrangement plus the set of operations that arrangement supports efficiently. A string is a data structure whose elements are characters kept in order, so slicing and reversing come naturally. A list is a data structure whose elements may be of different types, kept in order and reachable by index, so appending, removing and sorting come naturally.
You can see the arrangement at work in a short piece of code you already know.
marks = [72, 65, 88]
marks.append(91)
marks.insert(1, 54)
print(marks)
print(len(marks))The output is:
[72, 54, 65, 88, 91]
5Notice what the list permitted. append() added at the end; insert() pushed a value into the middle and shifted the rest along. A list is willing to be changed anywhere, and that willingness is a property of how it is organised, not of the numbers inside it.
3.1.1 What a Data Structure Organises
Grouping data has two purposes, and it is worth separating them.
The first is storage. Forty marks kept in forty separate variables named mark1, mark2 and so on are forty unrelated names; the program cannot loop over them, cannot count them, and cannot pass them anywhere as one thing. Grouped into a single list, they become one object with a size, and every loop you write for one of them works for all of them.
The second is access. Once the elements are grouped in a definite arrangement, that arrangement fixes how quickly you can reach a particular element. In a list, position 30 is reached directly. In a pile of forty sheets of paper lying on a table, the thirtieth sheet is reached only by lifting twenty-nine sheets off it first.
That last point is the doorway to this chapter. You are about to meet a structure whose usefulness comes from what it forbids.
3.1.2 Linear and Non-Linear Arrangements
Data structures are classified by the shape of the arrangement they impose. Two broad shapes cover almost everything you will meet.
In a linear data structure, the elements are arranged one after another in a sequence. Each element has exactly one element before it and one after it, except for the two at the ends. A string is linear; so is a list; so is a tuple. You can walk through such a structure from one end to the other and be certain of visiting every element exactly once, in a definite order.
In a non-linear data structure, the elements are not laid out in a single sequence. An element may be connected to several others at once, and there is no single “next”. A family tree is non-linear: one person may have three children, so “the element after this one” has no unique answer. A map of cities joined by roads is non-linear for the same reason.
The difference is visible the moment you draw the two, as in Fig. 3.1.
Fig. 3.1 – Linear vs non-linear data structures.
Computer science uses many structures beyond the ones Python gives you as built-in types: arrays, linked lists, binary trees, heaps, graphs and sparse matrices are all standard, and each exists because some family of problems is awkward without it.
Two of these, stack and queue, are the ones this course cares about, and neither is available in Python as a ready-made type. That is not a gap to be apologised for. A stack and a queue are defined by their behaviour — by the rule governing where elements may enter and leave — and any structure that can obey that rule can serve as one. You will see in section 3.4 that an ordinary Python list, used with discipline, obeys the stack rule perfectly.
3.2 Stack
Walk into a school canteen and look at the trays kept near the counter. They are piled one on top of another. When a fresh tray is washed and returned, the attendant does not lift the pile and slide it in halfway down — the tray goes on top. When you take one, you take the top tray. Nobody has written a rule on the wall. The arrangement itself makes any other action absurdly inconvenient.
The same arrangement turns up wherever things are piled: files stacked on an office desk, chairs stacked in a hall after a function, bangles slipped onto a wrist. In every case, the item that went in most recently is the one sitting where your hand naturally reaches, and the item that went in first is buried at the bottom.
A stack is that arrangement, made precise and used deliberately in a program.
Read the definition carefully, because the important word in it is only. A list allows you to insert at position 1 and delete from position 3; a stack does not. Section 3.1 said that a structure is defined as much by what it forbids as by what it allows, and the stack is the clearest illustration of that claim in this course.
Fig. 3.2 – A stack showing insertion and deletion restricted to the top.
Fig. 3.2 shows a stack holding four elements. Only the box at the open end can be touched. The element 6 sits directly below 39, but there is no operation in the stack’s vocabulary that reaches it — not to read it, not to remove it, not to replace it. To get at 6, the elements above it must be removed first, one at a time.
3.2.1 The Last-In-First-Out Principle
Because both insertion and deletion happen at the same end, the order in which elements leave a stack is completely determined by the order in which they entered — and it is the reverse of that order. The element inserted most recently is the element removed first. The element inserted first is removed last.
This rule has a name: the last-in-first-out (LIFO) principle.
Suppose the trays numbered 11, 24, 6 and 39 were placed on the pile in that order. If you now remove trays one after another, they come off as 39, then 6, then 24, then 11. The pile has reversed the sequence without being asked to, simply by obeying its own rule.
3.2.2 Top of the Stack
The end at which insertion and deletion take place is called the top of the stack. The other end, at which the oldest element sits, is the bottom.
Two points about the top are worth fixing now, because both cause confusion later.
First, the top is a position, not a value. It marks where the next insertion will land and which element the next deletion will take away. As elements are added, the top moves outward; as elements are removed, it moves back in.
Second, an empty stack has no top element at all. This is not a technicality. Every operation that reads or removes the top element must first face the question of what to do when there is nothing there, and section 3.3 gives that situation its own name.
Fig. 3.3 – The top of a stack moves outward as elements are inserted.
3.2.3 Applications of Stack
A structure this restrictive would be a curiosity if it were not so widely needed. It is needed constantly.
Where you already meet stacks
Outside the computer, the arrangement appears in a pile of clothes in an almirah, in chairs stacked vertically, in bangles worn on the wrist, and in boxes of eatables piled on a kitchen shelf. In each of these, the last item placed is the first item available, and taking one from the middle means disturbing everything above it.
Where a program needs a stack
Inside a program, four uses of the stack are standard, and each of them is a case of the same idea: something must be dealt with in the reverse of the order in which it arrived.
Reversing a sequence. To print a word backwards, the characters must be produced in the reverse of their reading order. Put every character into a stack as you read the word from left to right, then take them out one by one; LIFO does the reversing for you, and no index arithmetic is needed.
Undo in an editor. When you type, delete, paste and format in a text or image editor, each change is recorded. Pressing undo reverses the most recent change first, then the one before it. The editor keeps the record of changes in a stack, which is why undo always works backwards through your session and never jumps to the middle of it.
The back button of a browser. As you move from one page to the next by following links, each page you leave is remembered. Clicking BACK returns you to the most recently left page, clicking it again returns you to the one before that. The browsing history is maintained as a stack.
Matching parentheses in an expression. When a program contains an expression such as one written with brackets inside brackets, the compiler must check that every opening bracket has a matching closing bracket and that the pairs are properly nested. The natural method is to push each opening bracket onto a stack and, on meeting a closing bracket, remove the most recent opening bracket and check that the two match. If a closing bracket arrives when the stack is empty, or if the stack is not empty when the expression ends, the brackets are mismatched and the compiler reports an error.
The same principle reaches deeper into the machinery than these four examples suggest. When a function calls another function, which calls a third, the system must remember where to return to when each one finishes — and it must return in the reverse of the order of calling. That record of pending returns is held in a stack, which is why a chain of function calls can be unwound reliably no matter how deep it goes.
3.3 Operations on Stack
Section 3.2 fixed the arrangement: elements enter and leave at the top, and nowhere else. That description is still only a picture. To use a stack in a program you need the arrangement expressed as operations — named actions, each with a stated effect and a stated behaviour in the awkward cases.
Two operations are fundamental, and everything else a stack does is built on them. Inserting an element at the top is called PUSH. Removing the element at the top is called POP. Both are written in capitals when the operation itself is meant, to keep them distinct from the Python methods you will use to implement them in section 3.4.
3.3.1 PUSH Operation
PUSH is the insertion operation. It takes one element, places it at the top of the stack, and the element it places becomes the new top. Nothing else in the stack moves, and no existing element is disturbed.
Consider a stack that is empty, and push the token numbers 15, 27 and 8 in that order. After the first PUSH the stack holds 15, which is both the top and the bottom. After the second, 27 sits above 15 and is the top. After the third, 8 sits above 27. The element 15 has not moved and has not changed, but it is now buried under two others.
Fig. 3.4 – Trace of PUSH operations on a stack.
The method itself is short, but stating it in words before writing any code is the habit worth forming.
3.3.2 POP Operation
POP is the deletion operation. It removes the element currently at the top, and the element immediately below it becomes the new top. POP does more than delete: it also returns the removed element, so the program can use the value it has just taken out. That returned value is what makes a stack usable — you do not merely discard the top item, you receive it.
Continue with the stack holding 15, 27 and 8, with 8 on top. A POP removes 8 and hands it back; the stack is left holding 15 and 27, with 27 on top. A second POP removes 27 and hands it back. Notice that 8 and 27 come out in the reverse of the order in which they went in, which is the LIFO principle doing its work.
A sequence of operations, step by step
The clearest way to see PUSH and POP together is to follow a run of them and record the state of the stack after each one. Table 3.3 traces the operations PUSH 15, PUSH 27, PUSH 8, POP, PUSH 42, POP, POP on a stack that starts empty. The stack contents are written bottom-to-top, so the rightmost value in each row is the top element.
Read the last three rows together. The element 42 entered after 27 and left before it; the element 15, which entered first, is still sitting at the bottom untouched. Seven operations have been performed and 15 has never once been reachable.
3.3.3 Overflow and Underflow
Both fundamental operations have a case in which they cannot do what they were asked to do, and each case has a name.
A stack is full when no more elements can be added to it. Attempting a PUSH on a full stack is an error condition called overflow — there is a new element, but there is no room for it.
A stack is empty when it holds no elements at all. Attempting a POP on an empty stack is an error condition called underflow — there is a request for an element, but there is nothing to give.
These two are easy to confuse because both are “the stack cannot cope” situations. They are opposites, and Table 3.4 keeps them apart.
The two conditions are not equally likely to trouble you, and the reason is worth stating plainly. Overflow depends entirely on how the stack has been built. A stack laid out inside a fixed block of memory — a block of fifty positions, say — is genuinely full at fifty elements, and its PUSH must test for that. A stack built on a structure that grows on demand has no such fixed ceiling, and its PUSH has nothing to test.
Underflow, by contrast, is unavoidable in every implementation. Emptiness is not a limitation of the storage; it is a fact about the data. Any stack, however it is built, will be empty when everything put into it has been taken out, and any program that pops without checking will fail there. This is why the empty test in the POP algorithm was described as compulsory while the full test was described as conditional.
3.4 Implementation of Stack in Python
Sections 3.2 and 3.3 described a stack without writing a single line of Python. That was deliberate. A stack is a rule about behaviour, and the rule can be stated completely before any decision is taken about how to store the elements. Only now does the storage question arise: given that Python offers no data type called “stack”, what do you actually keep the elements in?
The answer is a list — used with discipline.
3.4.1 Why a List Serves as a Stack
A Python list is a linear, ordered, mutable collection. Its elements sit in a definite sequence, they can be reached by index, and the list can grow or shrink while the program runs. Three of those properties are exactly what a stack needs.
Look at what a list already gives you. append() adds an element at the rightmost end. pop(), called with no argument, removes and returns the element at the rightmost end. Those two methods, and only those two, are the whole of PUSH and POP — provided you agree that the rightmost end of the list is the top of the stack.
That agreement is the discipline. Nothing in Python stops you from writing book_stack.insert(0, "X") or reading book_stack[1]; the list will oblige. What makes the list a stack is your refusal to do so.
Fig. 3.5 – A Python list functioning as a stack.
Fig. 3.5 shows why the rightmost end is chosen rather than the leftmost. Adding or removing at the right disturbs nothing: every other element keeps the index it already had. Adding or removing at the left would force every remaining element to shift by one position, which costs time and gains nothing.
There is a second reward for choosing the right-hand end. The top element of the stack is always the last element of the list, and a list always knows its own length. The position of the top is therefore never in doubt and never has to be stored — len(stack) - 1 gives it, and the index -1 gives it more directly still. In an implementation built inside a fixed block of memory, a separate variable holding the index of the top is essential; here it would be an extra thing to keep correct, and one more thing to get wrong.
3.4.2 Creating an Empty Stack
A stack that has just been created holds nothing, so it is created as an empty list:
book_stack = []The form book_stack = list() does the same thing and you will meet it in other books. Either is correct; this book uses [] throughout.
The example carried through this section is a small library counter. Books returned by students are placed on a pile at the counter, each identified by its accession code, and the attendant works from the top of the pile. Every function below takes the stack as a parameter, so the same functions would work equally well for a pile of trays or a browsing history — the code does not care what the elements mean.
3.4.3 Testing Whether the Stack is Empty
Section 3.3 established that a POP must never be attempted on an empty stack. That test will be needed in more than one place, so it is worth writing once as a function.
In Python:
def is_empty(stack):
return len(stack) == 0The comparison len(stack) == 0 is itself either True or False, so it can be returned directly; an if statement that returns True in one branch and False in the other would do the same work in five lines instead of one.
3.4.4 Implementing PUSH
PUSH takes two things: the stack to insert into, and the element to insert. Both become parameters.
def push_item(stack, item):
stack.append(item)The function returns nothing, and it does not need to. Lists are mutable, so the list that the caller passed in is the very list the function modifies — not a copy of it. After the call, the caller’s stack has the new element on top.
Notice what the PUSH algorithm of section 3.3 required and this function does not have: a test for fullness. A Python list grows as elements are added, and it goes on growing for as long as the computer has memory to give it. There is no fixed capacity to reach, so the overflow condition described in section 3.3.3 does not arise in this implementation. Underflow does, which is why the next function has a test and this one does not.
3.4.5 Implementing POP
POP has more to do than PUSH. It must check for underflow, remove the top element, and hand that element back to the caller.
def pop_item(stack):
if is_empty(stack):
print("Underflow: the stack is empty")
return None
return stack.pop()Three decisions in that function are worth spelling out.
First, the emptiness test comes before anything else. If it were placed after the pop(), it would be too late to be of any use.
Second, when the stack is empty the function returns None. Something must be returned, because the caller wrote value = pop_item(book_stack) and is waiting for a value. None is Python’s way of saying “no value at all”, and the caller can test for it.
Third, stack.pop() is called with no argument. Called with an argument, as in stack.pop(0), the method removes the element at that index instead — which is a perfectly good list operation and a completely wrong stack operation.
You can see underflow handled by running the function on an empty list. Assuming is_empty and pop_item have been defined as above:
empty_stack = []
value = pop_item(empty_stack)
print("Returned value:", value)The output is:
Underflow: the stack is empty
Returned value: NoneThe program does not crash, and the caller is left holding a value it can recognise as meaning “nothing was there”.
3.4.6 Reading the Top Element and the Size
Two supporting operations complete the set. One reports how many elements the stack holds; the other reads the top element without removing it.
def stack_size(stack):
return len(stack)
def top_item(stack):
if is_empty(stack):
print("The stack is empty")
return None
return stack[-1]stack[-1] is the last element of the list, and therefore the top of the stack. The same element could be reached by computing stack[len(stack) - 1], and the two are exactly equivalent; the negative index simply says the same thing without arithmetic.
The distinction between top_item() and pop_item() is one students routinely blur, so state it precisely: top_item() reads the top and leaves the stack unchanged, while pop_item() removes the top and shortens the stack by one. Calling top_item() twice in a row gives the same answer twice. Calling pop_item() twice in a row gives two different elements.
3.4.7 Displaying the Contents of the Stack
While developing and testing, it helps to see the whole stack. Since the top element is the one that matters most, the contents are printed from top to bottom — which means walking the list backwards.
def display_stack(stack):
if is_empty(stack):
print("The stack is empty")
return
print("Stack contents from top to bottom:")
for i in range(len(stack) - 1, -1, -1):
print(stack[i])The three arguments of range() are the start, the stop and the step. Starting at len(stack) - 1 begins at the last index; stopping at -1 means the loop stops just before index -1, so index 0 is the final value used; the step -1 counts downwards. Getting the middle argument wrong is the usual slip — writing range(len(stack) - 1, 0, -1) would stop one element early and never print the bottom of the stack.
3.4.8 Putting the Operations Together
The six functions can now be collected into one program, together with the statements that exercise them. The program below is complete: it can be keyed in and run as it stands, and it needs no input file and no user input.
3.5 Notations for Arithmetic Expressions
Everything so far has been about the stack itself. The rest of the chapter is about the single problem for which the stack was invented, and to state that problem properly you need a little vocabulary about expressions.
An arithmetic expression is built from two kinds of thing. An operand is a value the expression works on — a number such as 7, or a variable such as a. An operator is a symbol for an operation performed on operands — +, -, *, / and so on. The operators used in this chapter are all binary, meaning each one takes exactly two operands.
The question this section answers is where the operator should be written in relation to its two operands. There are three possible answers, and all three are in real use.
3.5.1 Infix Notation
You have written expressions one way all your life: the operator goes between its two operands, as in a + b. This is infix notation, and it is the notation of ordinary arithmetic, of school algebra and of Python source code.
Infix is easy to read, but it is not self-explanatory, and the reason is worth dwelling on. Consider:
a + b * cWritten down, this string does not by itself say which operation happens first. Is a added to b and the result multiplied by c, or is b multiplied by c and the result added to a? The symbols are in a definite order, yet the meaning is not fixed by that order alone.
Infix copes with this by adding two extra rules that live outside the expression.
The first is operator precedence: an agreed ranking that says which operator acts first when two of them compete for the same operand. You know it as the BODMAS rule — brackets first, then orders, then division and multiplication, then addition and subtraction. Under that ranking, a + b * c means b * c is computed first.
The second is parentheses, which override the ranking when you want a different order. Writing
(p + q) * rforces the addition to happen first, because the brackets say so.
Fig. 3.6 – Order of evaluation in infix notation.
So an infix expression is not complete on its own. Reading it correctly needs the expression plus the precedence rules plus the bracketing conventions. A human carries those rules in their head without noticing. A program must be given them explicitly, and that is precisely the difficulty.
3.5.2 Prefix Notation
In the 1920s the Polish mathematician Jan Lukasiewicz proposed writing the operator before its two operands. The expression a + b becomes + a b. This arrangement is called prefix notation, or Polish notation after its inventor.
The point of the arrangement is not brevity. It is that the order of evaluation becomes part of the expression itself, so no precedence rule and no bracket is needed.
Take the two examples from section 3.5.1. In prefix, a + b * c is written:
+ a * b cReading it: the first operator + has two operands; the first is a, and the second is whatever * b c produces. The multiplication is inside the addition, so it must happen first — and that is visible from the writing, not from a rule.
The bracketed expression (p + q) * r is written:
* + p q rHere the outermost operator is *, and its first operand is + p q. The brackets have disappeared, because their whole job was to say which operation was outermost, and the notation now says that by itself.
A longer example makes the pattern clear. The expression (m - n) / (p + q) becomes:
/ - m n + p q3.5.3 Postfix Notation
Reverse the idea and you get the third notation: the operator is written after its two operands. The expression a + b becomes a b +. This is postfix notation, also called reverse Polish notation.
The same three expressions in postfix are:
a b c * +
p q + r *
m n - p q +Take the first one slowly, reading left to right. The operands a, b and c arrive first. Then * arrives; it takes the two operands immediately available to it, which are b and c. Then + arrives; its two operands are a and the result of the multiplication. Every operator, when it appears, finds its operands already computed and waiting — which is exactly the property that makes postfix expressions easy for a machine to evaluate, as section 3.7 will show.
Notice also what did not change. In all three notations the operands appear in the same left-to-right order: a, b, c in the first expression, p, q, r in the second. Only the operators move. Conversion between notations is therefore a matter of placing the operators correctly, never of shuffling the operands.
3.5.4 Comparing the Three Notations
Any arithmetic expression can be written in any of the three notations — infix, prefix and postfix — and the three forms are exactly equivalent in meaning. Table 3.7 sets them side by side.
Read the table across each row rather than down each column. The three entries in a row are three spellings of one expression, and all three produce the same value.
You can confirm that with numbers. The infix expression 5 + 3 * 2 has the value 11, since the multiplication is performed first. Its postfix form is 5 3 2 * + and its prefix form is + 5 * 3 2, and both evaluate to 11 as well — the notation changes, the arithmetic does not.
The last two rows explain why this chapter is not merely a tour of alternative spellings. Infix is what people write; postfix is what a machine can evaluate in a single pass with nothing more than a stack. The gap between the two has to be crossed by a program, and crossing it is the subject of section 3.6.
3.6 Conversion from Infix to Postfix Notation
Section 3.5 left the chapter with a gap. People write infix, because it is readable. Machines want postfix, because it can be evaluated in one scan. Something has to convert the first into the second, and that something is a program with a stack.
This section builds the conversion method by hand, in the order the method itself demands: first the difficulty, then the reasoning that resolves it, then the algorithm, then a complete worked trace.
3.6.1 Operator Precedence and the Need for a Stack
Try converting an infix expression the naive way — reading it from left to right and writing each symbol out as you meet it — and you will see the problem within a few characters.
Take p - q * r. Scanning left to right, you meet p, then -, then q, then *, then r. The operand p can be written to the output at once; every operand can, because operands appear in the same order in both notations. But - cannot be written yet. In postfix an operator is written after its operands, and at the moment - is met, its second operand has not even been read, let alone evaluated. Worse, when * turns up later it must be written out before -, even though - was met first, because multiplication ranks higher.
So the scan meets operators in one order and must output them in another — and the order in which they must be output is the reverse of the order in which they were postponed. The most recently postponed operator is the one that becomes ready first.
That last sentence is the LIFO principle, word for word. The operators are held on a stack.
The ranking that decides which operator outranks which is operator precedence, and for the operators used in this chapter it is short.
Two operators of the same precedence, such as * and /, are performed left to right — in q * r / s the multiplication happens first simply because it comes first. This matters more than it looks, and section 3.6.2 shows exactly where it enters the method.
Parentheses sit outside the ranking altogether. An opening parenthesis is pushed on the stack to mark a fresh start, and while it sits there it shields everything below it: no operator inside the brackets may cause an operator from outside the brackets to be output. The opening parenthesis is removed only when its matching closing parenthesis arrives.
3.6.2 The Conversion Method
Two things are maintained during the scan: a stack, which holds operators and opening parentheses, and a string, which is built up left to right and holds the postfix expression. Both start empty.
Each symbol of the infix expression is then examined once, and there are four kinds of symbol to deal with.
An operand is appended to the postfix string immediately. Operands never go on the stack and never wait.
An opening parenthesis is pushed on the stack, where it acts as a barrier.
A closing parenthesis causes operators to be popped and appended to the postfix string until the matching opening parenthesis is reached; that opening parenthesis is then popped and discarded. Neither parenthesis is ever written to the output — brackets do not exist in postfix.
An operator is the interesting case. Before it can be pushed, every operator already on the stack that must be performed earlier has to be popped and appended to the postfix string. An operator must be performed earlier if its precedence is higher than the incoming operator’s, and also if its precedence is equal, since operators of equal precedence are performed left to right and the one on the stack was met first. Popping stops at an opening parenthesis, which is never popped by an operator. Only then is the incoming operator pushed.
When the whole expression has been scanned, any operators still waiting on the stack are popped and appended in turn. Nothing is left pending.
3.6.3 Working Through a Conversion
Take the infix expression:
p - q * (r + s) / tIt has been chosen because it exercises every branch of the method: an operator that waits, a bracketed group, and a pair of operators of equal precedence.
The scan takes eleven symbols. Table 3.10 records, for each one, what the method does, what the stack holds afterwards, and what the postfix string has become. The stack is written bottom to top, so the rightmost entry is the top.
The converted expression is therefore:
p q r s + * t / -
Fig. 3.7 – Converting an infix expression to postfix notation.
Three moments in Table 3.10 deserve a second look.
At the symbol *, nothing was popped. The - already on the stack ranks lower, so it must be performed later than the multiplication; it stays where it is and waits.
At the symbol +, nothing was popped either, but for a different reason. There were operators on the stack, and * outranks + — yet a ( was sitting on top of them, and the barrier stopped the popping immediately. That is what preserves the brackets’ meaning: the + inside them cannot disturb the * outside them.
At the symbol /, the * was popped even though the two operators rank equally. This is the case that a careless “higher precedence only” test gets wrong. Since q * ... was written before ... / t, the multiplication must be performed first, so * must appear earlier in the postfix string — and popping on equality is what puts it there.
Finally, check the result against meaning rather than against the table. The infix expression says: multiply q by (r + s), divide that by t, and subtract the whole thing from p. In p q r s + * t / -, reading left to right, r s + produces the sum, q ... * multiplies it, ... t / divides, and the final - subtracts the result from p. The two agree.
3.7 Evaluation of Postfix Expression
Section 3.6 turned an infix expression into a postfix one. That was half the job. A postfix expression is a string of symbols, and a string of symbols is not a value — something must still read it and compute the number it stands for.
This is where the effort pays off. Evaluating an infix expression requires precedence rules, bracket handling and more than one pass over the symbols. Evaluating a postfix expression requires a single left-to-right scan and a stack, and nothing else. There are no precedence comparisons at all, because the conversion has already used them up.
As in section 3.6, every operator here is binary — it takes exactly two operands.
3.7.1 The Evaluation Method
Think about what a scan of a postfix expression actually meets. Operands arrive first, one after another, with no instruction about what to do with them. They must be kept somewhere until an operator turns up and claims them. When an operator does arrive, it claims the two operands that are most recently waiting — never older ones.
Once again the requirement is “give me the two most recent items”, and once again the stack supplies it.
So the method is short. Operands are pushed as they arrive. When an operator arrives, two elements are popped, the operator is applied to them, and the single result is pushed back — because that result is itself an operand as far as the rest of the expression is concerned. When the scan ends, the one element left on the stack is the value of the whole expression.
Notice how the roles have swapped since section 3.6. In conversion, operators were pushed and operands went straight to the output. In evaluation, operands are pushed and operators are never stored at all — each one is used the moment it is met.
The order of the two operands
One detail decides whether the method is correct or merely plausible, and it is the detail that catches most students.
Suppose the stack holds 4 and then 2, with 2 on top, and the operator - arrives. Two elements are popped. The first pop returns 2, the second returns 4. Which is the subtrahend?
Go back to the writing. In postfix, 4 2 - came from the infix 4 - 2, so the left operand is 4 and the right operand is 2. The left operand was pushed earlier and therefore sits deeper. The element popped first is the right operand, and the element popped second is the left one. The operator must be applied as second popped, operator, first popped.
For + and * the order makes no difference, which is precisely why the mistake goes unnoticed until a - or a / appears and quietly produces 2 - 4 in place of 4 - 2.
3.7.2 Working Through an Evaluation
Take the postfix expression:
9 4 2 - * 6 +It contains a subtraction, so it will show the operand order doing real work. Table 3.11 records the state of the stack after each of the seven symbols. The stack is written bottom to top, so the rightmost value is the top.
The value of the expression is \(24\).
Fig. 3.8 – Evaluating a postfix expression using a stack.
Two moments in the trace are worth re-reading.
At the symbol -, the pops returned 2 first and 4 second, and the computation performed was \(4 - 2\), not \(2 - 4\). Had the order been reversed, the stack would have held \(-2\) instead of \(2\), and every later step would have been wrong while looking perfectly orderly.
At the symbol *, the stack held only the two values 9 and 2 — the three original operands had already become two, because the subtraction consumed two and returned one. Each operator shortens the stack by exactly one element, which is why an expression with four operands and three operators finishes with a single value.
Now compare this with the infix expression the postfix came from, 9 * (4 - 2) + 6. Evaluating that directly means noticing the brackets, jumping ahead to the subtraction, coming back for the multiplication and only then adding — the scan does not proceed steadily from left to right. The postfix form was evaluated in one straight pass with no jumping and no rules about precedence, because the conversion had already settled every question of order.
3.8 Summary
A data structure is a way of storing and organising a collection of data elements together with the operations that can be efficiently performed on them. The arrangement, not the values, decides which operations are possible and which are cheap.
In a linear data structure the elements are arranged in a sequence, each with one predecessor and one successor except at the two ends. In a non-linear data structure an element may be connected to several others, so no single left-to-right order exists. String, list, tuple, stack and queue are linear; trees and graphs are not.
A stack is a linear data structure in which insertion and deletion are permitted at one end only, called the top of the stack. The other end is the bottom, and no element between the two can be reached.
Because both insertion and deletion happen at the same end, a stack follows the last-in-first-out (LIFO) principle: the element inserted most recently is the first one removed, and the element inserted first is removed last. LIFO order depends only on the order of entry, never on the values stored.
The top is a position, not a value. It moves outward as elements are inserted and inward as they are removed, and an empty stack has no top element at all.
Two operations are fundamental. PUSH inserts a new element at the top, which then becomes the top element, leaving all elements below it undisturbed. POP removes the top element and returns it, so the element below becomes the new top and the count of elements falls by one.
Attempting a PUSH on a stack that is full is the error condition called overflow. Attempting a POP on a stack that is empty is the error condition called underflow. They are opposites: overflow concerns space, underflow concerns contents.
Overflow depends on the implementation and arises only where the stack has a fixed capacity. Underflow arises in every implementation, because any stack becomes empty once everything put into it has been taken out. This is why an emptiness test before every POP is compulsory.
Reading the top element without removing it is a separate operation from POP. Reading leaves the stack unchanged; POP shortens it. The ability to look before removing is what lets a stack be used for making decisions rather than only for storage.
Python provides no stack data type, so a stack is implemented using a list, with the rightmost end of the list treated as the top. The list method
append()performs PUSH and the methodpop(), called with no argument, performs POP.The rightmost end is chosen because insertion and deletion there leave every other element’s index unchanged, whereas working at the left end would shift every remaining element by one position.
No separate variable for the top is needed in this implementation, because the top element is always the last element of the list and the list’s own length gives its position. The index
-1reaches it directly.A list built by
append()grows for as long as memory allows, so a stack implemented this way has no fixed capacity and does not meet the overflow condition. Underflow must still be handled, usually by testing for emptiness and returning a value that clearly means “nothing was there”.Using a list as a stack is a discipline, not a guarantee. Nothing in Python prevents insertion or deletion at another position, and removing from the wrong end breaks the LIFO order silently, without any error message.
An arithmetic expression is built from operands, which are the values worked on, and operators, which are the symbols for the operations. The operators in this chapter are binary, each taking two operands.
Any arithmetic expression can be written in three notations. In infix notation the operator is placed between its two operands, in prefix notation before them, and in postfix notation after them. Prefix is also called Polish notation and postfix is also called reverse Polish notation.
Infix is not self-explanatory. Reading it correctly requires operator precedence, which ranks multiplication and division above addition and subtraction, and parentheses, which override that ranking. Operators of equal precedence act from left to right.
Prefix and postfix need neither precedence rules nor parentheses, because the position of each operator already states when it acts. In all three notations the operands appear in the same order; only the operators move.
Converting infix to postfix uses a stack to hold operators and left parentheses, and a string that is built up as the postfix expression. Operands are appended to the string as soon as they are read and never go on the stack.
During conversion, an incoming operator first causes every stacked operator of higher or equal precedence to be popped and appended, and is then pushed. A left parenthesis is pushed as a barrier that stops such popping, and is removed only by its matching right parenthesis, both being discarded rather than written out. Any operators still on the stack at the end are popped and appended.
The equality case in that comparison is essential. Popping only on strictly higher precedence would place operators of equal rank in the wrong order and change the meaning of the expression.
Evaluating a postfix expression needs one left-to-right scan and a stack, with no precedence comparisons, because the conversion has already fixed the order of evaluation. Operands are pushed as they arrive, and operators are used the moment they are met rather than being stored.
On meeting an operator during evaluation, two elements are popped, the operator is applied and the single result is pushed back, since a completed sub-expression behaves like an operand. Each operator therefore shortens the stack by exactly one element.
The element popped first is the right operand and the element popped second is the left one. Reversing them leaves addition and multiplication looking correct while giving wrong answers for subtraction and division.
A valid postfix expression leaves exactly one element on the stack when the scan ends, and that element is the value of the expression. Anything else means the expression was not well formed.
Stacks are used wherever items must be dealt with in the reverse of the order in which they arrived: reversing a sequence, undoing edits in an editor, stepping back through browsing history, checking that parentheses are properly matched, and remembering where to return from a chain of function calls.
3.9 Key Terms
Access — the ability to reach a particular element of a collection, and the cost of doing so, which is decided by the way the collection is organised.
Data structure — a way of storing and organising a collection of data elements, together with the operations that can be efficiently performed on the collection and on its individual elements.
Empty stack — a stack that holds no element, and therefore has no top element; a POP attempted on it causes underflow.
Full stack — a stack to which no further element can be added; a PUSH attempted on it causes overflow.
Infix notation — a way of writing an arithmetic expression in which each binary operator is placed between its two operands.
LIFO — last-in-first-out; the principle followed by a stack, under which the element inserted most recently is the first one to be removed.
Linear data structure — a data structure in which the elements are organised in a sequence, each element having a unique predecessor and a unique successor except the first and the last.
Non-linear data structure — a data structure in which the elements are not arranged in a single sequence, so that an element may be connected to several others and no unique next element exists.
Operand — a value that an operator works on, such as a number or a variable in an arithmetic expression.
Operator — a symbol standing for an operation performed on operands; a binary operator takes exactly two of them.
Operator precedence — the agreed ranking that decides which operator acts first when two of them compete for the same operand, with multiplication and division ranking above addition and subtraction.
Overflow — the error condition that arises when a PUSH is attempted on a stack that is already full.
POP — the stack operation that removes the top element and returns it, so that the element below becomes the new top.
Postfix notation — a way of writing an arithmetic expression in which each binary operator is placed after its two operands; also called reverse Polish notation.
Prefix notation — a way of writing an arithmetic expression in which each binary operator is placed before its two operands; also called Polish notation.
PUSH — the stack operation that inserts a new element at the top, which then becomes the top element.
Stack — a linear data structure in which insertion and deletion are permitted at one end only, called the top.
Storage — the keeping of related data elements together as one object, so that the program can count them, loop over them and pass them around as a single thing.
Top — the end of a stack at which insertion and deletion take place, and the position of the element that would be removed by the next POP.
Underflow — the error condition that arises when a POP is attempted on a stack that is empty.
3.10 Points to Ponder
A stack is defined as much by what it refuses to do as by what it does. Can you name another structure — in computing or outside it — whose usefulness comes from a restriction rather than from a capability? What would be lost if the restriction were removed?
Python’s list will happily let you insert at position 0 or read the middle element, so nothing in the language enforces the stack rule. Is a structure that depends on the programmer’s discipline really a stack, or only a list being used politely? What would it take to make the rule impossible to break?
Underflow happens in every implementation of a stack, but overflow depends on how the stack was built. Does that make overflow a less important idea, or does it make it a more revealing one — something that tells you about the machine rather than about the data?
Infix notation needs precedence rules and brackets; postfix needs neither. If postfix is genuinely simpler, why has no one seriously proposed that people write arithmetic that way? What does the answer suggest about the difference between a notation that is easy to process and one that is easy to understand?
Converting an expression pushes operators and outputs operands; evaluating one pushes operands and never stores operators at all. The two methods use the same structure for opposite purposes. What does this suggest about whether a data structure “belongs” to the kind of data it holds?
A chain of function calls, a set of nested brackets and an undo history are all handled by a stack. Is that because the three problems are secretly the same problem, or because the stack is a general enough tool to fit many different ones? How would you tell the two explanations apart?
3.11 Objective Questions
- A stack is best described as a data structure in which [1 mark]
- elements are inserted at one end and removed from the other end
- elements are inserted and removed at the same end
- elements may be inserted or removed at any position
- elements are stored without any order at all
- Which list method, called with no argument, performs the POP operation on a stack implemented as a Python list? [1 mark]
remove()insert()pop()clear()
- The value of the postfix expression
6 2 3 * -is [1 mark]- 12
- 0
- 6
- -12
- Assertion (A): A stack implemented using a Python list does not run into the overflow condition. Reason (R): A Python list expands as elements are appended to it, and is limited only by the memory available to the program. [1 mark]
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true but R is false
- A is false but R is true
- Assertion (A): While an infix expression is being converted to postfix, a left parenthesis on the stack is never popped by an incoming operator. Reason (R): Parentheses are appended to the postfix string so that the order of evaluation is preserved. [1 mark]
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true but R is false
- A is false but R is true
- State whether each of the following is TRUE or FALSE: [1 mark]
- A stack is a non-linear data structure.
- The element inserted first into a stack is the last one to be removed.
- A POP operation may result in the overflow condition.
- In prefix notation, an operator is written before its operands.
- Match each item in Column A with the correct item in Column B: [1 mark]
| Column A | Column B |
|---|---|
| a. PUSH attempted on a full stack | i. returns the top element without removing it |
| b. POP attempted on an empty stack | ii. overflow |
c. Reading index -1 of the list |
iii. LIFO |
| d. Order in which elements leave a stack | iv. underflow |
- Fill in the blank, and write the full form: [1 mark]
- The end of a stack at which insertion and deletion take place is called the ____________.
- Write the full form of LIFO.
3.12 Check Your Concepts
Define a stack. Name the two fundamental operations performed on it, stating what each one does. [2 marks]
Differentiate between overflow and underflow, giving for each the operation that causes it and the state of the stack when it arises. [2 marks]
Write the postfix form of the infix expression
x + y * z - w, and state which operation is performed first when that postfix form is evaluated. [2 marks]A student claims that reading the top element of a stack and popping the stack are the same operation. Explain, with a short example of your own, why this is not so. [3 marks]
When a stack is implemented using a Python list, the rightmost end of the list is treated as the top. Give three reasons why this end is chosen rather than the leftmost end. [3 marks]
Convert the infix expression
a + b * (c - d) / einto its postfix form. Show the contents of the stack and of the postfix string after every symbol is processed. [4 marks]Write a Python function
pop_item(stack)that removes and returns the top element of a stack implemented as a list, handling the empty-stack case without stopping the program. Then explain in two or three lines what your function gives back in that case, and how the calling program can tell that nothing was removed. [4 marks]Evaluate the postfix expression
12 4 / 3 5 + *, showing the contents of the stack after every symbol is processed. Then explain why the element popped first must be treated as the right operand, and name the operators for which ignoring this rule would give a wrong answer. [5 marks]
3.13 Output & Debugging
- Predict the output of the following code, and state the contents of the list when it ends. [2 marks]
stack = []
for value in [3, 8, 5]:
stack.append(value)
total = 0
total = total + stack.pop()
total = total + stack.pop()
print("Total =", total, "Left =", stack)- Predict the output of the following code, and state in one line what it does for any word given to it. [2 marks]
word = "STACK"
letters = []
for ch in word:
letters.append(ch)
result = ""
while len(letters) > 0:
result = result + letters.pop()
print(result)- State the three values printed by the following code, and explain why
topandstack[-1]do not print the same value. [2 marks]
stack = [4, 7]
top = stack[-1]
stack.pop()
print(top, stack[-1], len(stack))- The code below runs without any error message, but it does not behave like a stack. State what it prints, identify the mistake, and rewrite the faulty line correctly. [3 marks]
def take(stack):
return stack.pop(0)
pile = []
pile.append(10)
pile.append(20)
pile.append(30)
print(take(pile), take(pile))- The code below stops with an error. Name the line at which it fails, explain in one line why it fails, and correct it. [3 marks]
tokens = []
tokens = tokens.append("A")
tokens.append("B")
print(tokens)3.14 Case-Based Questions
- A stationery shop receives cartons through the day and stacks them one above another near the storeroom door, each carton carrying a batch code. A new carton is always placed on top of the pile, and the topmost carton is always the one taken when stock is needed. Starting with an empty pile, the following operations are carried out in this order:
| Step | Operation |
|---|---|
| 1 | PUSH B21 |
| 2 | PUSH B34 |
| 3 | PUSH B07 |
| 4 | POP |
| 5 | PUSH B55 |
| 6 | POP |
| 7 | POP |
| 8 | POP |
| 9 | POP |
a. Write the contents of the pile from bottom to top after step 5, and name the batch code that is on top at that moment. [2 marks]
b. Write, in order, the batch codes returned by the POP operations at steps 4, 6, 7 and 8. [2 marks]
c. State what happens at step 9, name the condition that arises, and explain in one line how the program should be written so that this condition does not stop it. [1 mark]- A small calculator application accepts a formula from the user in ordinary infix form, converts it to postfix, and then evaluates the postfix form. A user enters the formula below, in which each letter stands for a numeric value already known to the application.
(p + q) * r - s / ta. Convert the formula to postfix notation, showing the stack contents and the postfix string after every symbol is processed. [3 marks]
b. The application then evaluates the postfix form with `p` = 2, `q` = 3, `r` = 4, `s` = 9 and `t` = 3. Show the stack after every symbol during the evaluation, and give the final value. [3 marks]
c. Explain why the application converts the formula before evaluating it, instead of evaluating the infix form directly. [2 marks]3.15 Programming Practice
Write a complete Python program that reads integers entered by the user one at a time, stopping when the user enters
-1. Every entered integer that is divisible by 5 is pushed onto a stack implemented as a list, and all others are ignored. When the input ends, the program must pop the stack completely, printing each value as it is removed, and then print the smallest value that had been stored; if nothing was stored, it must print a suitable message instead of stopping with an error. Submit the complete program together with an identifier description table, and test it with the input 20, 7, 45, 12, 5, -1 and also with the input 3, 8, -1. [5 marks]Write a Python function
is_palindrome(text)that uses a stack to decide whether the string passed to it reads the same forwards and backwards, returningTrueorFalse. The function must build a stack of the characters oftextand obtain the reversed order by POP operations only; slicing and thereversed()function must not be used. Submit the function together with three statements that call it, one of which passes a string that is not a palindrome. [4 marks]Write a complete Python program that reads one line consisting only of the characters
(and), and reports whether the parentheses in it are properly matched. Use a stack: push every opening parenthesis, and on meeting a closing parenthesis remove one opening parenthesis from the stack. The line is properly matched only if no closing parenthesis arrives while the stack is empty, and the stack is empty when the line ends. Submit the complete program, and state what it prints for the input(())()and for the input())(. [5 marks]