Stacks, queues and reverse Polish notation
Stacks and queues are lists where you can only add and remove items at certain ends. That restriction is exactly what makes them useful, for undo buttons, printer queues, subroutine calls and evaluating expressions.
Part 1 of 3: Learn it
In short
- A stack is last in, first out (LIFO): push on and pop off the top.
- A queue is first in, first out (FIFO): enqueue at the rear, dequeue from the front.
- Reverse Polish notation puts the operator after its operands and is evaluated with a stack.
Where this is in your specification
Spec points: AQA 7517 4.2.3, 4.2.4 and 4.3.2, OCR H446 1.4.2
| Board | Topic: Data structures |
|---|---|
| AQA 7517 | 4.2.1 to 4.2.6, 4.3.1 to 4.3.3 |
| OCR H446 | 1.4.2 and 2.3.1 |
| Higher C816 76 | Software design and development: parallel 1D arrays, records, arrays of records |
Stacks
| Operation | What it does |
|---|---|
| push(item) | add to the top, if the stack is not full |
| pop() | remove and return the top item, if not empty |
| peek() | return the top item without removing it |
| isEmpty() / isFull() | check before popping or pushing |
A stack uses one pointer to the top. Pushing onto a full stack is an overflow; popping from an empty one is an underflow. Uses: the call stack for subroutines, undo, browser back buttons and backtracking.
Queues
- Linear queue: front and rear pointers move along an array. Space at the start is wasted once items are removed, unless items are shuffled forward.
- Circular queue: the rear pointer wraps round to the start, using (pointer + 1) MOD size, so freed space is reused.
- Priority queue: each item has a priority; higher priority items are dequeued first, regardless of arrival order.
Reverse Polish notation
In RPN, (3 + 4) × 2 is written 3 4 + 2 ×. There are no brackets and no precedence rules. To evaluate, read left to right: push each number; when you meet an operator, pop two values, apply it (second popped, operator, first popped) and push the result.
Convert (a + b) × c to reverse Polish notation.
Show the answer
a b + c ×.
Part 2 of 3: See it worked
Worked examples
Example 1
An empty stack has these operations: push 4, push 7, pop, push 2, push 9, pop. Which values are popped, and what is left?
- push 4: [4]; push 7: [4, 7]
- pop returns 7: [4]; push 2: [4, 2]; push 9: [4, 2, 9]
- pop returns 9: [4, 2]
Answer: 7 then 9 are popped; the stack holds 4 (bottom) and 2 (top).
Example 2
Evaluate the RPN expression 6 2 3 + ×.
- Push 6, push 2, push 3
- + : pop 3 and 2, push 5
- × : pop 5 and 6, push 30
Answer: 30.
Common mistakes
- Popping from the bottom of a stack, or dequeuing from the rear of a queue.
- Getting the order wrong for − and ÷ in RPN: the second value popped comes first.
- Forgetting the MOD that wraps a circular queue's pointers.
- Not checking for empty or full before removing or adding.
Evaluate 8 2 − 3 ×.
Show the answer
(8 − 2) × 3 = 18.
Part 3 of 3: Test yourself
Check yourself
Answer each one in your head or on paper first, then open it to check.
Convert (a + b) × c to reverse Polish notation.
a b + c ×.
Evaluate 8 2 − 3 ×.
(8 − 2) × 3 = 18.
Give one use of a queue in a computer system.
Any one of: print jobs, keyboard buffer, processes waiting for the CPU, breadth-first search.
Jobs that use this
Each link opens the job profile on the National Careers Service (England). In the rest of the UK: My World of Work (Scotland), Careers Wales, nidirect careers (Northern Ireland).
Full lessons and marked practice for this course are coming soon to Brainlag Learn. See courses