Tracing the Two Stacks
Here is a sequence of operations on a stack of integers that starts out empty:
stack.push(17);
stack.push(42);
stack.push(28);
stack.pop();
stack.push(65);
stack.pop();
stack.pop();
Solution
push(17)
┌────┬────┬────┬────┬────┐
│ 17 │ _ │ _ │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
push(42)
┌────┬────┬────┬────┬────┐
│ 17 │ 42 │ _ │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
push(28)
┌────┬────┬────┬────┬────┐
│ 17 │ 42 │ 28 │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
pop()
┌────┬────┬────┬────┬────┐
│ 17 │ 42 │ _ │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
push(65)
┌────┬────┬────┬────┬────┐
│ 17 │ 42 │ 65 │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
pop()
┌────┬────┬────┬────┬────┐
│ 17 │ 42 │ _ │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
pop()
┌────┬────┬────┬────┬────┐
│ 17 │ _ │ _ │ _ │ _ │
└────┴────┴────┴────┴────┘
↑
size
Solution
push(17)
┌────┐
top ───▶ │ 17 │ ──▶ null
└────┘
push(42)
┌────┐ ┌────┐
top ───▶ │ 42 │ ──▶ │ 17 │ ──▶ null
└────┘ └────┘
push(28)
┌────┐ ┌────┐ ┌────┐
top ───▶ │ 28 │ ──▶ │ 42 │ ──▶ │ 17 │ ──▶ null
└────┘ └────┘ └────┘
pop()
┌────┐ ┌────┐
top ───▶ │ 42 │ ──▶ │ 17 │ ──▶ null
└────┘ └────┘
push(65)
┌────┐ ┌────┐ ┌────┐
top ───▶ │ 65 │ ──▶ │ 42 │ ──▶ │ 17 │ ──▶ null
└────┘ └────┘ └────┘
pop()
┌────┐ ┌────┐
top ───▶ │ 42 │ ──▶ │ 17 │ ──▶ null
└────┘ └────┘
pop()
┌────┐
top ───▶ │ 17 │ ──▶ null
└────┘