The shape of the lesson
By the end of the lesson, learners can
- Stacks: last in, first out: In the lab, push a few values, then pop them.
- Queues: first in, first out: In the lab, fill the queue, take two items off the front and try to add more.
- Linked lists: In the lab, insert and delete items and watch only the pointers change: no data is moved.
- Stack (LIFO): push = check full, top + 1, store; pop = check empty, read, top − 1.
- Queue (FIFO): add at the rear, remove from the front; circular pointers wrap with MOD; keep a count.
- Linked list: node = data + pointer; start pointer, null pointer, free list.
- Insert: new node's pointer first, then the previous node's pointer.
One picture every idea returns to
An abstract data type (ADT) is a collection of data together with a set of operations on that data. A stack is last in, first out (LIFO): items are pushed onto and popped from the top, tracked by a top pointer. A queue is first in, first out (FIFO): items join at the rear and leave from the front; a circular queue reuses freed spaces. A linked list is a set of nodes, each holding data and a pointer to the next node, with a start pointer, a null pointer at the end and a free list of unused nodes. All three can be implemented using arrays.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Data with rules.. An abstract data type is defined by what you can do with it, not by how it is stored. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Stacks: last in, first out | In the lab, push a few values, then pop them. Project tab 1 of the lab (Stack) and let a student drive it while the class predicts. Model the worked example Trace a stack on the board, one line at a time. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Queues: first in, first out | In the lab, fill the queue, take two items off the front and try to add more. Project tab 2 of the lab (Circular queue) and let a student drive it while the class predicts. Model the worked example Trace a circular queue on the board, one line at a time. Your turn: Continue: ENQUEUE G, then ENQUEUE H. What happens? | Pairs |
| 21 to 30 min | Teach and check: Linked lists | In the lab, insert and delete items and watch only the pointers change: no data is moved. Project tab 3 of the lab (Linked list with a free list) and let a student drive it while the class predicts. Model the worked example Insert into an ordered list on the board, one line at a time. Your turn: Start again from the original table and delete Fig. Which pointers change? | Anticipation / Reaction Guide |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 23 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Linked lists, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Anticipation / Reaction Guide
Before the lesson, students mark five statements true or false. After the teaching they mark them again and justify any change of mind in one sentence each. The statements come from the examiner traps below.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| Do not say a pop "deletes" the value from the array. | Only the pointer changes; the old value is simply overwritten by the next push. |
| In a circular queue, Rear = upper bound does not mean the queue is full: Rear can wrap round. | Test fullness with the count (or by comparing the pointers carefully). |
| When inserting, set the new node's pointer before changing the previous node's pointer. | Doing it the other way round loses the address of the rest of the list. |
Stacks, queues and linked lists: worksheet
6 questions, 23 marks. Written in the style of the papers; no past paper question is reproduced.
Explain what is meant by an abstract data type (ADT) and name two examples.
A stack uses Stack : ARRAY[1:5] OF INTEGER, so an empty stack has TopOfStack = 0. Starting from empty, these operations are carried out: PUSH 12, PUSH 30, PUSH 7, POP, POP, PUSH 25, PUSH 18, PUSH 4, PUSH 9. State (a) the values returned by the POP operations, (b) the final value of TopOfStack and the contents of the stack, (c) what would happen with a further PUSH 6.
A circular queue uses Queue : ARRAY[0:4] with FrontPointer = 0, RearPointer = −1 and NumberInQueue = 0. These operations are carried out: ENQUEUE 10, ENQUEUE 20, ENQUEUE 30, DEQUEUE, DEQUEUE, ENQUEUE 40, ENQUEUE 50, ENQUEUE 60. State the final values of the three variables and the next item to be dequeued.
Describe how a queue can be implemented using an array.
A linked list of integers in ascending order is stored using arrays, with −1 as the null pointer.
| Index | Data | Pointer |
|---|---|---|
| 0 | 27 | 2 |
| 1 | 9 | 0 |
| 2 | 41 | −1 |
| 3 | 4 | |
| 4 | −1 |
StartPointer = 1 and FreeListPointer = 3. (a) 30 is inserted. Give the new contents of the Pointer array and the values of StartPointer and FreeListPointer. (b) 5 is then inserted. Give the values that change.
For each situation, state whether a stack, a queue or a linked list is most suitable and justify your choice: (a) the undo feature of a graphics program, (b) callers waiting to speak to a helpline, (c) a list of contacts kept in alphabetical order where contacts are often added and removed.
Answer key and marking notes
- A collection of data together with a set of operations on that data.
- Any two of: stack, queue, linked list.
- (a) 7, then 30.
- (b) TopOfStack = 5.
- (b) The stack holds 12, 25, 18, 4, 9 (bottom to top).
- (c) The stack is full, so stack overflow: 6 is not added.
- FrontPointer = 2.
- RearPointer = 0 (60 wraps round into index 0).
- NumberInQueue = 4.
- The next item dequeued is 30.
- A 1D array holds the items, with a fixed size.
- A front pointer gives the index of the item to be removed next; a rear pointer gives the index of the last item added.
- Enqueue: check the queue is not full, move the rear pointer on and store the item; dequeue: check it is not empty, return the item at the front and move the front pointer on.
- Pointers wrap round to the start of the array (circular queue), and a counter records how many items are in the queue.
- (a) 30 is stored in node 3; FreeListPointer becomes 4.
- (a) 30 goes after 27 (node 0): Pointer[3] = 2, then Pointer[0] = 3.
- (a) Pointer array 3, 0, −1, 2, −1; StartPointer = 1; FreeListPointer = 4.
- (b) 5 is stored in node 4; FreeListPointer becomes −1 (the free list is now empty).
- (b) 5 is smaller than the first item, so Pointer[4] = 1 (the old StartPointer).
- (b) StartPointer = 4.
- (a) Stack: the most recent action must be undone first (LIFO).
- (b) Queue: callers are answered in the order they called (FIFO).
- (c) Linked list: items can be inserted or deleted in order by changing pointers, without moving the other data.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
Which situation is best modelled by a stack?
- AThe back button of a web browser, returning to the most recently visited page first
- BDocuments sent to a shared printer, printed in the order they arrive
- CCustomers waiting on a helpline, answered in the order they called
- DKeys pressed on a keyboard, processed in the order they were typed
A stack uses ARRAY[0:5] and TopOfStack starts at −1. These operations are carried out: PUSH 5, PUSH 1, PUSH 8, POP, POP, PUSH 6, PUSH 2, POP. What is the final state?
- ATopOfStack = 1; the stack holds 5, 6 (bottom to top)
- BTopOfStack = 2; the stack holds 5, 6, 2 (bottom to top)
- CTopOfStack = 1; the stack holds 5, 1 (bottom to top)
- DTopOfStack = 4; the stack holds 5, 1, 8, 6, 2 (bottom to top)
A circular queue uses ARRAY[0:5], starting with Front = 0, Rear = −1 and Count = 0. P, Q, R, S, T are enqueued, three items are dequeued, then U and V are enqueued. At which index is V stored?
- A0
- B6
- C5
- D3
Which statement describes an abstract data type?
- AA collection of data together with a set of operations on that data
- BA data type, such as INTEGER, that is built into every programming language
- CA data type that can hold only one value at a time
- DAny data that is stored in a text file rather than in memory
A linked list is stored in two arrays, Data and Pointer:
| Index | Data | Pointer |
|---|---|---|
| 0 | Perth | 4 |
| 1 | Dakar | 3 |
| 2 | Oslo | 0 |
| 3 | Lima | 2 |
| 4 | Quito | −1 |
| 5 | −1 |
StartPointer = 1, FreeListPointer = 5, and −1 is the null pointer.
In what order are the items output when the list is traversed from the start pointer?- ADakar, Lima, Oslo, Perth, Quito
- BPerth, Dakar, Oslo, Lima, Quito
- CPerth, Quito
- DQuito, Perth, Oslo, Lima, Dakar
Using the same linked list, Oslo is deleted and its node is returned to the front of the free list:
| Index | Data | Pointer |
|---|---|---|
| 0 | Perth | 4 |
| 1 | Dakar | 3 |
| 2 | Oslo | 0 |
| 3 | Lima | 2 |
| 4 | Quito | −1 |
| 5 | −1 |
StartPointer = 1, FreeListPointer = 5, and −1 is the null pointer.
Which values change?- APointer[3] = 0, Pointer[2] = 5, FreeListPointer = 2
- BPointer[1] = 0, Pointer[2] = 5, FreeListPointer = 2
- CPointer[3] = 2, Pointer[2] = −1, FreeListPointer = 5
- DPointer[2] = 0, Pointer[3] = −1, StartPointer = 2
Quiz key
The back button must return to the page visited most recently, the last one added, so it is LIFO: a stack. Print jobs, helpline callers and a keyboard buffer must all be handled in arrival order, first in, first out, which is a queue.
5, 1, 8 are pushed (TopOfStack 2); two POPs return 8 and 1 (TopOfStack 0); 6 and 2 are pushed (TopOfStack 2); the last POP returns 2, leaving 5, 6 with TopOfStack = 1. 5, 6, 2 ignores the final POP, 5, 1 pops from the bottom as if it were a queue, and the last option ignores every POP.
P to T fill indices 0 to 4 (Rear = 4). Dequeuing P, Q and R moves Front to 3. U goes to index 5, and V to (5 + 1) MOD 6 = 0, the space P left. Index 6 does not exist in ARRAY[0:5], 5 is where U went, and 3 is the front of the queue, which still holds S.
An ADT such as a stack, queue or linked list is defined by its data and the operations on it (push, pop, enqueue, insert), independent of how it is implemented. Built-in single-value types such as INTEGER are not ADTs, and where the data is stored is irrelevant.
Start at node 1 (Dakar), then Pointer[1] = 3 (Lima), Pointer[3] = 2 (Oslo), Pointer[2] = 0 (Perth), Pointer[0] = 4 (Quito), and Pointer[4] = −1 ends the list. Perth, Dakar, Oslo, Lima, Quito is the index order of the array, Perth, Quito starts at index 0 instead of the start pointer, and the last option is the list in reverse.
Lima (node 3) points to Oslo, so it takes Oslo's pointer: Pointer[3] = 0 (Perth). Node 2 then joins the free list: Pointer[2] = the old FreeListPointer, 5, and FreeListPointer = 2. Changing Pointer[1] would make Dakar skip Lima as well. Leaving Pointer[3] = 2 keeps Oslo in the list, and the last option breaks the list after Lima and makes the deleted node the start.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.