- Define and explain Using Stacks in your own words
- Use key terms such as stack accurately
- Apply what you have learned to new examples and questions
- Avoid the common mistakes learners make with this topic
A list is not always the right tool: undo buttons, printer queues, file systems and sat-navs each need their own way of organising data. Data structures are these specialised containers, and choosing well is what separates working code from elegant code. This chapter builds the four structures every A-level student must master.
This lesson focuses on Using Stacks: store data last-in, first-out, like a pile of plates.
Store data last-in, first-out, like a pile of plates.
Key ideas
LIFO versus FIFO changes everything
Stacks reverse order — perfect for undo, back buttons and checking balanced brackets. Queues preserve order — perfect for print spooling and handling requests fairly. The operations differ too: stacks push and pop at the top, while queues enqueue at the rear and dequeue at the front. Picking the wrong one silently produces wrong answers.
Trees turn searching into halving
A binary search tree keeps smaller values left and larger values right, so each comparison discards half the tree — the same idea as binary search, built into the structure. Traversals visit nodes in different orders: in-order on a binary search tree yields the values sorted. Insert order shapes the tree, and a badly ordered insert degrades it into a slow linked list.
Key term — stack: A last-in, first-out structure: items are added and removed from the same end, called the top — like a spring-loaded plate dispenser.
Start with an empty stack. Push 4, push 7, pop, push 2, pop. What does each pop return, and what is left?
Push 4: the stack is [4] with 4 on top. Push 7: the stack is [4, 7] with 7 on top. Pop removes from the top, so the first pop returns 7. The stack is [4]. Push 2: the stack is [4, 2] with 2 on top. Pop again removes the top, so the second pop returns 2. The stack is [4].
Answer: The pops return 7 then 2, and the stack holds just [4] — last in, first out.
- Using a stack where a queue is needed Correction: ask 'must the first arrival be served first?' — if yes, you need a queue; a stack would serve the last arrival first.
- Popping or dequeuing from an empty structure Correction: always check the structure is not empty first — removing from nothing causes an underflow error.
Practice
A stack — each new page is pushed, and Back pops the most recent page, which is last-in, first-out.
True — push each opening bracket and pop on each closing one; the last opened must be the first closed, which is exactly LIFO.
[B, C, D] — A leaves from the front and D joins at the rear.
3 — it goes left of root 5, and then 1 goes left of 3.
Quick check
Which of these best defines "stack"?
In a road network modelled as a graph, what do nodes, edges and weights represent?
What does an in-order traversal of a binary search tree produce?
- Using Stacks: store data last-in, first-out, like a pile of plates.
- LIFO versus FIFO changes everything: Stacks reverse order — perfect for undo, back buttons and checking balanced brackets.
- node: A single element in a tree or graph, holding data plus links to other nodes.
- Watch out for: using a stack where a queue is needed