12.05Beginner / Intermediate5 topics16 min4 interactive animations

Stack simulation

Stacks simulate processes that nest or reverse: undo and redo, browser history, function calls, depth-first search with an explicit stack and backtracking without recursion.

Learning goals

Model undo/redo and back/forward with two stacks
Explain the call stack and its limits
Convert recursive DFS into an iterative one
Replace recursion in backtracking with an explicit stack

Prerequisites

ImplementationsRecursion basics

12.05.1

Undo/redo

Undo and redo use two stacks. Every action is pushed on the undo stack; undo pops it and pushes it on the redo stack; redo moves it back. A new action clears the redo stack, because the old future no longer applies. Both operations are O(1), and the undo stack alone spells out the current document.

Type letters, undo with < and redo with >, then type again to see the redo stack cleared.

Java

1class Editor {
2    private final Deque<Character> undo = new ArrayDeque<>(), redo = new ArrayDeque<>();
3    void type(char c) { undo.push(c); redo.clear(); }
4    void undo() { if (!undo.isEmpty()) redo.push(undo.pop()); }
5    void redo() { if (!redo.isEmpty()) undo.push(redo.pop()); }
6    String text() { StringBuilder sb = new StringBuilder(); undo.descendingIterator().forEachRemaining(sb::append); return sb.toString(); }
7}

Undo/redo and browser history with two stacks

Interactive · edit the input

undo stack = the text (top is last)

empty

redo stack

empty

Setup

The undo stack holds the actions in order, so it also spells the current text. Undo moves the top action to the redo stack.

Step 1 / 9

Java

1// editor: every action goes on the undo stack
2void type(char c)  { undo.push(c); redo.clear(); }          // a new action invalidates the redo history
3void undo()        { if (!undo.isEmpty()) redo.push(undo.pop()); }
4void redo()        { if (!redo.isEmpty()) undo.push(redo.pop()); }
5// browser: a back stack, a forward stack and the current page
6void visit(String url) { if (current != null) back.push(current); current = url; forward.clear(); }
7void back()        { if (!back.isEmpty()) { forward.push(current); current = back.pop(); } }
8void forward()     { if (!forward.isEmpty()) { back.push(current); current = forward.pop(); } }

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L1		The undo stack holds the actions in order, so it also spells the current text. Undo moves the top action to the redo stack.
2	L2	action='a' text="a"	Type 'a': push on the undo stack.
3	L2	action='b' text="ab"	Type 'b': push on the undo stack.
4	L2	action='c' text="abc"	Type 'c': push on the undo stack.
5	L3	action='<' text="ab"	Undo: move 'c' from the undo stack to the redo stack.
6	L3	action='<' text="a"	Undo: move 'b' from the undo stack to the redo stack.
7	L2	action='d' text="ad"	Type 'd': push on the undo stack and clear the redo stack (2 actions lost: a new action rewrites history).
8	L4	action='>' text="ad"	Redo with nothing to redo: no change.
9	L4	return="ad"	Final text "ad".

12.05.2

Browser history

Browser navigation is the same idea with the current page held separately: visiting a page pushes the current page on the back stack and clears the forward stack; back moves the current page to the forward stack and pops the back stack; forward does the reverse. Visiting a new page after going back discards the forward history.

Switch the animation to the browser model.

Java

1class Browser {
2    private final Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
3    private String current;
4    void visit(String url) { if (current != null) back.push(current); current = url; forward.clear(); }
5    void back()    { if (!back.isEmpty()) { forward.push(current); current = back.pop(); } }
6    void forward() { if (!forward.isEmpty()) { back.push(current); current = forward.pop(); } }
7}

Undo/redo and browser history with two stacks

Interactive · edit the input

undo stack = the text (top is last)

empty

redo stack

empty

Setup

The undo stack holds the actions in order, so it also spells the current text. Undo moves the top action to the redo stack.

Step 1 / 9

Java

1// editor: every action goes on the undo stack
2void type(char c)  { undo.push(c); redo.clear(); }          // a new action invalidates the redo history
3void undo()        { if (!undo.isEmpty()) redo.push(undo.pop()); }
4void redo()        { if (!redo.isEmpty()) undo.push(redo.pop()); }
5// browser: a back stack, a forward stack and the current page
6void visit(String url) { if (current != null) back.push(current); current = url; forward.clear(); }
7void back()        { if (!back.isEmpty()) { forward.push(current); current = back.pop(); } }
8void forward()     { if (!forward.isEmpty()) { back.push(current); current = forward.pop(); } }

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L1		The undo stack holds the actions in order, so it also spells the current text. Undo moves the top action to the redo stack.
2	L2	action='a' text="a"	Type 'a': push on the undo stack.
3	L2	action='b' text="ab"	Type 'b': push on the undo stack.
4	L2	action='c' text="abc"	Type 'c': push on the undo stack.
5	L3	action='<' text="ab"	Undo: move 'c' from the undo stack to the redo stack.
6	L3	action='<' text="a"	Undo: move 'b' from the undo stack to the redo stack.
7	L2	action='d' text="ad"	Type 'd': push on the undo stack and clear the redo stack (2 actions lost: a new action rewrites history).
8	L4	action='>' text="ad"	Redo with nothing to redo: no change.
9	L4	return="ad"	Final text "ad".

12.05.3

Function calls

Every method call pushes a stack frame holding its parameters, local variables and return address; returning pops it. Recursion therefore uses a stack that grows with the depth of the calls, which is why unbounded recursion ends in StackOverflowError. Replacing the call stack with your own Deque lets you control the depth.

Step through factorial and watch the frames pile up and unwind.

Java

1static long fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }     // depth n: one frame per pending multiplication
2static long factIterative(int n) {
3    Deque<Integer> pending = new ArrayDeque<>();
4    for (int i = n; i > 1; i--) pending.push(i);          // the explicit "call stack"
5    long r = 1;
6    while (!pending.isEmpty()) r *= pending.pop();
7    return r;
8}

Factorial: calls, base case and return path

Interactive · edit the input

Recursion tree · 1 call

factorial(4)…

Running now

Call

Call factorial(4). It is frame number 1 on the call stack.

Step 1 / 20

Java

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

Live state

1 calls

depth

No condition evaluated on this step

Call stack (top first)

factorial(4)

Execution trace (dry run table)Show 20 steps

Step	Line	State	What happens
1	L1	n=4 depth=1	Call factorial(4). It is frame number 1 on the call stack.
2	L2	n=4	n is not 0, so this call cannot answer yet. It needs factorial(3).
3	L3	n=4	Pause factorial(4) and call factorial(3). The pending multiplication by 4 waits on the stack.
4	L1	n=3 depth=2	Call factorial(3). It is frame number 2 on the call stack.
5	L2	n=3	n is not 0, so this call cannot answer yet. It needs factorial(2).
6	L3	n=3	Pause factorial(3) and call factorial(2). The pending multiplication by 3 waits on the stack.
7	L1	n=2 depth=3	Call factorial(2). It is frame number 3 on the call stack.
8	L2	n=2	n is not 0, so this call cannot answer yet. It needs factorial(1).
9	L3	n=2	Pause factorial(2) and call factorial(1). The pending multiplication by 2 waits on the stack.
10	L1	n=1 depth=4	Call factorial(1). It is frame number 4 on the call stack.
11	L2	n=1	n is not 0, so this call cannot answer yet. It needs factorial(0).
12	L3	n=1	Pause factorial(1) and call factorial(0). The pending multiplication by 1 waits on the stack.
13	L1	n=0 depth=5	Call factorial(0). It is frame number 5 on the call stack.
14	L2	n=0	Base case reached: no more recursion. Everything below this point is the return path.
15	L2	n=0 return=1	return 1.
16	L3	n=1 return=1	factorial(1) resumes: 1 × 1 = 1. Return it to the caller.
17	L3	n=2 return=2	factorial(2) resumes: 2 × 1 = 2. Return it to the caller.
18	L3	n=3 return=6	factorial(3) resumes: 3 × 2 = 6. Return it to the caller.
19	L3	n=4 return=24	factorial(4) resumes: 4 × 6 = 24. Return it to the caller.
20	L3	return=24	factorial(4) = 24, using 5 calls and a maximum stack depth of 5.

12.05.4

DFS with explicit stack

Depth-first search can be written with an explicit stack instead of recursion, which avoids stack overflow on deep structures. For a tree traversal push the root; for preorder pop a node, visit it and push its right child and then its left child. For inorder walk left pushing nodes, then pop, visit and move right; postorder needs to know that the right subtree has been finished. The stack depth equals the tree height.

Switch between preorder, inorder and postorder in the animation.

Java

1static List<Integer> inorder(int[] a) {                // tree stored by level: children of i are 2i + 1 and 2i + 2
2    List<Integer> out = new ArrayList<>();
3    Deque<Integer> st = new ArrayDeque<>();
4    int cur = 0;
5    while (cur < a.length || !st.isEmpty()) {
6        while (cur < a.length) { st.push(cur); cur = 2 * cur + 1; }      // go left as far as possible
7        int i = st.pop();
8        out.add(a[i]);
9        cur = 2 * i + 2;                                                  // then the right subtree
10    }
11    return out;
12}

Depth-first traversal with an explicit stack

Interactive · edit the input

Heap as a binary tree · 7 nodes

int[] arr · length 7

0123456

Current nodeOn the stackVisited

stack of node indexes (top is last)

empty

visit order

none yet

Setup

Inorder visits the left subtree, the node, then the right subtree. The stack replaces the call stack that recursion would use.

Step 1 / 16

Java

1// nodes are array indexes: children of i are 2i + 1 and 2i + 2
2// preorder: node, left, right. Push right first so left is popped first.
3Deque<Integer> st = new ArrayDeque<>(); st.push(0);
4while (!st.isEmpty()) { int i = st.pop(); visit(i); if (2*i+2 < n) st.push(2*i+2); if (2*i+1 < n) st.push(2*i+1); }
5// inorder: left, node, right. Walk left, remember the path on the stack.
6int cur = 0;  while (cur < n || !st.isEmpty()) {
7    while (cur < n) { st.push(cur); cur = 2*cur + 1; }          // go as far left as possible
8    int i = st.pop(); visit(i); cur = 2*i + 2;                  // then the right subtree
9}
10// postorder: left, right, node. Visit a node only after its right child was visited.
11int last = -1; cur = 0; while (cur < n || !st.isEmpty()) {
12    if (cur < n) { st.push(cur); cur = 2*cur + 1; }
13    else { int top = st.peek(), r = 2*top + 2;
14           if (r < n && last != r) cur = r; else { visit(top); last = st.pop(); } }
15}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L6		Inorder visits the left subtree, the node, then the right subtree. The stack replaces the call stack that recursion would use.
2	L7	cur=1	Push 1 and keep going left.
3	L7	cur=2	Push 2 and keep going left.
4	L7	cur=4	Push 4 and keep going left.
5	L8	visit=4	No left child left: pop 4 and visit it, then move to its right subtree.
6	L8	visit=2	No left child left: pop 2 and visit it, then move to its right subtree.
7	L7	cur=5	Push 5 and keep going left.
8	L8	visit=5	No left child left: pop 5 and visit it, then move to its right subtree.
9	L8	visit=1	No left child left: pop 1 and visit it, then move to its right subtree.
10	L7	cur=3	Push 3 and keep going left.
11	L7	cur=6	Push 6 and keep going left.
12	L8	visit=6	No left child left: pop 6 and visit it, then move to its right subtree.
13	L8	visit=3	No left child left: pop 3 and visit it, then move to its right subtree.
14	L7	cur=7	Push 7 and keep going left.
15	L8	visit=7	No left child left: pop 7 and visit it, then move to its right subtree.
16	L9	return=[4, 2, 5, 1, 6, 3, 7]	Inorder: [4, 2, 5, 1, 6, 3, 7]. The stack never holds more than the tree height plus one: O(h) space.

12.05.5

Backtracking with stack

Backtracking explores choices and undoes them; recursion does this implicitly with the call stack. An explicit stack stores the pending states instead: pop a state, generate its children and push them. The example enumerates all subsets: each state is (index, mask) and either skips or takes the current element. Order of results differs from recursion, but the set is the same.

Use it when the depth could overflow the call stack.

Java

1static List<List<Integer>> subsets(int[] a) {
2    List<List<Integer>> out = new ArrayList<>();
3    Deque<int[]> stack = new ArrayDeque<>();
4    stack.push(new int[]{0, 0});                              // {index, chosen mask}
5    while (!stack.isEmpty()) {
6        int[] s = stack.pop();
7        if (s[0] == a.length) {
8            List<Integer> subset = new ArrayList<>();
9            for (int i = 0; i < a.length; i++) if ((s[1] >> i & 1) == 1) subset.add(a[i]);
10            out.add(subset);
11        } else {
12            stack.push(new int[]{s[0] + 1, s[1] | (1 << s[0])});   // take a[index]
13            stack.push(new int[]{s[0] + 1, s[1]});                  // skip a[index]
14        }
15    }
16    return out;
17}

Practice ladder

Now try it yourself

Easy

Show the undo and redo stacks after typing a, b, c, undo, undo
Why does infinite recursion end in StackOverflowError?

Medium

Simulate a browser: visit A, B, C, back, back, visit D
Write an iterative preorder traversal

Advanced

Convert a recursive permutation generator into an iterative one with an explicit stack

Key takeaways

Undo/redo and back/forward are two stacks, with the redo/forward stack cleared by a new action.
The call stack holds one frame per active call; an explicit stack replaces it.
Iterative DFS pushes pending work and pops the next item.