B2.2.3 · Data structures
Stacks: last in, first out
Some collections don't care about order at all. A stack cares about exactly one thing: whatever went in most recently is the only thing you can ever take out next.
Explainer
A stack of trays at a cafeteria counter works one way and one way only: a clean tray goes on TOP of the pile, and whoever takes the next tray takes the one sitting on top, never one from partway down the pile. It's physically impossible to pull a tray out of the middle without disturbing everything above it. A program can enforce that exact same restriction on purpose, and that restriction is the entire point of the structure.
A stack is an abstract data structure that works on the Last In, First Out (LIFO) principle, sometimes called First In, Last Out (FILO). Only the item most recently added, the item on top, can be accessed, added to, or removed. Everything below it is temporarily unreachable.
A stack can be built two ways: as a static structure using an array (a fixed maximum size, decided upfront), or as a dynamic structure with its elements chained together via references, no fixed limit, growing one item at a time. The LIFO behaviour is identical either way, this is the same static-vs-dynamic choice from B2.2.1, just applied to one specific structure. (HL students meet this chained structure by name, as a linked list, when they reach B4.1.3.)
Explainer
The four required operations
The syllabus names these four explicitly. Each does exactly one job, and no two of them do the same job.
| Operation | What it does | Python (a function per operation) | Java (java.util.Stack) |
|---|---|---|---|
| push | Add a new item to the top | push(stack, value) | stack.push(value); |
| pop | Remove AND return the top item | pop(stack) | stack.pop(); |
| peek | Return the top item WITHOUT removing it | peek(stack) | stack.peek(); |
| isEmpty | Check whether the stack has anything in it at all | is_empty(stack) | stack.isEmpty(); |
Java's own Stack class happens to name its methods identically to the syllabus terms, push/pop/peek/isEmpty, so there's no vocabulary gap to bridge on this statement, unlike some others.
In Python, the cleanest way to teach these four operations is one small function per operation, each taking the stack (a plain list) as its argument:
Every later example on this page calls these four functions instead of writing append/pop() directly, so the stack's four required operations stay named exactly as the syllabus states them.
peek and pop are not the same operation, and mixing them up is the single most common slip on this statement. peek only looks, the stack is completely unchanged afterward. pop genuinely removes the top item, the stack is one item smaller afterward. If a question needs the stack unchanged for a later step, that's peek, never pop.
Overflow and underflow are the two failure conditions named alongside these operations. Stack overflow is attempting to push onto a stack that's already at its maximum size (only possible for a static, array-based stack with a genuine fixed limit). Stack underflow is attempting to pop (or peek) from a stack that's already empty, there's nothing there to return. A static implementation commonly adds a fifth operation, isFull, checked BEFORE every push specifically to catch overflow before it happens rather than after.
Explainer
How the choice of implementation affects performance and memory
This is the statement's second named requirement, and it's a direct application of B2.2.1's comparison to one specific structure.
Real example: a fixed-size stack of at most 20 trays, the counter genuinely cannot hold a 21st.
Advantage
- Fast push/pop (writing to or reading from one known index, no memory allocation needed on every operation)
Disadvantage
- A genuine maximum size (push past that size is a real stack overflow, not just a slow operation)
Real example: an undo history with no sensible upper limit on how many actions a user might take.
Advantage
- No fixed limit (genuinely cannot overflow, it grows one linked node at a time as long as memory allows)
Disadvantage
- Extra memory per item (every node stores a link to the next one, on top of the value itself, and allocating that node costs real time on every push)
Worked example
An undo history for a drawing app
Every action a user takes gets pushed onto a stack. Undo pops the most recent one, whatever that happens to be, which is exactly the behaviour LIFO guarantees and a queue never could.
Step 1. Three actions, pushed in order. Each call to push adds to the top. The stack now holds, top to bottom, the reverse of the order they happened in.
Step 2. peek before deciding anything. The app checks what undo WOULD affect, without changing the stack at all.
Step 3. pop actually undoes it. "draw line" is removed and returned. The stack is genuinely one item smaller now, "draw square" is the new top.
Step 4. isEmpty guards every undo request. Before popping again, the app must check there's actually something to undo.
Step 5. One more undo, then genuinely empty. The isEmpty check is what stops the NEXT undo from underflowing, attempting to pop again here would be exactly the failure case named above.
Try it yourself
Run the undo history
The same push/peek/pop/isEmpty sequence as the steps above, live and editable, using the same four functions. An experiment is waiting at the bottom: keep undoing past the point where the stack is empty, and watch pop's stack.pop() raise a real error instead of quietly doing nothing.
Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports lists used as stacks (append, pop, negative indexing, len), exactly what this page needs, but it isn't full Python.
Check your understanding
A stack holds, top to bottom: "C", "B", "A". peek() is called, then pop() is called. What does the stack hold afterward, and what did each operation return?
Common mistake
RecurringWhen asked to state an application of a stack, a vague answer like "stacks are used for undo" is reported as not specific enough to earn the mark. The mark is for describing an actual mechanism, not just naming a use case in passing.
The second common slip is confusing peek with pop, treating "look at the top" and "remove the top" as interchangeable when a question depends on the stack being unchanged afterward.
Answer frame that scores: name the application AND explain the specific push/pop mapping. "An undo feature" is not enough; "each action a user takes is pushed onto a stack, and using undo pops the most recent action back off" is.
What the vague version looks like: "A stack could be used to undo actions in an app." Names a use case, explains nothing about how push/pop actually implement it.
What it should say: "Each action the user takes is pushed onto a stack as it happens. When undo is triggered, the stack is popped, removing and reversing the most recently performed action, exactly the LIFO order undoing requires." States the mechanism, not just the label.
Revision questions
Past-paper style. Write an answer, then reveal the marking points and mark yourself.
[2]Distinguish between the peek and pop operations on a stack.
Marking points
评分要点
- Peek returns the item on top of the stack without removing it, so the stack is unchanged.
- Pop removes the item on top of the stack and returns it, so the stack has one fewer element.
- peek 返回栈顶的项但不移除它,栈保持不变。
- pop 移除栈顶的项并返回它,栈少一个元素。
[3]Explain how a stack could be used to implement the "back" button in a web browser.
Marking points
评分要点
- Each page the user visits is pushed onto a stack.
- Pressing back pops the current page off the stack.
- The page now on top of the stack is the previous one, which is displayed; this gives last-in, first-out behaviour that matches going back through history.
- 用户访问的每个页面被压入一个栈。
- 按后退把当前页面从栈中弹出。
- 现在位于栈顶的页面是上一个,被显示出来;这给出后进先出的行为,与在历史记录中后退相符。
[4]Compare an array-based (static) stack with a chained, dynamic stack in terms of performance and memory usage.
Marking points
评分要点
- Array-based (static) stack: push and pop are fast constant-time operations, but the size is fixed so it can overflow, and unused slots waste memory.
- Chained, dynamic stack: it grows and shrinks to fit the data so no overflow and no wasted slots, but each node needs extra memory for a reference and traversal is slower due to scattered memory.
- For a known small maximum the array stack is simpler and faster; for an unpredictable size the chained stack is safer.
- 基于数组的(静态)栈:压入和弹出是快速的常数时间操作,但大小固定所以可能上溢,未使用的位置浪费内存。
- 链式的动态栈:它增长和收缩以适应数据,所以没有上溢也没有浪费的位置,但每个节点需要额外内存存放引用,且由于内存分散遍历较慢。
- 对于已知的小最大值,数组栈更简单更快;对于不可预测的大小,链式栈更安全。
Flashcards
Active recall for this statement’s key terms.
Keep this statement’s practice with you
Free account: unlock every revision question and flashcard for B2.2.3, and every other IB CS 2027 statement.