Stacks: LIFO Operations and Trade-offs
Explain stack behaviour, trace the four required operations, and justify when a LIFO structure fits a problem.
What you need to be able to do
- explain a stack as a last-in, first-out (LIFO) structure;
- use and trace push, pop, peek and isEmpty accurately;
- explain how stack operations affect performance and memory use;
- justify whether a stack is appropriate for a specific problem.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Read a stack from the top
[A, B, C] ← Top. The stack then performs push(D), peek(), pop(), push(E), pop().Trace the operations
isEmpty().push(D)→[A, B, C, D]peek()returnsD; stack stays[A, B, C, D]pop()returnsD; stack becomes[A, B, C]push(E)→[A, B, C, E]pop()returnsE; stack becomes[A, B, C]
isEmpty() returns False because three items remain.
Explain what each operation changes
Push / pop
These operations change the number of stored items.
Peek / isEmpty
These operations inspect the stack without changing its contents.
Explain the LIFO rule
A student says, “A stack is just a list with a different name.” Explain what restriction makes a stack different as an abstract behaviour.
A stack restricts normal insertion and removal to one end, called the top. Because a new item is pushed onto the top and pop removes that same top item, the most recently added item is the first one removed, giving last-in, first-out behaviour.
What do stack operations cost?
A stack only needs direct access to its top. With an appropriate implementation, push, pop, peek and isEmpty can be performed without scanning every stored item.
Explain the trade-off
A program's undo stack grows from 10 saved actions to 10,000 saved actions. Explain one likely effect on memory use and one reason stack operations can still remain efficient.
Memory use will increase because many more undo records must be stored. The core stack operations can still remain efficient because push, pop and peek work at the top of the structure and do not require searching through all 10,000 records.
When does LIFO match the problem?
Explain why a stack is appropriate
A drawing app records actions so that Undo must reverse the most recent action that has not already been undone. Explain why a stack matches this requirement.
Each new drawing action can be pushed onto the top of the stack. When Undo is selected, pop removes the most recent action, which is exactly the action that must be reversed first. A FIFO structure would instead remove the oldest saved action first, so it would not match the Undo requirement.
Teacher-created Paper 2 practice
1. A stack initially contains, from bottom to top, [4, 7, 9]. Trace: push(12), pop(), peek(), push(15).
2. Explain how peek() differs from pop().
3. A program processes nested function calls. Explain why a stack is a suitable structure for remembering which unfinished call should resume next.
push(12)→[4,7,9,12];pop()returns 12 →[4,7,9];peek()returns 9 with no change;push(15)→[4,7,9,15].peek()returns the top item without removing it;pop()returns and removes the top item.- The most recently started unfinished call must complete or return before the earlier call resumes, which matches LIFO. New calls are pushed; returning from a call pops it and exposes the previous call.
Finish the learning cycle
IA — main task
Refine the current IA problem/planning material. Make sure the data the solution must store and manipulate is described clearly enough to support later design decisions.
Syllabus — short retrieval
Repeat only the stack cards marked “Review again”, then redo the trace on page 8 without revealing the marking points.