2.2.4 Abstract Data Types — Stack, Queue & Linked List
Cambridge 9618 · International A Level Computer Science · ~15 min read
Notes
Video
Slides
Quiz
Worksheet
Abstract Data Types (ADTs)
An Abstract Data Type (ADT) defines a data structure by the operations it supports, not by how it is implemented internally. You use the interface (the operations) without needing to know the underlying code.
Cambridge 9618 requires knowledge of three ADTs: Stack, Queue, and Linked List.
Stack
A stack is a Last In, First Out (LIFO) structure. The last item added is the first to be removed — like a pile of plates.
"Bob" ← Top (push/pop here)
"Alice"
"Zara"
Items added/removed only from the top. Access is sequential from top.
Stack Operations
Push(item)
Add item to the top of the stack. Error if stack is full (overflow).
Pop()
Remove and return the top item. Error if stack is empty (underflow).
Peek() / Top()
Return the top item without removing it. Does not modify the stack.
isEmpty()
Returns TRUE if the stack has no items.
isFull()
Returns TRUE if the stack has reached maximum capacity.
Stack Using an Array — Pseudocode
A stack can be implemented using an array with a Top pointer (an integer tracking the index of the top item):
// Stack initialisation (array size 5, Top = 0 means empty) DECLARE Stack : ARRAY[1:5] OF STRING DECLARE Top : INTEGER
Top ← 0
// Push operation PROCEDURE Push(item : STRING) IF Top = 5THEN
OUTPUT "Stack overflow" ELSE
Top ← Top + 1
Stack[Top] ← item ENDIF ENDPROCEDURE
// Pop operation FUNCTION Pop() RETURNS STRING IF Top = 0THEN
OUTPUT "Stack underflow" ELSE DECLARE item : STRING
item ← Stack[Top]
Top ← Top - 1 RETURN item ENDIF ENDFUNCTION
Real-world Uses of Stacks
Undo/redo in text editors — each action pushed onto a stack
Browser back/forward buttons
Call stack when functions call other functions (return addresses)
// Dequeue FUNCTION Dequeue() RETURNS INTEGER IF Front > Rear THEN
OUTPUT "Queue empty" ELSE DECLARE item : INTEGER
item ← Queue[Front]
Front ← Front + 1 RETURN item ENDIF ENDFUNCTION
Real-world Uses of Queues
Print spooler — documents printed in order they were sent
CPU task scheduling — processes wait in a queue
Keyboard buffer — key presses buffered and processed in order
Messaging systems / network packet delivery
Linked List
A linked list is a dynamic data structure where each element (node) stores a data value and a pointer to the next node. Unlike arrays, linked lists do not need contiguous memory — they can grow and shrink at runtime.
HEAD→
10
→
25
→
47
→
63
NIL
Each node has two parts: data (the stored value) and pointer/next (the address of the next node). The last node points to NIL (or null) indicating the end of the list. A Head variable stores the address of the first node.
Linked List Operations
Operation
Description
Complexity
Traverse
Visit every node from Head to NIL
O(n)
Insert at head
New node points to current Head; Head updated to new node
O(1)
Insert at tail
Traverse to last node; last node pointer updated to new node
O(n)
Insert at position
Traverse to position; update pointers to link new node in
O(n)
Delete node
Update previous node's pointer to skip deleted node
O(n)
Search
Traverse from Head comparing each data value
O(n)
Traversing a Linked List — Pseudocode
// Assume nodes stored in parallel arrays: Data[] and Next[] // Head stores index of first node; -1 = NIL (empty/end) DECLARE current : INTEGER
current ← Head WHILE current <> -1DO
OUTPUT Data[current]
current ← Next[current] ENDWHILE
Stack vs Queue vs Linked List — Comparison
Feature
Stack
Queue
Linked List
Order
LIFO
FIFO
Positional (by pointer chain)
Add/Remove
Top only
Rear/Front
Any position
Size
Fixed (array) or dynamic
Fixed (array) or dynamic
Dynamic
Random access
No
No
No (must traverse)
Example use
Undo, call stack
Print queue, task scheduler
Music playlist, OS free memory list
Exam tip: Cambridge 9618 often asks you to trace through stack/queue operations and show the state of the structure after each. Always show the pointer (Top/Front/Rear) value clearly. For LIFO vs FIFO, remember: Stack = "last plate on a pile", Queue = "bus stop line". Linked list questions often ask about insertion — always update the pointer of the previous node first, THEN update Head/other pointers.
⚠️ Common Mistakes
Confusing stack (LIFO) with queue (FIFO) — remember: Stack = plate pile, Queue = bus stop
Stack overflow: pushing when Top already = max size. Always check isFull before pushing
Stack underflow: popping when Top = 0. Always check isEmpty before popping
In a linked list, forgetting to update the previous node's pointer when inserting — this breaks the chain
Treating a linked list like an array — you cannot directly access node 5 without traversing from Head
Not ending the linked list with NIL — every list must have a terminal pointer
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.2.4 Abstract Data Types
8 questions · Cambridge 9618 standard
Q1A stack contains the values [3, 7, 12] from bottom to top. Show the state of the stack after: Push(5), Pop(), Push(2), Peek(). State the final Top value and the Peek result.[4]
✅ Mark scheme
After Push(5): [3,7,12,5] Top=4 [1]; After Pop(): [3,7,12] Top=3 (returns 5) [1]; After Push(2): [3,7,12,2] Top=4 [1]; Peek() returns 2 (Top item), stack unchanged, Top remains 4 [1].
Q2Explain the difference between overflow and underflow in the context of a stack.[2]
✅ Mark scheme
Overflow occurs when Push is attempted on a full stack (Top = max size) [1]; underflow occurs when Pop/Peek is attempted on an empty stack (Top = 0) [1].
Q3A queue contains [A, B, C] with Front=1, Rear=3. Show the state after: Enqueue(D), Dequeue(), Enqueue(E). State the final Front, Rear, and contents.[4]
Q4State two advantages of a linked list over an array for storing a collection of data that changes size frequently.[2]
✅ Mark scheme
Any 2 of: Linked lists are dynamic — they grow/shrink at runtime, no fixed maximum size [1]; inserting/deleting a node only requires updating pointers — no shifting of elements [1]; no wasted memory from unused array slots [1].
Q5Write pseudocode to push items 10, 20, 30 onto a stack, then pop and output each item. State the order in which items are output.[4]
Q6Describe how insertion at the head of a singly-linked list is performed. Why is this O(1) while insertion at a specific position is O(n)?[3]
✅ Mark scheme
Set new node's pointer to current Head [1]; update Head to point to new node [1] — no traversal needed so always 2 steps = O(1). Insertion at position requires traversing from Head to the desired location, which takes up to n steps for n nodes = O(n) [1].
Q7Write a recursive FUNCTION Power(Base : INTEGER, Exp : INTEGER) RETURNS INTEGER that computes Base^Exp. Include the base case and recursive case. Then trace the call Power(3, 4), showing each recursive call and return value.[6]
Q8Identify three conditions that must be met for a recursive algorithm to terminate correctly. Explain what a stack overflow is in the context of recursion, and state one way to mitigate the risk of stack overflow in a recursive program.[5]
✅ Mark scheme
Condition 1: there must be a base case — a terminating condition that does not make a further recursive call [1]; Condition 2: each recursive call must progress towards the base case (reducing the problem size) [1]; Condition 3: the base case must be reached for all valid inputs — infinite recursion must not be possible [1]; Stack overflow: each recursive call adds a new stack frame to the call stack; if recursion is too deep, the call stack runs out of memory, causing a stack overflow error / the program crashes [1]; Mitigation: use tail recursion (if the language optimises it) or convert the algorithm to an iterative solution using an explicit stack, avoiding call-stack growth [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 7
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.2.4 Abstract Data Types
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1A stack is described as LIFO. What does LIFO mean?
Q2Which operation removes and returns an item from the top of a stack?
Q3In a queue, where are new items added?
Q4What is stored in each node of a singly-linked list?
Q5A stack has Top=3 and max size 5. An item is pushed. What is Top now?
Section B — Short Answer [5 marks]
Q6State what FIFO means and give one real-world example of a queue data structure.
Mark schemeFIFO = First In, First Out [1]; any valid example: print spooler, CPU scheduling, keyboard buffer, messaging system [1].
Q7A linked list uses a Head pointer. What does Head store, and what does NIL indicate?
Mark schemeHead stores the address/index of the first node in the list [1]; NIL indicates the end of the list — the last node's pointer is NIL/null to show there is no next node [1].
Q8Explain what stack overflow is and when it occurs.
Mark schemeStack overflow occurs when a Push operation is attempted on a full stack [1] — i.e., when Top equals the maximum capacity of the stack array [1].
Q9Give one advantage of a linked list over an array for storing data.
Mark schemeAny one of: Linked list is dynamic so it can grow and shrink at runtime without a fixed size [1]; insertion/deletion only requires updating pointers, no shifting of elements [1]; no wasted memory from empty slots [1].
Q10Items A, B, C are enqueued in that order. Then Dequeue() is called twice. What item is now at the front of the queue?
Mark schemeA is dequeued first (FIFO), then B. C is now at the front [1]. Award full mark for C with reasoning shown.