Abstract Data Types

— Computer Science · A Level (9618) Paper 2 · Part D: Stack · Queue · Linked List —

★ Exam Tip: ADT questions are drawing / completing diagrams and "complete the steps" questions (3–6 marks each). Learn what each pointer points to and where it moves after every operation.

★ Sir's exam note: In the 2023 papers (May/June and Oct/Nov, 9618) question 3 in about six papers was on abstract data types — stack, queue and linked list all appear. Practise every one of them from past papers.

How to answer "describe" questions (e.g. 4 marks): look at the marks first — 4 marks = a detailed answer with 4 points. For adding to a queue the first point is always: check the queue is not full, then say where the End pointer moves, then what is stored.

Abstract Data Type (ADT): a collection of data and a set of operations on that data. Three ADTs: Stack · Queue · Linked List.

1. Stack

Definition: a list of items operating on the last-in-first-out (LIFO) principle. Items are added with PUSH and removed with POP. The first item added is the last removed.

TopOfStack pointer → the last item added
BottomOfStack pointer → the first item on the stack
the stack grows upwards when items are added
POP on an empty stack → error (underflow); PUSH on a full stack → can't add (overflow)

items enter and leave from the top only

worked tracestack · LIFO

Push("Taha"), Push("Ali"), Push("Amjad"), Push("Bano"), Pop(), Pop(), Push("Qasim")

Operation	Stack (bottom → top)
Push Taha	Taha
Push Ali	Taha, Ali
Push Amjad	Taha, Ali, Amjad
Push Bano	Taha, Ali, Amjad, Bano
Pop → Bano removed	Taha, Ali, Amjad
Pop → Amjad removed	Taha, Ali
Push Qasim	Taha, Ali, Qasim (top = Qasim)

questionwhy does "Papersdock" come back as "kcodsrepaP"?

Each character is pushed one by one, then all are popped. The stack is Last In First Out, so the first character added ("P") is removed last — the order is reversed.

past paperstack contents · 1 + 1 marks

Stack (bottom → top): red, blue, green, yellow.

(i) POP · PUSH('purple') · PUSH('orange') → red, blue, green, purple, orange (top)(ii) then POP · POP · PUSH('brown') · POP · PUSH('black') → red, blue, green, black (top)

(ii) step by step: POP removes orange, POP removes purple, brown is pushed then popped straight away, black is pushed.

past paper q3stack in memory locations 500–506 · 1 + 4 + 1 + 5 marks

Memory locations 500 → 505: PPP (500, BottomOfStack), NNN, ZZZ, XXX, YYY, WWW (505, TopOfStack). 506 empty.

(a)(i) maximum consecutive POPs before an error = 6 (one per item). (a)(ii) POP→Data1 · POP→Data2 · PUSH AAA · PUSH BBB · POP (discard) · POP→Data2

Step	Effect
POP → Data1	Data1 = WWW, top = 504 (YYY)
POP → Data2	Data2 = YYY, top = 503 (XXX)
PUSH AAA	504 = AAA, top = 504
PUSH BBB	505 = BBB, top = 505
POP (discard)	BBB discarded, top = 504
POP → Data2	Data2 = AAA, top = 503

Final: 500 PPP · 501 NNN · 502 ZZZ · 503 XXX ← TopOfStack · (504 AAA, 505 BBB left in memory but above the pointer) · BottomOfStack at 500 · Data1 = WWW · Data2 = AAA. Marks: BBB & AAA values · XXX→PPP unchanged · both pointers labelled · both variables.

(b)(i) Why write the stack to a text file before the program ends? So the data can be recovered / restored next time the program runs (permanently saved, not lost when the program terminates). (b)(ii) SaveStack() in five steps (max 5): ① open the text file in WRITE mode ② check there is a value on the stack ③ POP a value ④ write the value to the text file ⑤ repeat from step 2 (loop)

Alternative without POP: read the value at TopOfStack · write it · decrement ToS · repeat.

past paperstack in a 1D array of 8 elements · 3 + 5 marks

Stack (top → bottom): D1, D3, D4, D5, D2. The array is filled from the lowest index upwards and all 8 elements are available.

element 1 = D2 (bottom) … element 5 = D1 (top)

Array element	1	2	3	4	5	6–8
Data	D2	D5	D4	D3	D1	empty

TopOfStack = 5 (index of D1) · BottomOfStack = 1 (index of D2). The first item pushed (D2) is at the bottom/lowest index.

(b) Push() — complete the five steps:

① If TopOfStack = 8 (stack full) then return FALSE② Otherwise increment TopOfStack③ Use TopOfStack as an index to the array④ Set the element at this index to the value being added⑤ Return TRUE

2. Queue

Definition: a list operating on the first-in-first-out (FIFO) principle — the first item added is the first removed. Data is added at the rear using the EndPointer and removed from the front using the StartPointer. (Enqueue = add, Dequeue = remove)

Front of queue pointer → the next item to be removed
End of queue pointer → the last item added

worked tracequeue · FIFO

Enqueue("Taha"), Enqueue("Ali"), Enqueue("Amjad"), Enqueue("Bano"), Dequeue(), Dequeue(), Enqueue("Qasim")

Operation	Queue (front → rear)
4 × Enqueue	Taha, Ali, Amjad, Bano
Dequeue → Taha out	Ali, Amjad, Bano
Dequeue → Ali out	Amjad, Bano
Enqueue Qasim	Amjad, Bano, Qasim

Linear vs circular queue

start: values 5 6 7 8 9 1 −1 2 in locations 0–7; two Dequeue() move Front to 2

Linear queue full: rear (end) pointer points to the upper bound / max index — even if the front has moved on and earlier spaces are empty, adding still prints "The queue is full". Circular queue: pointers wrap around to the beginning so locations can be reused. Circular queue is full when number of items = size (or when incremented EoQ = FoQ).

past paperqueue of 10 locations (0–9) · circular · 4 + 1 + 5 marks

Front pointer → location 5 (Red); items Red 5, Green 6, Blue 7, Pink 8 (End pointer); 9 empty. Max 10 items.

(i) How Orange and Yellow are added (max 4): ① check that the queue is not full ② EoQ pointer moves to location 9 ③ Orange stored in the location referenced by EoQ ④ EoQ moves to location 0 (wrap round) ⑤ Yellow stored in the location referenced by EoQ (ii) 10 locations used; Front = 5, End = 1 → items in 5,6,7,8,9 and 0,1 = 7 data items (b) FileToQueue() (no pseudocode): ① open the file in READ mode ② loop until EOF / all lines processed ③ the loop also ends when AddToQueue() returns FALSE (queue full) ④ read a line from the file (in the loop) ⑤ pass the string to AddToQueue()

past paperprint server · circular queue with 6 spaces · 1 + 3 + 1 marks

Jobs A, B, C, D arrived in that order; Start pointer at 2nd space, End pointer at 5th space.

(i) locations 2–5 hold A, B, C, D (in arrival order); Start → A, End → D (ii) A and B complete (Start moves to C) and E, F, G, H arrive: E → location 6, then wrap: F → 1, G → 2, H → 3. Queue: locations 1–6 = F, G, H, C, D, E; Start pointer → C (4), End pointer → H (3) (iii) another job added → the queue is full → error message / the job cannot be added

The board's attempted answer wrote the jobs as A B D C — arrival order must be kept (C before D).

past paperanimal queue · 8 locations (0–7) · circular · 2 + 2 + 1 marks

Frog 0 (front), Cat 1, Fish 2, Elk 3 (end); 4–7 empty.

(i) add "Octopus": the EoQ pointer is incremented (moves to location 4); "Octopus" is stored in location 4 (ii) remove the next item into AnimalName: the value pointed to by FoQ ("Frog", location 0) is assigned to AnimalName; FoQ moves to location 1 ("Cat") (iii) front and end pointers have the same value → there is only one data item in the queue

same queue3 + 2 + 3 marks

(b)(i) Add Wasp, Bee, Mouse then remove 2 items: 4 Wasp · 5 Bee · 6 Mouse added; Front pointer → 2 (Fish), End pointer → 6 (Mouse) (Frog & Cat still sit in memory but are no longer in the queue) (ii) queue is: Elk (3, Front) … Mouse (6, End), with Ant left in 7. Remove one item (Elk) then add Dolphin and Shark → Front → 4 (Wasp); Dolphin stored in 7; Shark stored in 0 (wrap) → End pointer → 0 (Shark) (c) algorithm to move the end pointer when adding: ① increment EoQ; if incremented EoQ = FoQ → error: queue full ② otherwise store the value ③ manage wrap-around (if past the last location, set EoQ to the first)

past paperqueue implemented with 3 variables + 1D array of 8 elements · 3 + 6 marks

FrontOfQueue, EndOfQueue and NumItems (number of items); queue (front → end) = D3, D4, D1, D2, D5. Pointer variables store array indices.

Index	1	2	3	4	5	6	7	8
Array		D3	D4	D1	D2	D5

FrontOfQueue = 2 · EndOfQueue = 6 · NumItems = 5 (mark scheme accepts the items in any five consecutive locations, in order or reversed, with pointers matching D3 and D5).

(b) AddTo() — circular queue, check it is not full. Complete the six steps:

① If NumItems = 8 (queue full) then jump to step 6② Increment EndOfQueue③ If EndOfQueue = 9 then set EndOfQueue to 1 (wrap round)④ Increment NumItems⑤ Set the element at the index stored in EndOfQueue to the value being added⑥ Stop

Step 5 marking: 1 mark for "element", 1 mark for the other two terms.

3. Linked List

Definition: a data structure that stores a collection of items where each item (node) is linked to the next one using pointers.

a node = data + pointer to the next node · the Start pointer points to the first node

Ordered vs unordered: an ordered linked list keeps its elements in ascending or descending order. An unordered linked list's elements are not sorted in any particular order.

Start pointer → first node of the list · Free-list pointer → first unused node (the free list is another linked list of empty nodes)
Null pointer = end of list: accept 0 / Ø / −1 / an out-of-bounds index
implemented with two 1D arrays (Data array + Pointer array) and two variables — pointers store index numbers

past paperrepresent the linked list with arrays · 5 + 4 marks

Ptr1 = start pointer: D40 → D32 → D11 → D100 → Ø. Ptr2 = free-list pointer: F1 → F2 → F3 → F4 → Ø. Some nodes already filled in: index 1 D32 (pointer 2) · index 2 pointer 3 · index 4 D40 · index 6 F2 (pointer 7) · Free_List_Pointer = 5.

Variable	Value
Start_Pointer	4
Free_List_Pointer	5

Index	Data array	Pointer array	Which list?
1	D32	2	list → next is index 2 (D11)
2	D11	3	list → index 3 (D100)
3	D100	0	list, last node (null = 0)
4	D40	1	list, first node (Start_Pointer = 4)
5	F1	6	free list, first (Free_List_Pointer = 5)
6	F2	7	free list
7	F3	8	free list
8	F4	0	free list, last (null)

Marks: 1 for Start_Pointer + 1 for each group of rows: 2 · 3 and 4 · 5 · 7 and 8. How to read: start at Start_Pointer 4 → D40 → pointer 1 → D32 → pointer 2 → D11 → pointer 3 → D100 → pointer 0 = end.

same question(b) insert D6 between D32 and D11 · 4 marks

① Assign the data item D6 to F1 (the first free node)② Set the pointer of this node to point to D11③ Set Ptr2 to point to F2 (next free node)④ Set the pointer of D32 to point to D6

Insert a node (generally)

Check for a free node in the linked list (free list not empty)
Search for the correct position (ordered list)
Assign the value (e.g. B) to the first node in the free list
The pointer from B is changed to point to C
The pointer from A points to B
The free-list start pointer moves to point to the next free node

Order matters: set the new node's pointer first (B → C) and only then change A → B — otherwise you lose the rest of the list.

Delete a node

Search for the node you want to delete — start from the first node and follow the pointers
If it is the first node: point the start pointer to the next node in the list
If it is in the middle: change the pointer of the previous node to point to the node after the deleted one
Point the free-list pointer towards the removed node (it becomes the new first free node, pointing to the old first free node)

deleting a middle node = change the previous node's pointer

past paperunordered linked list in a 1D array of records (node: data, nextNode)

startPointer = 0 · emptyList = 5 (the free list). Records:

Index	0	1	2	3	4	5	6	7	8	9
data	1	5	6	7	2	0	0	56	0	0
nextNode	1	4	7	−1	2	6	8	3	9	−1

Reading it: list from startPointer 0 → 1 (idx 0) → 5 (idx 1) → 2 (idx 4) → 6 (idx 2) → 56 (idx 7) → 7 (idx 3) → −1 (end). Free list from emptyList 5 → idx 5 → 6 → 8 → 9 → −1. Here −1 is the null pointer and the list is unordered (1, 5, 2, 6, 56, 7). (The slide shows the table; the sub-questions asked about it were not on the page I could see.)

✓ Quick Recap — Part D

ADT = data + operations · Stack, Queue, Linked list
Stack: LIFO · PUSH / POP · TopOfStack, BottomOfStack · full if ToS = max · empty if no items · "reverse" = LIFO
Queue: FIFO · add at end (EoQ ↑), remove at front (FoQ ↑) · circular: wrap round (after last index → first) · full when NumItems = size
Same front & end pointer ⇒ exactly one item in the queue
Linked list: node = data + pointer · Start pointer + Free-list pointer · null = 0 / Ø / −1
Insert: take first free node → set its pointer → relink previous node → move free pointer · Delete: relink previous node (or start pointer) → add node to free list