2.4.3 ADT Implementation — Stack & Queue in Pseudocode
Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
Abstract vs Concrete: What and How
An abstract data type (ADT) defines what operations are available — not how they are implemented. When you implement an ADT in pseudocode, you choose a concrete data structure (typically an array) and write procedures/functions to carry out each operation.
Abstract level
Concrete level
Stack — LIFO store with Push, Pop, Peek
Array + Top pointer + integer counter
Queue — FIFO store with Enqueue, Dequeue
Array + Front/Rear pointers + size counter
Stack Implementation Using an Array
A stack stores items in Last In, First Out (LIFO) order. Only the top element is directly accessible. We implement it using a fixed-size array and a Top pointer (integer index).
State Variables
CONSTANT MAX_SIZE = 5 DECLARE Stack : ARRAY[1:MAX_SIZE] OF INTEGER DECLARE Top : INTEGER
Top ← 0// 0 means empty; Top points to current top element
Stack state: Top = 3, pushed 10, 20, 30
30index 3 ← Top
20index 2
10index 1
—index 4 (empty)
—index 5 (empty)
Key rules
Top = 0 → stack is EMPTY
Top = MAX_SIZE → stack is FULL
Push: increment Top first, then store
Pop: read Stack[Top] first, then decrement Top
Peek: read Stack[Top] without changing Top
Push (add to stack)
PROCEDURE Push(item : INTEGER) IF Top = MAX_SIZE THEN
OUTPUT "Stack overflow — stack is full" ELSE
Top ← Top + 1// increment first
Stack[Top] ← item // then store at new Top ENDIF ENDPROCEDURE
Pop (remove from stack)
FUNCTION Pop() RETURNS INTEGER IF Top = 0THEN
OUTPUT "Stack underflow — stack is empty" RETURN -1// error sentinel ELSE DECLARE item : INTEGER
item ← Stack[Top] // read top element first
Top ← Top - 1// then decrement RETURN item ENDIF ENDFUNCTION
Peek and isEmpty
FUNCTION Peek() RETURNS INTEGER IF Top = 0THEN RETURN -1// empty — nothing to peek ELSE RETURN Stack[Top] // Top unchanged ENDIF ENDFUNCTION
FUNCTION isEmpty() RETURNS BOOLEAN RETURN (Top = 0) ENDFUNCTION
Stack Trace — Worked Example
Starting with empty stack (Top=0, MAX_SIZE=4). Trace each operation:
Operation
Check
Action
Top after
Stack state
Push(5)
Top≠4
Top←1; Stack[1]←5
1
[5,_,_,_]
Push(12)
Top≠4
Top←2; Stack[2]←12
2
[5,12,_,_]
Pop()
Top≠0
item←Stack[2]=12; Top←1
1
[5,_,_,_] returns 12
Peek()
Top≠0
Return Stack[1]=5
1
[5,_,_,_] no change
Push(3)
Top≠4
Top←2; Stack[2]←3
2
[5,3,_,_]
Queue Implementation Using an Array
A queue stores items in First In, First Out (FIFO) order. We implement it using a fixed-size array and two pointers: Front and Rear. A size counter tracks how many items are stored.
State Variables
CONSTANT MAX_SIZE = 5 DECLARE Queue : ARRAY[1:MAX_SIZE] OF INTEGER DECLARE Front, Rear, Size : INTEGER
Front ← 1// start of queue
Rear ← 0// last item added (0 = nothing added yet)
Size ← 0// number of items currently in queue
Queue state: Front=2, Rear=4, Size=3 → items at indices 2,3,4
—
idx 1
A
Front(2)
B
idx 3
C
Rear(4)
—
idx 5
Enqueue (add to rear)
PROCEDURE Enqueue(item : INTEGER) IF Size = MAX_SIZE THEN
OUTPUT "Queue is full" ELSE
Rear ← Rear + 1
Queue[Rear] ← item
Size ← Size + 1 ENDIF ENDPROCEDURE
Dequeue (remove from front)
FUNCTION Dequeue() RETURNS INTEGER IF Size = 0THEN
OUTPUT "Queue is empty" RETURN -1 ELSE DECLARE item : INTEGER
item ← Queue[Front] // take from front
Front ← Front + 1// advance front pointer
Size ← Size - 1 RETURN item ENDIF ENDFUNCTION
Queue Trace — Worked Example
Operation
Action
Front
Rear
Size
Queue
Enqueue(10)
Rear←1; Queue[1]←10; Size←1
1
1
1
[10,_,_]
Enqueue(20)
Rear←2; Queue[2]←20; Size←2
1
2
2
[10,20,_]
Dequeue()
item←Queue[1]=10; Front←2; Size←1; return 10
2
2
1
[_,20,_]
Enqueue(30)
Rear←3; Queue[3]←30; Size←2
2
3
2
[_,20,30]
Dequeue()
item←Queue[2]=20; Front←3; Size←1; return 20
3
3
1
[_,_,30]
Exam tip — always check before Push/Enqueue and Pop/Dequeue: Cambridge mark schemes always give a mark for checking whether the stack/queue is full (before adding) or empty (before removing). Never write Push or Enqueue without first checking for overflow; never write Pop or Dequeue without first checking for underflow.
Push order matters: Always increment Top before storing the item — i.e. Top ← Top + 1 then Stack[Top] ← item. If you decrement after popping, always read the value first: item ← Stack[Top] then Top ← Top - 1.
⚠️ Common Mistakes
Forgetting the overflow/underflow check — always check before Push and Pop
Decrementing Top before reading the value in Pop — read Stack[Top] first
Incrementing Top after storing in Push — increment Top first, then store
Using Top=0 to mean "first item is at index 0" — in 9618, Top=0 means EMPTY; first Push sets Top=1
Queue Dequeue: forgetting to update Front after removing (and forgetting to decrement Size)
Confusing which end items enter/leave: Queue — Enqueue at Rear, Dequeue at Front
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.4.3 ADT Implementation
8 questions · Cambridge 9618 standard
Q1A stack is implemented using an array Stack[1:4] and a Top pointer initialised to 0. Trace the following operations: Push(7), Push(3), Pop(), Push(9), Peek(). Show Top and the stack contents after each step.[5]
Q2Write pseudocode for a PROCEDURE called Push that adds a character to a stack implemented as Stack[1:MAX_SIZE] with Top pointer. Include an overflow check.[5]
✅ Mark scheme
PROCEDURE Push(item : CHAR) [1]; IF Top = MAX_SIZE THEN [1]; OUTPUT "Stack overflow" [1]; ELSE; Top ← Top + 1 [1]; Stack[Top] ← item [1]; ENDIF; ENDPROCEDURE.
Q3Describe the difference between Pop() and Peek() for a stack. Why is Peek useful?[3]
✅ Mark scheme
Pop() returns the top element AND removes it (decrements Top) [1]; Peek() returns the top element but does NOT change Top — the element remains on the stack [1]; Peek is useful when you need to inspect the top item without removing it, e.g. to decide whether to pop based on its value [1].
Q4A queue uses Queue[1:3], Front=1, Rear=0, Size=0. Trace: Enqueue(4), Enqueue(8), Dequeue(), Enqueue(15). Show Front, Rear, Size, and queue contents after each operation.[5]
Q5State two checks that must be made before a Dequeue operation and explain what happens in each case.[4]
✅ Mark scheme
Check 1: Size = 0 (or queue is empty) [1]; if so, output an error / underflow message and return without dequeuing [1]. Check 2: (Some implementations) Confirm Front ≤ Rear or Size > 0 [1]; the operation proceeds only if there is at least one item to remove [1].
Q6A student writes this pseudocode for Pop: Top ← Top - 1; RETURN Stack[Top]. Identify and correct the error.[2]
✅ Mark scheme
The error is decrementing Top before reading the value [1]. The correct order is: read the top value first (item ← Stack[Top]), then decrement (Top ← Top - 1), then return item [1]. Decrementing first loses the top element — Stack[Top] after decrement is the element below the original top.
Q7Design a class called BankAccount with attributes: accountNumber (STRING), balance (REAL), and owner (STRING). Include a constructor, a method Deposit(amount : REAL), a method Withdraw(amount : REAL) that prevents overdraft, and a method GetBalance that returns the balance. Write the full class definition in CAIE pseudocode.[6]
✅ Mark scheme
CLASS BankAccount — 1 mark; PRIVATE accountNumber : STRING, balance : REAL, owner : STRING — 1 mark; PUBLIC PROCEDURE NEW(num,own,bal) with assignments — 1 mark; PUBLIC PROCEDURE Deposit(amount : REAL): balance ← balance + amount — 1 mark; PUBLIC PROCEDURE Withdraw(amount : REAL): IF amount ≤ balance THEN balance ← balance - amount — 1 mark; PUBLIC FUNCTION GetBalance() RETURNS REAL: RETURN balance — 1 mark.
Q8Explain the concept of encapsulation in OOP. State two benefits of making attributes PRIVATE and accessing them via PUBLIC methods. Give one example where failing to encapsulate could cause a data integrity problem.[4]
✅ Mark scheme
Encapsulation: bundling data and methods together, hiding internal state from outside — 1 mark; benefit 1: prevents invalid values being set directly (e.g. negative balance) — 1 mark; benefit 2: internal implementation can change without affecting code that uses the class — 1 mark; e.g. if balance were PUBLIC, external code could set balance ← -5000 bypassing overdraft check — 1 mark.
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.4.3 ADT Implementation
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1A stack array Stack[1:5] has Top=0. What does Top=0 indicate?
Q2What is the correct order of operations in a Push procedure?
Q3Which condition triggers a stack overflow error?
Q4In a queue implementation, which pointer is advanced after a Dequeue operation?
Q5What is the difference between Peek() and Pop() on a stack?
Section B — Short Answer [5 marks]
Q6Stack[1:3], Top=1, Stack[1]=7. Write pseudocode for Pop() that returns the top item and updates Top.
Mark schemeIF Top = 0 THEN OUTPUT "underflow" RETURN -1 ENDIF [1]; DECLARE item : INTEGER; item ← Stack[Top] [1]; Top ← Top - 1 [1]; RETURN item [1].
Q7State the initial values for Front, Rear, and Size when setting up an empty queue.
Mark schemeFront ← 1 [1]; Rear ← 0 [1]; Size ← 0 [1]. (Accept: Front=1, Rear=0, Size=0 as long as consistent with algorithm.)
Q8A stack is used to check if brackets in an expression are balanced. Explain how.
Mark schemeFor each character in the expression [1]: if it is an opening bracket push it onto the stack [1]; if it is a closing bracket, check the stack is not empty then pop — if the popped bracket does not match the closing bracket, the expression is unbalanced [1]; after processing all characters, if the stack is not empty, there are unmatched opening brackets — unbalanced [1].
Q9Queue[1:4], Front=2, Rear=3, Size=2. The queue contains ['B','C'] at indices 2 and 3. Perform Enqueue('D'). Show new state.
Q10Explain why a separate Size variable is useful in a queue implementation rather than computing size from Front and Rear.
Mark schemeComputing size as Rear - Front + 1 only works when the queue hasn't wrapped around [1]; a separate Size variable always gives the correct count regardless of pointer positions [1]; it also makes isEmpty and isFull checks simpler: Size=0 means empty, Size=MAX_SIZE means full [1].