An abstract data type is defined by what you can do with it, not by how it is stored. Stacks, queues and linked lists are three ADTs you must be able to use, justify and build from arrays and pointers. You add, edit and delete data by hand and explain each step.
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.
Fig. 1: a stack, a queue and a linked list (the stack after PUSH 4, PUSH 9, PUSH 2, POP, PUSH 7)
Section 01
Stacks: last in, first out.
In the lab, push a few values, then pop them. Watch TopOfStack: it is the only pointer a stack needs. In the lab and in this lesson arrays start at index 0, so an empty stack has TopOfStack = −1. (With a lower bound of 1, an empty stack has TopOfStack = 0.)
Push: if TopOfStack is already the upper bound, report stack overflow; otherwise add 1 to TopOfStack and store the item there.
Pop: if TopOfStack is −1, report stack underflow; otherwise return the item at TopOfStack and subtract 1. The value stays in the array but is no longer part of the stack.
Implementation: a 1D array plus one integer variable, the top of stack pointer. The bottom of the stack is fixed at the lower bound.
Uses: undo in an editor, the back button of a browser, storing return addresses when procedures are called, recursion, reversing a sequence.
Worked example Trace a stack
Stack is ARRAY[0:5] and TopOfStack starts at −1. Trace PUSH 4, PUSH 9, PUSH 2, POP, PUSH 7, POP, POP.
PUSH 4, 9, 2: TopOfStack goes 0, 1, 2 and the stack holds 4, 9, 2 (bottom to top).
POP returns 2; TopOfStack = 1.
PUSH 7: TopOfStack = 2 and 7 overwrites the old 2 in Stack[2] (this is the state in Fig. 1).
POP returns 7 (TopOfStack 1); POP returns 9 (TopOfStack 0).
Answer:
Operation
TopOfStack
Stack (bottom to top)
Returned
start
−1
empty
PUSH 4
0
4
PUSH 9
1
4, 9
PUSH 2
2
4, 9, 2
POP
1
4, 9
2
PUSH 7
2
4, 9, 7
POP
1
4, 9
7
POP
0
4
9
Examiner trap
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.
Section 02
Queues: first in, first out.
In the lab, fill the queue, take two items off the front and try to add more. In a linear queue the spaces at the front are wasted; switch to the circular queue and the rear pointer wraps round to reuse them.
Pointers: FrontPointer (the next item to leave) and RearPointer (the last item added), plus a count NumberInQueue. An empty queue in a 0-based array has Front = 0, Rear = −1, Count = 0.
Enqueue: if Count equals the array size, the queue is full; otherwise move Rear on one place, store the item and add 1 to Count.
Dequeue: if Count = 0, the queue is empty; otherwise return the item at Front, move Front on one place and subtract 1 from Count.
Circular: "move on one place" wraps round from the last index to the first, for a 5-element array Rear ← (Rear + 1) MOD 5.
Uses: print jobs waiting for a shared printer, a keyboard buffer, processes waiting for the processor, data buffered for streaming.
Worked example Trace a circular queue
Queue is ARRAY[0:4] with Front = 0, Rear = −1, Count = 0. Trace ENQUEUE A, B, C, D, then DEQUEUE twice, then ENQUEUE E, F.
Enqueue A, B, C, D: Rear goes 0, 1, 2, 3 and Count becomes 4.
Dequeue returns A (Front 1), then B (Front 2); Count is 2.
Enqueue E: Rear = 4, Count = 3.
Enqueue F: Rear = (4 + 1) MOD 5 = 0, so F goes into Queue[0], the space A left. Count = 4.
Answer: Front = 2, Rear = 0, Count = 4; the queue in order is C, D, E, F (indices 2, 3, 4, 0)
Your turn
Continue: ENQUEUE G, then ENQUEUE H. What happens?
G goes into index 1 (Rear = 1) and Count = 5, so the queue is full. H is rejected: the queue is full.
Examiner trap
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).
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
Which ADT works on a last in, first out basis?
Quick check+10 XP
In the lab, POP is pressed when the stack is empty. What is reported?
Quick check+10 XP
A circular queue uses ARRAY[0:5]. RearPointer is 5 and the queue is not full. Where is the next item stored?
Quick check+10 XP
What does the pointer of the last node in a linked list hold?
Section 03
Linked lists.
In the lab, insert and delete items and watch only the pointers change: no data is moved. The same list can be written as two arrays (or one array of records with Data and Pointer fields), with −1 as the null pointer.
Index
Data
Pointer
0
Kiwi
3
1
Apple
4
2
5
3
Mango
−1
4
Fig
0
5
−1
StartPointer = 1, FreeListPointer = 2. Following the pointers from node 1: Apple → Fig (4) → Kiwi (0) → Mango (3) → null, so the list is in alphabetical order even though the array is not. The free list is node 2 → node 5 → null.
Insert: take the first node from the free list, store the data, find the node it must follow, copy that node's pointer into the new node, then point that node at the new node.
Delete: point the previous node (or the start pointer) at the deleted node's successor, then return the freed node to the free list.
Edit: traverse to the node and change its data (for an ordered list, delete and reinsert if the order would change).
Why use one: insertion and deletion only change pointers, so no data is shifted. But there is no direct access: you must follow the pointers from the start, and the pointers take extra storage.
Worked example Insert into an ordered list
Using the table above, insert Lime so that the list stays in alphabetical order. Give the new pointer values.
Take node 2 from the free list; FreeListPointer becomes Pointer[2] = 5. Store Data[2] = Lime.
Traverse from the start: Apple, Fig, Kiwi, then Mango, which comes after Lime. So Lime goes after Kiwi (node 0).
New node first: Pointer[2] = Pointer[0] = 3 (Lime points to Mango).
Then Pointer[0] = 2 (Kiwi points to Lime).
Answer: Pointer[0] = 2, Pointer[2] = 3; StartPointer = 1, FreeListPointer = 5. The list is Apple, Fig, Kiwi, Lime, Mango
Your turn
Start again from the original table and delete Fig. Which pointers change?
Apple (node 1) must skip Fig: Pointer[1] = Pointer[4] = 0. Node 4 joins the free list: Pointer[4] = 2 and FreeListPointer = 4. StartPointer stays 1.
Examiner trap
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.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to AS Paper 1 and Paper 2 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Which describes an abstract data type?
Exam style+20 XP
Which situation is best modelled by a queue?
Exam style+20 XP
An empty stack has the operations PUSH 3, PUSH 8, POP, PUSH 5, PUSH 1, POP. What does it hold, bottom to top?
Exam style+20 XP
Why might a linked list be used instead of an array for a list kept in order?
Skill unlocked
Stacks, queues and linked lists, mastered.
This skill is now recorded on your profile. Keep the chain going.