The shape of the lesson
By the end of the lesson, learners can
- Stacks and queues in code: In the lab, fill the circular queue, dequeue a few items and enqueue again: the rear pointer wraps round to index 0.
- Linked lists in code: In the lab, insert and delete items and watch only the pointers change.
- Trees, dictionaries and graphs: In the lab, insert a value into the binary tree and watch the comparisons from the root: left if smaller, right if larger or equal, until a null pointer is found.
- Insert: check for full (free pointer null / count = size), then take a node and set the pointers.
- Delete: check for empty, then reconnect around the item and return the node to the free list.
- Circular queue: move pointers with
(Pointer + 1) MOD Sizeand keep a count. - Binary tree: from the root, smaller goes left, otherwise right, until a null pointer.
One picture every idea returns to
An abstract data type (ADT) is defined by its data and its operations, not by how it is stored. A stack (push, pop) needs an array and a top pointer; a circular queue (enqueue, dequeue) needs front and rear pointers that wrap round with MOD; a linked list needs an array of records with a start pointer, a free list pointer and a null pointer (−1) at the end; a binary search tree adds a left and a right pointer to each node, smaller values to the left. A dictionary stores key-value pairs, and a graph is a set of vertices joined by edges. ADTs can be built from other ADTs, for example a queue from two stacks.
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, Write the operations.. At A Level you must write the algorithms that make each abstract data type work: insert into and delete from a stack, a queue and a linked list, and insert into and find in a binary tree. 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 and queues in code | In the lab, fill the circular queue, dequeue a few items and enqueue again: the rear pointer wraps round to index 0. Project tab 2 of the lab (Circular queue) and let a student drive it while the class predicts. Model the worked example Trace the circular queue on the board, one line at a time. Your turn: A queue is built from two stacks, InStack and OutStack. Enqueue pushes onto InStack. Dequeue pops from OutStack, but if OutStack is empty it first pops every item from InStack and pushes it onto OutStack. Trace Enqueue A, B, C; Dequeue; Enqueue D; then Dequeue three times. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Linked lists in code | In the lab, insert and delete items and watch only the pointers change. 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 Delete from the middle on the board, one line at a time. Your turn: Start again from the table. Write the steps (in words or pseudocode) to insert Abe at the start of the list, and give the new values of StartPointer and FreeListPointer. | Pairs |
| 21 to 30 min | Teach and check: Trees, dictionaries and graphs | In the lab, insert a value into the binary tree and watch the comparisons from the root: left if smaller, right if larger or equal, until a null pointer is found. Project tab 4 of the lab (Binary tree) and let a student drive it while the class predicts. Model the worked example Insert into the tree on the board, one line at a time. Your turn: After those two inserts, search the tree for 48. Which values are compared, and how does the search end? | Mix-Pair-Share |
| 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, 26 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 Trees, dictionaries and graphs, 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.
Mix-Pair-Share
Students mix around the room until you call pair; they pair with the nearest classmate, discuss the prompt, then mix again. Three prompts of rising difficulty, three different partners.
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 |
|---|---|
| In a circular queue, write (RearPointer + 1) MOD 6, not RearPointer + 1. | Without MOD the pointer runs past index 5 even though spaces at the front are free. |
| Deleting the first node is a special case: there is no previous node, so the start pointer must change. | Code that only updates List[Previous].Pointer fails for it. |
| When inserting into a tree or a linked list, take the node from the free list and update the free pointer before setting the new node's own pointers, or the rest of the free list is lost. | Return to Trees, dictionaries and graphs: ask a pair to state the correct version and show it on the lab before moving on. |
Stacks, queues, linked lists and binary trees: worksheet
6 questions, 26 marks. Written in the style of the papers; no past paper question is reproduced.
Using the record type TreeNode and the global variables in this lesson, write pseudocode for a function FindNode(SearchItem : INTEGER) RETURNS INTEGER that returns the index of the node holding SearchItem, or −1 if it is not in the tree.
An empty binary search tree uses nodes 0 to 9 in order from the free list. The values 40, 25, 60, 10, 30, 55, 75 are inserted in that order. Draw the tree and give the LeftPointer and RightPointer of nodes 0 and 1.
A circular queue uses Queue : ARRAY[0:9] OF STRING, FrontPointer, RearPointer and NumberInQueue. Write pseudocode for a procedure Enqueue(NewItem : STRING) that adds an item, or outputs an error message if the queue is full.
Using the linked list table in this lesson (StartPointer = 1, FreeListPointer = 2), state every value that changes when (a) DeleteItem("Ava") is run on the original table (b) DeleteItem("Eli") is run on the original table.
A delivery company wants to store the towns it serves and the roads between them, with the driving time for each road. Identify a suitable ADT, describe its key features and justify the choice.
Explain how a queue can be implemented using two stacks.
Answer key and marking notes
- Function header and
ENDFUNCTION; local Current initialised to RootPointer. - Loop while Current is not the null pointer (−1).
- If
Tree[Current].Data = SearchItem, return Current (or set a flag and exit the loop). - If SearchItem is less than
Tree[Current].Data, Current ←Tree[Current].LeftPointer. - Otherwise Current ←
Tree[Current].RightPointer. - Return −1 after the loop when the item is not found.
- 40 is the root (node 0); 25 (node 1) left of 40; 60 (node 2) right of 40.
- 10 (node 3) left of 25; 30 (node 4) right of 25; 55 (node 5) left of 60; 75 (node 6) right of 60.
- Node 0: LeftPointer 1, RightPointer 2.
- Node 1: LeftPointer 3, RightPointer 4.
- Procedure header with STRING parameter and
ENDPROCEDURE. - Check
NumberInQueue = 10; output an error message if full. - Otherwise
RearPointer ← (RearPointer + 1) MOD 10. Queue[RearPointer] ← NewItem.NumberInQueue ← NumberInQueue + 1.
- (a) Ava is the first node, so StartPointer ← List[1].Pointer = 4.
- (a) List[1].Pointer ← 2 and FreeListPointer ← 1.
- (b) Previous is Dan (node 6), so List[6].Pointer ← List[3].Pointer = −1.
- (b) List[3].Pointer ← 2 and FreeListPointer ← 3.
- A graph.
- Towns are vertices (nodes); roads are edges (arcs) joining pairs of vertices.
- Edges are weighted with the driving time (and may be directed for one-way roads).
- Justification: towns can be connected in any pattern, including cycles, which a tree or list cannot represent; algorithms can then find the quickest route.
- Enqueue pushes the new item onto the first (input) stack.
- Dequeue pops from the second (output) stack.
- If the output stack is empty, first pop every item from the input stack and push it onto the output stack, which reverses the order so the oldest item is on top (first in, first out).
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.
A stack is held in Stack : ARRAY[0:7] OF INTEGER with TopPointer = −1 when empty. Push stores at TopPointer + 1; Pop returns Stack[TopPointer] and then decreases TopPointer. Starting empty, these operations run:
CALL Push(5) CALL Push(8) OUTPUT Pop() CALL Push(3) CALL Push(6) OUTPUT Pop() OUTPUT Pop()What is output, and what is TopPointer at the end?
- A8, 6, 3 and TopPointer = 0
- B5, 8, 3 and TopPointer = 0
- C8, 6, 3 and TopPointer = 1
- D8, 3, 6 and TopPointer = 0
A circular queue uses Queue : ARRAY[0:5], FrontPointer starting at 0, RearPointer starting at −1 and NumberInQueue starting at 0. Enqueue outputs "Queue full" if NumberInQueue = 6; otherwise it does RearPointer ← (RearPointer + 1) MOD 6 and stores the item. Starting empty: Enqueue 1, 2, 3, 4, 5, 6; Dequeue twice; then Enqueue 7, 8, 9. What is the final state?
- AFrontPointer = 2, RearPointer = 1, and 9 is rejected as the queue is full
- BFrontPointer = 2, RearPointer = 2, and 9 overwrites 3 in index 2
- CFrontPointer = 2, RearPointer = 8, and 9 is stored in index 8
- DFrontPointer = 0, RearPointer = 1, and 9 is rejected as the queue is full
A linked list is stored in the array below. StartPointer = 3 and FreeListPointer = 1; −1 is the null pointer.
| Index | Data | Pointer |
|---|---|---|
| 0 | Kim | 2 |
| 1 | 5 | |
| 2 | Lee | 4 |
| 3 | Ali | 6 |
| 4 | Raj | −1 |
| 5 | −1 | |
| 6 | Fay | 0 |
- AAli, Fay, Kim, Lee, Raj
- BKim, Lee, Ali, Raj, Fay
- CFay, Kim, Lee, Raj
- DAli, Kim, Lee, Raj, Fay
Which statement about building one ADT from another is correct?
- AA queue can be built from two stacks
- BA stack can only be built from a binary tree
- CA dictionary cannot be built from arrays
- DA linked list must be built from a queue
Using the table below (StartPointer = 3, FreeListPointer = 1), the DeleteItem procedure from the lesson removes "Ali" and returns its node to the front of the free list.
| Index | Data | Pointer |
|---|---|---|
| 0 | Kim | 2 |
| 1 | 5 | |
| 2 | Lee | 4 |
| 3 | Ali | 6 |
| 4 | Raj | −1 |
| 5 | −1 | |
| 6 | Fay | 0 |
- AStartPointer becomes 6, List[3].Pointer becomes 1 and FreeListPointer becomes 3
- BList[6].Pointer becomes 3 and FreeListPointer becomes 3; StartPointer stays 3
- CStartPointer becomes 6; List[3].Pointer and FreeListPointer do not change
- DStartPointer becomes 1, List[3].Pointer becomes 6 and FreeListPointer becomes 3
These values are inserted, in this order, into an empty binary search tree (smaller values go left, others go right): 40, 25, 60, 30, 10, 55, 70, 35. The tree is then searched for 33. Which values are compared, and what is the result?
- A40, 25, 30, 35, then not found
- B40, 25, 30, then not found
- C10, 25, 30, 35, then not found
- D40, 60, 55, then not found
Quiz key
Push 5, Push 8; Pop returns 8. Push 3, Push 6; Pop returns 6, then Pop returns 3. Only 5 is left, in Stack[0], so TopPointer = 0. 5, 8, 3 treats the stack as a first in, first out queue, TopPointer = 1 forgets the last Pop, and 8, 3, 6 pops the older of the two items first.
Six enqueues fill indices 0 to 5 (RearPointer = 5). Two dequeues remove 1 and 2, so FrontPointer = 2 and four items remain. 7 goes to (5 + 1) MOD 6 = 0 and 8 to index 1, making six items again, so Enqueue 9 finds NumberInQueue = 6 and outputs Queue full. Overwriting index 2 ignores the full check, index 8 forgets MOD and is outside the array, and FrontPointer does not return to 0 when items are added.
Index 3 (Ali) points to 6 (Fay), which points to 0 (Kim), then 2 (Lee), then 4 (Raj), whose pointer is −1. Kim, Lee, Ali, Raj, Fay is index order, which ignores the pointers. Fay, Kim, Lee, Raj starts at Ali's pointer and misses the first node. Ali, Kim, Lee, Raj, Fay jumps from Ali to index 0 instead of following its pointer, 6.
Pushing onto one stack and, when needed, moving every item onto a second stack reverses the order twice, so items leave first in, first out: a queue. A stack is usually built from an array or a linked list, a dictionary can be built from parallel arrays, an array of records or a hash table, and a linked list is built from an array of records with pointers.
Ali is found with Previous = null, so StartPointer ← List[3].Pointer = 6. The freed node goes to the front of the free list: List[3].Pointer ← FreeListPointer (1), then FreeListPointer ← 3. Changing List[6].Pointer treats Ali as a middle node and leaves the list still starting at the deleted node. Leaving the free list alone loses node 3 for ever. StartPointer = 1 would make the list begin at an empty free node.
35 is placed as the right child of 30 (35 < 40, 35 > 25, 35 > 30). Searching for 33: 33 < 40 go left to 25; 33 > 25 go right to 30; 33 > 30 go right to 35; 33 < 35 go left, which is null, so 33 is not in the tree after 4 comparisons. Stopping at 30 forgets the node 35, 10, 25, 30, 35 is a linear search of the sorted values, and 40, 60, 55 goes right at the root although 33 is smaller than 40.
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.