Press m or Esc to close
One rule — the last thing in is the first thing out. From that single restriction comes the undo button, the browser back button, and Python's own traceback.
You have a list, which lets you put a value anywhere and take it from anywhere. Total freedom.
A stack is a list you are only allowed to touch at one end. You may add at the top, remove from the top, and look at the top. Nothing else.
Because the restriction is the feature. Many real problems have exactly this shape — and a structure that can only do the right thing cannot do the wrong thing.
Data structure — a way of organising data in memory
together with the operations allowed on it.
Stack — a linear data structure in which insertion and
deletion take place at one end only, called the top, so that the
element inserted last is the one removed first.
LIFO — Last In, First Out. Whatever the question, this phrase is worth a mark, and it is the reason for every behaviour in this chapter.
Ctrl+Z reverses your most recent action first, then the one before it.
Back takes you to the page you visited most recently, not the first one.
Python's call stack. Chapter 3 §6.4 printed one — this chapter explains why it is shaped like that.
basic.pystack = [] stack.append(10) print(stack) stack.append(20) print(stack) stack.append(30) print(stack) print(stack.pop()) print(stack) print(stack.pop()) print(stack)
append() adds at the end. pop() with no
argument removes from the end. Both are already one-end operations —
so a Python list is a stack, if you use only those two methods.
You could put the top at index 0 with insert(0, x) and
pop(0). Do not. Those shift every other element up or down, so they
are slow — and the syllabus, the marking scheme and every textbook use the end.
| Operation | Stack after | top | Returned |
|---|---|---|---|
| start | [] | — | — |
| append(10) | [10] | 10 | — |
| append(20) | [10, 20] | 20 | — |
| append(30) | [10, 20, 30] | 30 | — |
| pop() | [10, 20] | 20 | 30 |
| pop() | [10] | 10 | 20 |
| pop() | [] | — | 10 |
They went in 10, 20, 30. They came out 30, 20, 10. A stack reverses the order of whatever passes through it — and that one observation is half the applications in this chapter.
| Name | Does | In Python |
|---|---|---|
| push | add at the top | st.append(x) |
| pop | remove and return the top | st.pop() |
| peek | look at the top, leave it | st[-1] |
| isEmpty | is there anything? | st == [] |
| size | how many? | len(st) |
peek, isEmpty and sizeinspect.pystack = [10, 20, 30] print("top :", stack[-1]) print("size :", len(stack)) print("empty?:", stack == []) print("stack :", stack) empty = [] print("empty?:", empty == [])
peek does not change the stack
Line 4 of the output still shows all three elements. stack[-1]
reads the top; stack.pop() removes it. Confusing the
two is the most common error in a written stack answer.
st == [] · len(st) == 0 · not st
All three are correct. Use st == [] — it is what the
marking scheme prints and it reads unambiguously.
WRONG — main.py1stack = [] 2print(stack.pop())
Underflow — the condition that arises when a
pop or peek is attempted on an empty stack.
Overflow — the condition when a push is
attempted on a full stack.
A Python list grows on demand, so a list-based stack has no fixed size and never overflows in practice. Overflow matters in languages where a stack is a fixed-size array. Write that distinction if the question asks about overflow; it shows you understand the term rather than reciting it.
pop is to check first
Every stack function you write in this chapter begins with
if st == []:. That guard is the underflow handling, and it
is a mark on its own.
stack.pydef push(st, item): st.append(item) # list end == stack top def pop(st): if st == []: return "Underflow" return st.pop() def peek(st): if st == []: return "Underflow" return st[-1] def isEmpty(st): return st == []
usestack.pyfrom stack import push, pop, peek, isEmpty s = [] print(isEmpty(s)) push(s, "a") push(s, "b") push(s, "c") print(s) print(peek(s)) print(pop(s)) print(pop(s)) print(s) print(pop(s)) print(pop(s)) print(isEmpty(s))
stack.py defines the stack once; usestack.py imports it
and uses it. This is the third kind of function from Chapter 2 §3.4 — a
user-defined module — and it is how the practical file expects a stack to be
written.
push needs no return
st.append(item) mutates the list the caller passed in — Chapter
2 §7.2 exactly. The caller's s and the parameter st are
two labels on one object, so the change is already visible outside.
peek printed c and pop then printed
c as well — because peek left it there.
The last pop on an empty stack returned "Underflow"
instead of raising IndexError. That is the guard doing its job.
Predict the exact output.
S = [] for i in [3, 1, 4, 1, 5]: S.append(i) if len(S) == 3: S.pop() print(S) print(len(S))
| i | after append | len == 3? | after the if |
|---|---|---|---|
| 3 | [3] | No | [3] |
| 1 | [3, 1] | No | [3, 1] |
| 4 | [3, 1, 4] | Yes → pop | [3, 1] |
| 1 | [3, 1, 1] | Yes → pop | [3, 1] |
| 5 | [3, 1, 5] | Yes → pop | [3, 1] |
The stack never gets past two elements: anything that makes it three is immediately popped off — and what is popped is always the item just pushed, because that is the top.
reverse.pystack = [] word = "PYTHON" # push every character for ch in word: stack.append(ch) # pop them all back off rev = "" while stack != []: rev = rev + stack.pop() print(rev)
| Phase | Stack | rev |
|---|---|---|
| after all pushes | ['P','Y','T','H','O','N'] | "" |
| pop → N | ['P','Y','T','H','O'] | "N" |
| pop → O | ['P','Y','T','H'] | "NO" |
| pop → H | ['P','Y','T'] | "NOH" |
| pop → T | ['P','Y'] | "NOHT" |
| pop → Y | ['P'] | "NOHTY" |
| pop → P | [] | "NOHTYP" |
Because the first thing pushed is the last thing popped. Reversal is not a trick you apply to a stack — it is what LIFO means.
word[::-1] from Chapter 1 does the same thing in one line. If the
question says "using a stack", you must show the push loop and the pop
loop — the slice earns nothing.
brackets.pydef balanced(expr): stack = [] for ch in expr: if ch == "(": stack.append(ch) elif ch == ")": if stack == []: return False stack.pop() return stack == [] print(balanced("(a+b)*(c-d)")) print(balanced("((a+b)")) print(balanced("a+b)("))
| Expression | Fails because |
|---|---|
| (a+b)*(c-d) | every ( was matched — stack ends empty |
| ((a+b) | one ( left on the stack at the end |
| a+b)( | a ) arrived when the stack was already empty |
Too many closing brackets is caught during the loop —
if stack == []: return False.
Too many opening brackets is caught after it —
return stack == [].
Both lines are needed; a solution with only one of them fails half the test
cases.
For one bracket type a counter works. Add [ and { and it
does not: ([)] has equal counts but is wrong. A stack remembers
which bracket is still open and in what order — a counter only remembers how
many.
tobinary.pydef to_binary(n): stack = [] while n > 0: stack.append(n % 2) n = n // 2 bits = "" while stack != []: bits = bits + str(stack.pop()) return bits print(to_binary(13)) print(to_binary(2)) print(to_binary(100))
| Pass | n | n % 2 | n // 2 | Stack |
|---|---|---|---|---|
| 1 | 13 | 1 | 6 | [1] |
| 2 | 6 | 0 | 3 | [1, 0] |
| 3 | 3 | 1 | 1 | [1, 0, 1] |
| 4 | 1 | 1 | 0 | [1, 0, 1, 1] |
Division produces the bits backwards — 1, 0, 1, 1 — but the answer is
1101. The stack holds them until they can come out in the right order. This is
the n % 10 / n // 10 digit loop from Chapter 1 §4.2,
in base 2.
undo.pyundo = [] def do(action): undo.append(action) print("did :", action) def undo_last(): if undo == []: print("nothing to undo") return print("undone:", undo.pop()) do("type Hello") do("bold") do("insert image") undo_last() undo_last() do("type World") undo_last() undo_last() undo_last()
type World was done after type Hello, so it is
undone before it — even though type Hello was still sitting
on the stack the whole time. That is LIFO behaving exactly as a user expects an
undo button to behave.
The ninth call found an empty stack and printed a message instead of raising
IndexError. Every real stack has that check.
main.py1def outer(): 2 return middle() 3 4def middle(): 5 return inner() 6 7def inner(): 8 return 1 / 0 9 10print(outer())
The traceback prints the stack from the bottom up, so the frame where the error actually happened is at the end — nearest the exception name. That is why Chapter 3 told you to read a traceback bottom-up.
fromfile.pyimport pickle def push_toppers(): st = [] with open("marks.dat", "rb") as f: data = pickle.load(f) for rec in data: if rec[1] > 85: st.append(rec[0]) return st s = push_toppers() print(s) while s != []: print(s.pop())
“Read records from a file, push the ones satisfying a condition onto a stack, then display the stack.” It is Chapter 4 §5.4 followed by this chapter's pop loop, and it is set almost every year.
The file holds Riya, Aarav, Meera in that order. Pushing preserves it; popping reverses it. If a question wants file order, print the list — if it says "display by popping", the reversal is the expected answer.
Predict the exact output.
def process(L): st = [] out = [] for x in L: if x > 0: st.append(x) else: if st != []: out.append(st.pop()) return st, out print(process([5, 3, -1, 8, -1, -1, -1]))
| x | action | st | out |
|---|---|---|---|
| 5 | push | [5] | [] |
| 3 | push | [5, 3] | [] |
| -1 | pop → 3 | [5] | [3] |
| 8 | push | [5, 8] | [3] |
| -1 | pop → 8 | [5] | [3, 8] |
| -1 | pop → 5 | [] | [3, 8, 5] |
| -1 | st is empty — nothing happens | [] | [3, 8, 5] |
The result is a tuple of two lists, because return st, out
packs them — Chapter 2 §5.4. And the last -1 did nothing at all: the
if st != [] guard prevented the underflow.
“A stack is a linear data structure in which insertion and deletion take place
at one end only, called the top, so the element inserted last is deleted first —
LIFO.”
“Underflow occurs when a pop is attempted on an empty stack; a Python
list-based stack cannot overflow because the list grows on demand.”
Write the output of the following code.
st = [] for ch in "STACK": st.append(ch) print(st.pop(), st.pop()) st.append("X") print(st) print(st[-1], len(st))
The first line is where marks go. Both pop()s run before
print displays anything — the left one first — so it is
K then C, not C K. After them the stack is
['S','T','A'], and pushing "X" makes four.
A list L contains integers. Write push_even(st, L) to push
every even number of L onto stack st, and
pop_all(st) to display and remove every element, printing
"Stack Empty" if there is nothing to show.
evens.pydef push_even(st, L): for n in L: if n % 2 == 0: st.append(n) def pop_all(st): if st == []: print("Stack Empty") return while st != []: print(st.pop(), end=" ") print() s = [] push_even(s, [12, 7, 25, 8, 31, 4]) print(s) pop_all(s) print(s) pop_all(s)
① the n % 2 == 0 test and append.
② the while st != [] pop loop.
③ the empty check printing "Stack Empty" — the
mark most often dropped.
④ no return needed on push_even, because
the list is mutated in place.
end=" " puts a space after every value, including
12. Reproduce it in the answer.
marks.dat holds a pickled list of [name, marks, stream]
records. Write a function that pushes the names of all students scoring more
than 85 onto a stack, then displays them one per line by popping. Handle the case
where nobody qualifies.
toppers.pyimport pickle def show_toppers(): st = [] with open("marks.dat", "rb") as f: data = pickle.load(f) for rec in data: if rec[1] > 85: st.append(rec[0]) if st == []: print("Stack Empty") return while st != []: print(st.pop()) show_toppers()
① import pickle, mode "rb",
pickle.load.
② the condition rec[1] > 85 and pushing
rec[0] — the name, not the whole record.
③ the empty-stack message.
④ displaying by pop(), which is why the order is
reversed.
A list and a loop (Ch 1), a function (Ch 2), a with block (Ch 4), pickle (Ch 4), and a stack (Ch 5).
A stack is a linear data structure in which insertion (push) and deletion (pop) are permitted at one end only, called the top.
Because both operations happen at the same end, the element inserted last is
the one removed first — LIFO. If 10, 20 and 30 are pushed in that
order, the first pop() returns 30. A stack of plates behaves the
same way: the plate put down last is the one picked up first.
Underflow is the condition that arises when a pop or
peek is attempted on an empty stack. Overflow arises
when a push is attempted on a stack that is already full.
In Python a stack is implemented on a list, which grows dynamically, so
there is no fixed capacity and overflow does not occur in practice. Only
underflow can occur, and it is prevented by testing
if st == [] before every pop.
Without running it — what does this print, and what is the general rule it demonstrates?
a = [1, 2, 3, 4] b = [] c = [] while a != []: b.append(a.pop()) while b != []: c.append(b.pop()) print(a) print(b) print(c)
The rule: a stack reverses. Pouring a into b
reversed it to [4, 3, 2, 1]; pouring b into
c reversed it again, restoring the original order.
Two stacks in series undo each other — exactly like
s[::-1][::-1] from Chapter 1. And a and b
are both left empty, because pop() removes as it reads.
Unit 1 is complete. You can compute, organise, name, protect, store and order data. Unit 2 leaves the single machine entirely — how two computers on opposite sides of the world exchange any of it.
Ch 1 data and control flow · Ch 2 functions and scope ·
Ch 3 exceptions · Ch 4 files — text, binary, CSV ·
Ch 5 the stack.
Unit 1 also carries the practical file, and every program in it is built
from these five chapters.