Stacks
IB Syllabus: B2.2.3 – Explain the concept of a stack as a “last in, first out” (LIFO) data structure: push, pop, peek, isEmpty.
Table of Contents
- Key Concepts
- Using Stacks in Java
- Visualising Stack Operations
- Real-World Applications
- Worked Examples
- Quick Check
- Trace Exercise
- Code Completion
- Spot the Error
- Predict the Output
- Practice Exercises
- Connections
Key Concepts
What is a Stack?
A stack is an abstract data structure that follows the Last In, First Out (LIFO) rule: the last item added is the first item removed. You can only access the top element.
Think of a stack of plates in a cafeteria: you add plates to the top and take plates from the top. You cannot pull a plate from the middle.
Stack Operations
| Operation | Description | Java Method |
|---|---|---|
| Push | Add an item to the top | stack.push(value) |
| Pop | Remove and return the top item | stack.pop() |
| Peek | Look at the top item without removing it | stack.peek() |
| isEmpty | Check if the stack has no elements | stack.isEmpty() |
| Size | Get the number of elements | stack.size() |
Pop and peek on an empty stack throw an EmptyStackException. Always check isEmpty() before calling pop() or peek().
Using Stacks in Java
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
// Push elements onto the stack
stack.push(10); // stack: [10] top = 10
stack.push(20); // stack: [10, 20] top = 20
stack.push(30); // stack: [10, 20, 30] top = 30
// Peek at the top (does not remove)
System.out.println(stack.peek()); // 30
// Pop the top element (removes and returns)
System.out.println(stack.pop()); // 30 stack: [10, 20]
System.out.println(stack.pop()); // 20 stack: [10]
// Check state
System.out.println(stack.isEmpty()); // false (10 is still there)
System.out.println(stack.size()); // 1
Remember: Stack<Integer> not Stack<int>. Like ArrayList, stacks store objects, not primitives.
Visualising Stack Operations
Push 10: Push 20: Push 30: Pop: Pop:
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ │ │ │ │ 30 │ ← │ │ │ │
├────┤ ├────┤ ├────┤ ├────┤ ├────┤
│ │ │ 20 │ ← │ 20 │ │ 20 │ ← │ │
├────┤ ├────┤ ├────┤ ├────┤ ├────┤
│ 10 │ ← │ 10 │ │ 10 │ │ 10 │ │ 10 │ ←
└────┘ └────┘ └────┘ └────┘ └────┘
top=10 top=20 top=30 top=20 top=10
The arrow (←) marks the top of the stack. Push adds above the arrow; pop removes at the arrow.
Real-World Applications
Undo/Redo
Every time you make an edit, the action is pushed onto the undo stack. Pressing Ctrl+Z pops the most recent action and undoes it. The undone action is pushed onto a redo stack.
Browser Back Button
Each page you visit is pushed onto a history stack. Clicking “Back” pops the current page and displays the previous one.
Method Call Stack
When a method calls another method, the calling method’s state is pushed onto the call stack. When the called method returns, its frame is popped and the calling method resumes.
public static void main(String[] args) {
System.out.println(add(3, multiply(4, 5)));
}
// Call stack when multiply runs: [main, add, multiply]
// multiply returns 20, popped: [main, add]
// add returns 23, popped: [main]
Expression Evaluation
Calculators use stacks to evaluate expressions with brackets. Opening brackets are pushed; when a closing bracket is found, operations are popped and evaluated.
When you see LIFO in an exam question, think stack.
Worked Examples
Example 1: Reversing a String
A stack naturally reverses order: push all characters, then pop them.
public static String reverse(String text) {
Stack<Character> stack = new Stack<>();
// Push each character
for (int i = 0; i < text.length(); i++) {
stack.push(text.charAt(i));
}
// Pop to build reversed string
String reversed = "";
while (!stack.isEmpty()) {
reversed += stack.pop();
}
return reversed;
}
System.out.println(reverse("hello")); // "olleh"
Example 2: Bracket Matching
Check if brackets in an expression are balanced: every ( must have a matching ).
public static boolean isBalanced(String expression) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
return false; // closing bracket with no opening
}
stack.pop();
}
}
return stack.isEmpty(); // true if all brackets matched
}
System.out.println(isBalanced("(a + b) * (c - d)")); // true
System.out.println(isBalanced("((a + b)")); // false
System.out.println(isBalanced("a + b)")); // false
Quick Check
Q1. What does LIFO stand for and what does it mean?
Q2. You push A, B, C (in that order). Then pop(), then peek(). What does peek() return?
Q3. What happens if you call pop() on an empty stack?
Q4. Which real-world application uses a stack?
Q5. What is the difference between peek() and pop()?
Trace Exercise
Trace the stack contents after each operation.
Trace: Track the stack contents and the return value of each operation.
Stack<String> stack = new Stack<>();
stack.push("Red"); // Op 1
stack.push("Blue"); // Op 2
stack.push("Green"); // Op 3
stack.pop(); // Op 4
stack.push("Yellow"); // Op 5
stack.peek(); // Op 6
stack.pop(); // Op 7| After Op | Stack (bottom to top) | Return Value |
|---|---|---|
| 1 | [Red] | -- |
| 2 | [Red, Blue] | -- |
| 3 | [Red, Blue, Green] | -- |
| 4 | ||
| 5 | -- | |
| 6 | ||
| 7 |
Code Completion
Complete the method that uses a stack to check if a string is a palindrome.
Fill in the blanks: Push all characters, then pop and compare.
public static boolean isPalindrome(String text) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < text.length(); i++) {
stack.(text.charAt(i));
}
for (int i = 0; i < text.length(); i++) {
if (text.charAt(i) != stack.) {
return ;
}
}
return true;
}Spot the Error
This code should reverse the numbers, but it crashes.
Bug Hunt: This code should print all numbers in reverse, but it misses the last one.
Pick the correct fix for line 4:
Predict the Output
Predict: What does this code print?
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(10);
s.push(15);
System.out.println(s.pop());
s.push(20);
System.out.println(s.pop());
System.out.println(s.peek());Practice Exercises
Core
-
Stack trace – Starting with an empty stack, perform these operations and write the stack contents after each: push(5), push(10), push(15), pop(), push(20), pop(), pop(), peek().
-
Reverse an array – Write a method that takes an
int[]array and uses aStack<Integer>to return a new array with the elements in reverse order. -
Stack applications – For each of the following, explain whether a stack is appropriate and why:
- (a) Managing browser history (back button)
- (b) A queue at a supermarket checkout
- (c) Evaluating nested brackets in a math expression
Extension
-
Undo system – Create a simple text editor model: an
ArrayList<String>of lines and aStack<String>for undo. ImplementaddLine(String line)(adds to the list and pushes to undo stack) andundo()(removes the last line added). -
Two-stack sort – Given a stack of integers in random order, use one additional stack to sort the elements so the smallest is on top. You may only use push, pop, peek, and isEmpty.
Challenge
- Postfix evaluator – Implement a calculator that evaluates postfix (Reverse Polish Notation) expressions. For example,
"3 4 + 2 *"means(3 + 4) * 2 = 14. Use a stack: push numbers, and when you encounter an operator, pop two numbers, apply the operator, and push the result.
Connections
- Prerequisites: 1D Arrays – understanding indexed collections
- Prerequisites: ArrayList – dynamic collections using Java generics
- Related: Queues – FIFO counterpart to stacks
- Forward: Recursion (HL) – the call stack is a stack
- Forward: ADTs: Stacks from Scratch (HL) – implementing your own stack