AQA 7517 4.2.1.4: Abstract data types/data structures
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
When you press undo, the last thing you did is the first thing to be taken back. That rule, last in first out, is a stack, and it is the first abstract data type in this module. In this lesson BugBot keeps a stack of its moves, so it can undo them one at a time and drive home.
- Abstract data types
- Static and dynamic structures
- The stack
- Tracing a stack
- Undoing moves
- Where stacks are used
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A3.2 Abstract data types and stacks Data structures
ADTs, static and dynamic structures, and a stack with a top pointer: an undo stack for the robot's moves. - A3.3 Queues: linear, circular and priority Data structures
Front and rear pointers, wrapping round with MOD, and priority queues: a command queue for the robot. - A3.4 Linked lists Data structures
Nodes and pointers, the free list, and traversing, inserting and deleting: a route of waypoints. - A3.5 Hash tables Data structures
Hashing functions, collisions, rehashing by probing, chaining and load factor: finding markers fast. - A3.6 Dictionaries Data structures
Keys and values, dictionaries built on hash tables, and information retrieval: commands looked up by name. - A3.7 Vectors Data structures
Vectors as lists, functions and arrows; addition, scaling, dot product and convex combination, on the robot's position. - A3.9 Project: mission control Data structures
A mission read from a file into a circular queue, moves looked up in a dictionary, position tracked as a vector, and an undo stack to…
Try it on a robot
The task from A3.2 Abstract data types and stacks, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.2.1.4 and is not endorsed by the board.