Stacks and Queues
Two simple rules for adding and removing items, and a surprising amount of real software depends on picking the right one. A stack always deals with the most recent addition first. A queue always deals with the oldest one first. That's the entire idea, everything else follows from it.
Stacks: Last In, First Out (LIFO)
Push adds to the top. Pop removes from the top. Whatever went in most recently is the first thing to come back out, like a stack of plates: you take from the top, not the bottom.
Controls
Used for
- Undo functionality: the most recent action is the first to be undone.
- Browser back button: the last page visited is the first you return to.
- The function call stack: exactly what you saw with recursion, the most recently paused call resumes first.
A real sum: evaluating expressions with a stack
Here's a stack doing genuine arithmetic. Postfix notation (also called Reverse Polish Notation) writes operators after their operands: "3 4 +" means 3 + 4. Read left to right: push every number you see, and whenever you hit an operator, pop the two most recent numbers, apply it, and push the result back.
Stack
Try an expression
The algorithm
Exam tips
- Pop order matters: the first pop is the right-hand operand (b), the second pop is the left-hand operand (a). Get this backwards and subtraction/division give the wrong answer.
- By the end, exactly one value should remain on the stack, the final result.
Queues: First In, First Out (FIFO)
Enqueue adds to the back. Dequeue removes from the front. Whatever's been waiting longest is served first, exactly like a real queue at a shop.
Controls
Used for
- Print queues: documents print in the order they were sent.
- Task scheduling: jobs handled fairly in the order they arrived.
- Breadth-first search: exploring the "closest" options first, level by level.
Same values, opposite order
| Added in this order | Stack removes in | Queue removes in |
|---|---|---|
| A, B, C | C, B, A | A, B, C |
Feed the same three values into both structures above and check this table matches what you see. The data is identical, only the order of removal differs, and that difference is the whole reason both structures exist.
Circular queues: reusing the space you've freed
The queue above works, but if it's built on a fixed-size array, removing from the front normally means shifting every remaining item along, which is slow. A circular queue fixes this: front and rear pointers just wrap back to index 0 once they reach the end, so freed slots at the front get reused without shifting anything. Watch the pointers actually move around the ring below.
Guided walkthrough
A fixed 8-slot buffer. Watch the rear pointer wrap from index 7 back to 0, then to 1, reusing a slot freed earlier.
Pointer maths
Exam tips
- Both front and rear pointers move forward using modulo arithmetic:
pointer = (pointer + 1) mod size, which is exactly what makes them wrap back to 0. - A circular queue still behaves as FIFO, the wraparound is purely an implementation detail for efficiency, not a change to the underlying rule.
- You need a way to tell "empty" apart from "full", since both can look like front equals rear. Common fixes: keep a separate count (as shown here), or deliberately leave one slot always unused.
A real use for stacks: matching brackets
Bare brackets on their own don't mean much, so here's the algorithm doing its actual job: checking a calculation is well-formed before anything tries to evaluate it. This is exactly what a calculator or code editor runs before working out the answer to something like (3 + (4 * 2)) - (5 - 1).