Learn
B2.2.3 | STACKS AND LIFO
01 | THE LAST THING ADDED IS THE FIRST THING REMOVED
Imagine stacking three trays: A first, then B, then C. To remove one without reaching through the stack, you take C. C was added last and is removed first.
A stack is a data structure with last in, first out (LIFO) access. Additions and removals occur at one designated end, called the top. The bottom entry waits until the entries above it have been removed.
This common SL/HL lesson explains push, pop, peek and isEmpty, traces their effects and connects stack implementations to performance, memory and suitable problems. A stack is defined by its access rules, not by whether the drawing is vertical.
02 | SEE THE TOP AND BOTTOM
After pushing A, then B, then C, the stack is shown below. The top is C. Its stored order from bottom to top is [A, B, C], but its next removal order is C, B, A.
Do not read a bottom-to-top list as the order in which values will be popped. Label your chosen convention in a trace. This page writes stack contents bottom → top, with the top at the right of a bracketed list.
03 | FOUR CORE OPERATIONS
| Operation | Purpose | Changes contents? | Example on [A,B,C], top C |
|---|---|---|---|
| push(value) | Add a new entry at the top. | Yes | push(D) gives [A,B,C,D]. |
| pop() | Remove and return the top entry. | Yes | pop returns C and leaves [A,B]. |
| peek() | Return/read the top entry without removing it. | No | peek returns C; contents remain [A,B,C]. |
| isEmpty() | Report whether there are no entries. | No | False for this stack. |
These names describe an abstract interface. A programming language may supply different method names or failure behaviour. Python list.append is used for push in our list-backed implementation; a wrapper function can expose the name push.
04 | PUSH: ADD AT THE TOP
Start empty. push(A) creates [A]. push(B) creates [A,B]. push(C) creates [A,B,C]. The new item becomes the top; earlier entries retain their relative order.
Push does not remove the previous top. It places the new entry above it. If A was below B before the push, it remains below B afterwards.
A fixed-capacity stack can reject a push when it has no free slot. A dynamic implementation can attempt to acquire more storage, but is still limited by resources and any application bound.
05 | POP: RETURN AND REMOVE
Popping [A,B,C] returns C and changes the stack to [A,B]. A second pop returns B. After the third pop returns A, the stack is empty.
The returned item and the remaining stack are different results of the operation. Record both in a trace: “returned C; remaining [A,B]”.
Popping an empty stack is an underflow condition. The interface must define a response, such as an exception or an explicit failure result. It must not silently invent a valid item.
06 | PEEK AND ISEMPTY DO NOT REMOVE
stack = ["A", "B", "C"]
print(stack[-1]) # C: peek
print(len(stack) == 0) # False
print(stack) # ['A', 'B', 'C']
Peek lets a program inspect the next item without consuming it. Repeated peeks return the same top value if no intervening operation changes the stack.
isEmpty answers a condition; it does not empty the collection. Check it before a top access when the calling code needs a controlled empty case.
Python stack[-1] on an empty list raises IndexError. Use the interface’s stated empty policy rather than assuming every peek in every language behaves identically.
07 | TRACE A MIXED SEQUENCE
| Operation | Returned item / result | Contents bottom → top |
|---|---|---|
| Start | No item | [] |
| push(A) | No item required by this interface | [A] |
| push(B) | No item required | [A,B] |
| peek() | B | [A,B] |
| pop() | B | [A] |
| push(C) | No item required | [A,C] |
| pop() | C | [A] |
| isEmpty() | False | [A] |
| pop() | A | [] |
The removal sequence is B, C, A because a new push occurs between the first and second pops. “Reverse the original input” only describes a sequence that pushes all values before popping them all.
At every step, derive the current top from the current contents. Do not keep using the most recent item ever pushed after it has already been removed.
08 | INTERACTIVE: CONTROL A BOUNDED STACK
Push values, predict the next result and try each operation. The diagram shows top first; the textual contents are bottom → top. The selected capacity is an application limit for this teaching model, not a claim about Python list’s internal capacity. Changing it resets the experiment.
| Operation | Result | Contents after operation |
|---|
Try push A, push B, peek, pop, isEmpty, pop and pop again. Then fill the stack and attempt one extra push. A rejected operation leaves contents unchanged. History displays the most recent 12 operations.
09 | EMPTY AND FULL ARE DIFFERENT QUESTIONS
Underflow concerns attempting a top operation when size is zero. Overflow concerns exceeding a bounded capacity on push. An empty stack is not full; a nonempty stack is not necessarily full.
For a capacity-five stack, isEmpty is true at size 0, while isFull would be true at size 5. isFull can be useful for a bounded implementation, though the core syllabus operations here are push, pop, peek and isEmpty.
Do not use None as an ambiguous empty marker if None can be a valid stored entry. An exception or a separate success flag can distinguish failure from returning a legitimate value.
10 | PYTHON: A LIST-BACKED STACK
stack = []
stack.append("A") # push
stack.append("B") # push
print(stack[-1]) # peek: B
print(stack.pop()) # pop: B
print(stack) # ['A']
print(len(stack) == 0) # isEmpty: False
Use the end of the list as the top. append and pop() work at that end, while [-1] accesses it without removal. Removing index 0 would implement a different access rule for these additions.
Although the list supports arbitrary indexing, a stack interface deliberately restricts how clients use it. The underlying collection’s extra capabilities do not change the intended LIFO contract.
11 | CONSTRUCT THE STACK INTERFACE
def push(stack, item):
stack.append(item)
def is_empty(stack):
return len(stack) == 0
def pop(stack):
if is_empty(stack):
raise IndexError("Cannot pop an empty stack")
return stack.pop()
def peek(stack):
if is_empty(stack):
raise IndexError("Cannot peek an empty stack")
return stack[-1]
work = []
push(work, "A")
push(work, "B")
print(peek(work)) # B
print(pop(work)) # B
print(pop(work)) # A
print(is_empty(work)) # True
These functions define one explicit empty policy: pop and peek raise IndexError. push mutates the supplied list and returns None implicitly; is_empty returns a Boolean.
The list passed as an argument is shared with the caller. Mutating it inside push changes the same list, unlike merely rebinding a local parameter to a different object.
12 | FIXED ARRAY MODEL: DEFINE THE TOP POINTER
A fixed-array implementation reserves slots and keeps an integer top. We choose top = −1 for empty, meaning top is the index of the most recently occupied slot. Capacity four therefore has valid storage indexes 0 through 3.
With this convention, size is top + 1. Empty means top == −1, and full means top == capacity − 1. Another textbook may use a pointer to the next free slot instead; its formulas will differ. Always state which convention applies.
| Contents | top | size |
|---|---|---|
| [] | −1 | 0 |
| [A] | 0 | 1 |
| [A,B] | 1 | 2 |
| [A,B,C,D] | 3 | 4 |
13 | FIXED ARRAY PUSH AND POP
capacity = 4
storage = [None] * capacity
top = -1
# Push A under the last-occupied-index convention.
if top == capacity - 1:
print("Stack full")
else:
top = top + 1
storage[top] = "A"
# Pop: save the item before moving the pointer.
if top == -1:
print("Stack empty")
else:
item = storage[top]
storage[top] = None
top = top - 1
print(item) # A
Check bounds before changing the pointer or accessing storage. Push increases top, then writes the new entry; pop reads the old top, clears that slot in this model, then decreases top.
Clearing a removed reference can avoid retaining an object unnecessarily. Moving top changes logical size but does not reduce the reserved array’s capacity.
This Python list simulates a fixed backing array by policy. Its built-in type is still resizable; the stack operations choose to use only the reserved slots.
14 | PERFORMANCE: ONE END MAKES OPERATIONS SIMPLE
A fixed-array push or pop normally updates one pointer and one slot, so its basic work is constant with respect to the number of stored entries. Peek reads one slot and isEmpty checks a pointer or count.
A resizable-array stack has similarly small ordinary end operations, but a growth-triggering push can allocate and copy existing entries. Push is commonly amortised constant time over a sequence, rather than guaranteed identical latency for every call.
Python list.pop() removes the final entry without shifting all preceding entries. Shrinking, allocation and runtime effects still matter. Treat asymptotic descriptions as growth behaviour, not exact timings in milliseconds.
15 | MEMORY: SIZE, CAPACITY AND PEAK USE
A fixed-capacity stack reserves room for its maximum. Unused slots cost storage, and exceeding the bound needs a defined overflow response. A resizable stack can reserve spare capacity and may temporarily need old and new backing blocks during growth.
A linked stack can add and remove nodes at its head, using a top reference. It avoids a single growing backing array, but each node needs link storage and allocation. Abstract push/pop can be constant-time link operations, while actual allocation cost depends on the system.
No dynamic stack has unlimited storage. Removing an entry changes logical size; freeing a backing block or returning memory to the operating system is a separate implementation concern.
16 | CHOOSE AN IMPLEMENTATION FOR THE WORKLOAD
| Implementation | Useful property | Trade-off |
|---|---|---|
| Fixed-capacity indexed storage | Known maximum and no capacity-growth copy while within the bound. | Unused reserved slots and overflow at the fixed limit. |
| Resizable array/list | Convenient growth and compact indexed backing storage. | Spare capacity and occasional resizing work. |
| Linked nodes at the top/head | Top changes by link updates without copying all entries. | Per-node links, allocation overhead and less contiguous storage. |
A stack is an abstract LIFO interface; the implementation determines storage costs. Do not claim that every stack is a static array or that dynamic stacks must use links.
17 | JAVA: A DEQUE USED AS A STACK
import java.util.ArrayDeque;
import java.util.Deque;
public class StackExample {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.peek()); // B
System.out.println(stack.pop()); // B
System.out.println(stack.pop()); // A
System.out.println(stack.isEmpty()); // true
}
}
Deque supports a stack interface at one end. These operations provide the same LIFO behaviour even though Python list uses different method names.
For this Java ArrayDeque, peek on empty returns null while pop on empty throws NoSuchElementException. It does not permit null entries, so the empty peek result is distinguishable. Our Python wrapper instead raises IndexError for empty peek. Read the chosen interface’s contract.
18 | AN APPROPRIATE PROBLEM: UNDO
A simple text editor lets a user undo the most recent change before earlier changes. That ordering matches LIFO: the last edit is the next one reversed.
One teaching implementation stores a snapshot of the previous document before each accepted edit. Push the old text; apply the new text. Undo pops the most recent saved snapshot and restores it.
For documents of length m and k snapshots, retained text can be large, roughly proportional to the sum of snapshot lengths. A production editor may store edit commands or differences instead. A stack provides the ordering, not a guarantee of low memory use.
19 | INTERACTIVE: WHY UNDO USES A STACK
The current document starts as CODE. Apply a new document value, then undo. Each actual edit pushes the previous text. Undo restores and removes the most recent snapshot. Empty text is allowed as document content; it is not used to indicate an empty history. This model retains up to five snapshots.
Try CODE → CODER → CODING, then undo twice. The states restored are CODER and CODE. A third undo has no saved snapshot. Undo does not automatically enable redo: a separate redo history and a policy for new edits would be needed.
20 | OTHER LIFO APPLICATIONS
Nested function calls resume in the reverse order in which unfinished calls were entered. Conceptually, a call stack holds frames containing return context and local state. The most recently entered unfinished call must finish before its caller resumes.
Bracket matching also uses nesting: the last opening bracket must be matched by the next appropriate closing bracket. A closing square bracket cannot correctly match an opening parenthesis merely because a stack is nonempty.
Backtracking can store earlier choices or states so the most recent unresolved decision is revisited first. The application must define what data each entry contains and what restoration means.
21 | WORKED PROGRAM: REVERSE A SEQUENCE
letters = ["C", "O", "D", "E"]
stack = []
for letter in letters:
stack.append(letter)
reversed_letters = []
while len(stack) > 0:
reversed_letters.append(stack.pop())
print(reversed_letters) # ['E', 'D', 'O', 'C']
print(stack) # []
Pushing all entries then popping them all reverses their order. Each letter is pushed and popped once, so the number of core operations grows linearly with the input length. The stack can hold the entire input, using linear additional entry storage.
The original letters list remains available, but the working stack is consumed. In Python there are shorter reversal methods; this program demonstrates why LIFO reverses a sequence.
22 | WORKED PROGRAM: MATCH PARENTHESES
def balanced_parentheses(text):
stack = []
for character in text:
if character == "(":
stack.append(character)
elif character == ")":
if len(stack) == 0:
return False
stack.pop()
return len(stack) == 0
print(balanced_parentheses("(a+(b*c))")) # True
print(balanced_parentheses(")(")) # False
print(balanced_parentheses("(()")) # False
A closing parenthesis requires an unmatched opening parenthesis. Pop it when matched. At the end, no openings may remain. Other characters are ignored in this particular task.
This checks parentheses only, not square/curly brackets, quoted text or a complete programming language. A multi-bracket version must also compare each closing type with the latest opening type.
Worst-case stored openings grow with input length. Every character is inspected once, but a list-backed push may occasionally trigger resizing.
23 | WHY A STACK DOES NOT FIT EVERY TASK
A first-come, first-served printer queue normally needs the oldest pending job next. A stack would give priority to the newest job, potentially delaying old jobs indefinitely as more arrive.
Choosing a stack therefore requires an explanation of why reversing access to pending entries matches the problem. For undo, the last edit is reversed first; for fair arrival-order service, that is usually the wrong rule.
A stack does not automatically allow efficient search for an arbitrary middle item through its abstract interface. If the task frequently needs unrelated indexed access, a different interface may suit it better.
24 | TEST OPERATIONS AND BOUNDARIES
| Test | Expected evidence |
|---|---|
| Pop or peek when empty | Defined underflow response; contents unchanged. |
| Push A, push B, peek | Return B without removal. |
| Push A, push B, pop twice | Return B then A; become empty. |
| Push after a pop | New item becomes the top. |
| One more push than bounded capacity | Defined overflow response; no overwritten entries. |
| Duplicate values | Each push creates a separate entry even when values are equal. |
Track size, contents, returned values and the pointer convention, rather than only checking the last output. A history or undo stack must preserve the correct state, not merely return a plausible-looking value.
25 | WRITE AN EXPLAIN ANSWER
Connect rule → operation → consequence. For example: “Undo stores the previous state before each edit. The most recent saved state is on top, therefore popping it reverses the latest edit before earlier ones.”
For performance, name the implementation and operation: a fixed-array pop updates the top and one slot; a resizable-array push may need a growth copy; a linked push allocates a node and updates references. Avoid saying every stack operation takes exactly the same measured time.
For memory, distinguish current entries, reserved capacity, per-entry overhead and any data stored inside each entry.
26 | READY FOR THE NEXT ACCESS RULE
You should now be able to trace LIFO behaviour, implement push/pop/peek/isEmpty, handle empty/full cases and justify an appropriate application with performance and memory considerations.
The next lesson introduces FIFO queues, where the earliest pending entry is removed first.