Stacks

The stack (last in, first out): push, pop, top, empty stack; array implementation; uses: bracket matching, undo, call stack, postfix expression.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Stack: what is it?
Show the answer
A collection where items are added and removed at one end only: the last item added is the first one removed.
Like a pile of plates: you put on and take off from the top. The items underneath wait until those above have gone.
What does this program print?

```python
p = []
p.append(3)
p.append(7)
a = p.pop()
p.append(1)
p.append(4)
b = p.pop()
c = p.pop()
print(a, b, c, p)
`
- 7 4 1 [3]
- 3 7 1 [4]
- 7 1 4 [3]
- 7 4 3 [1]
Show the answer
7 4 1 [3]
Removals always happen at the top: 7, then 4, then 1. The 3, pushed first, stayed at the bottom. 3 7 1 [4] is what a queue would give, as it removes the oldest.
A stack follows the rule …, …, abbreviated to LIFO.
Show the answer
A stack follows the rule last in, first out, abbreviated to LIFO.
The queue follows the opposite rule, first in, first out (FIFO): items leave from the side opposite to where they enter.
Top: what is it?
Show the answer
The end of the stack where every addition and removal takes place, and whose element can be read without removing it.
In a stack implemented with an array, the index of the top is kept. In Python, it is p[-1] for reading and p.pop() for removal.