Cambridge 9618 · International A Level Computer Science · ~15 min read
Notes
Video
Slides
Quiz
Worksheet
Abstract Data Types
An Abstract Data Type (ADT) is a data structure defined by its behaviour — the operations it supports — rather than how it is implemented in memory. Stacks and queues are both fundamental ADTs studied in Cambridge 9618 Paper 4.
Stack — LIFO (Last In, First Out)
A stack is a linear data structure where items can only be added or removed from one end — the top. The last item pushed onto the stack is the first to be removed: LIFO.
📚 Stack Properties
• Only one access point: the top
• LIFO — Last In, First Out
• Uses a top pointer to track the current top
• Stack overflow: push onto full stack
• Stack underflow: pop from empty stack
• Can be implemented with an array or linked list
📋 Analogy
Think of a stack of plates in a cafeteria:
• You put a new plate ON TOP
• You take a plate FROM THE TOP
• Can't take from the bottom without removing all above
Or a browser Back button — pages are pushed as you navigate; popped when you go back.
Stack — Visual Representation
Stack state after pushing: 10, 20, 30
30← TOP (index 2)
20index 1
10index 0
—empty
POP → removes 30 and top decrements to 1
Stack Operations
push(item)
Add item to the top of the stack. Top pointer increments. Check for overflow first.
pop()
Remove and return the top item. Top pointer decrements. Check for underflow first.
peek() / top()
Return the top item WITHOUT removing it. Top pointer does not change.
isEmpty()
Returns TRUE if the stack is empty (top pointer = −1 or 0 if 1-indexed).
isFull()
Returns TRUE if the stack is full (top = max size − 1). Only relevant for fixed-size implementations.
size()
Returns the number of items currently in the stack.
Stack — Cambridge 9618 Pseudocode
// Stack implemented as array with a top pointer DECLAREStack : ARRAY[1:10] OF INTEGER DECLARETopPtr : INTEGER TopPtr ← 0// 0 = empty
When a function is called, a stack frame is pushed
Contains local variables, parameters, return address
When function returns, its frame is popped
🔢 Expression Evaluation
Compilers use stacks to evaluate bracket matching
Convert infix expressions to postfix (RPN)
Evaluate postfix expressions
🧭 Backtracking Algorithms
Depth-First Search (DFS) uses a stack
Maze solving — track visited positions
Recursion itself uses the call stack implicitly
Queue — FIFO (First In, First Out)
A queue is a linear data structure where items are added at one end (rear / back) and removed from the other end (front). The first item added is the first to be removed: FIFO.
🚶 Queue Properties
• Two access points: front (remove) and rear (add)
• FIFO — First In, First Out
• Uses front pointer and rear pointer
• Queue overflow: enqueue onto full queue
• Queue underflow: dequeue from empty queue
• Can be linear or circular
🎭 Analogy
Like a supermarket checkout queue:
• People join at the BACK (rear)
• People leave from the FRONT
• Fair — first to arrive, first to be served
Or a printer queue — first document sent is first to print.
Queue — Visual Representation
Queue after enqueue: A, B, C, D
FRONT ↓
A
B
C
REAR ↓
D
—
DEQUEUE removes A (front). ENQUEUE E adds at rear position 4.
Queue Operations
enqueue(item)
Add item at the rear. Rear pointer increments. Check for overflow first.
dequeue()
Remove and return item from the front. Front pointer increments. Check for underflow first.
peek() / front()
Return front item WITHOUT removing it. Front pointer does not change.
isEmpty()
Returns TRUE if front > rear (linear) or count = 0 (circular). Empty queue check.
isFull()
Returns TRUE if the queue has reached maximum capacity. Prevents overflow.
size()
Returns the number of items currently in the queue.
Queue — Cambridge 9618 Pseudocode
// Queue implemented as array with front and rear pointers DECLAREQueue : ARRAY[1:10] OF STRING DECLAREFrontPtr, RearPtr, Count : INTEGER FrontPtr ← 1RearPtr ← 0Count ← 0
A problem with a linear queue implemented as an array is that after many enqueue/dequeue operations, the front pointer moves forward — creating "wasted" empty slots at the beginning of the array even when the queue isn't full. A circular queue solves this by wrapping around: when the rear reaches the end of the array, it loops back to index 1 (if those slots are free). The pointer update becomes: RearPtr ← (RearPtr MOD MaxSize) + 1. This reuses freed-up space efficiently.
Queue Applications
🖨 Print Queue
Print jobs are enqueued as they arrive
Printer dequeues one job at a time
Fair scheduling — first sent, first printed
⚙️ CPU Scheduling
Processes waiting for CPU time are queued
Round-robin scheduling uses a circular queue
First process waiting gets CPU next
🌐 Breadth-First Search
BFS graph traversal uses a queue
Start node enqueued; neighbours enqueued when visited
Dequeue to visit next node at current depth
📡 Keyboard/I/O Buffer
Keystrokes stored in queue as typed
Program reads from front when ready
Ensures characters processed in correct order
Stack vs Queue — Comparison
Feature
Stack
Queue
Principle
LIFO — Last In, First Out
FIFO — First In, First Out
Access point(s)
One end (top only)
Two ends (front and rear)
Add operation
Push (onto top)
Enqueue (at rear)
Remove operation
Pop (from top)
Dequeue (from front)
Inspect without removal
Peek / Top
Peek / Front
Typical use
Undo, call stack, DFS
Print queue, CPU scheduling, BFS
Empty check
TopPtr = 0
Count = 0
Cambridge 9618 exam tip: Know both the theoretical definition (LIFO/FIFO) and the implementation details. Exams frequently ask to "trace through" push/pop or enqueue/dequeue operations on a given stack/queue state — show the array contents and pointer values at each step. Know the terms: overflow (add to full structure), underflow (remove from empty structure). For circular queues: understand WHY they are needed (wasted space problem with linear queues) and the modulo wrapping formula for the rear pointer: RearPtr ← (RearPtr MOD MaxSize) + 1.
⚠️ Common Mistakes
Confusing LIFO and FIFO — Stack = LIFO (same end for add/remove); Queue = FIFO (add at rear, remove from front). A common exam trap is to describe them the wrong way around.
Stack overflow vs underflow — overflow: trying to push when full (too much in); underflow: trying to pop when empty (nothing to take out). These terms are commonly confused.
Forgetting to check isEmpty before pop/dequeue — always validate the structure is not empty before removing. A robust implementation always includes this check.
Linear queue "full" problem — in a simple array implementation, a queue can appear full even when space exists at the beginning (because front has moved). This is why circular queues exist — always explain this distinction if asked why circular queues are used.
Peek vs Pop — peek() returns the top/front item WITHOUT removing it; pop()/dequeue() removes AND returns it. Don't confuse these operations.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.3.1 Stacks & Queues
8 questions · Cambridge 9618 standard
Q1Define the terms LIFO and FIFO. State which data structure uses each principle and give one real-world analogy for each.[6]
✅ Mark scheme
LIFO: Last In, First Out — the most recently added item is the first to be removed [1]; used by a stack [1]; analogy: stack of plates — the plate added last is taken first / browser back button / undo history [1]; FIFO: First In, First Out — the first item added is the first to be removed [1]; used by a queue [1]; analogy: supermarket checkout queue — first person to join is first to be served / print queue / keyboard buffer [1].
Q2A stack contains [10, 20, 30, 40] with 40 at the top. Show the state of the stack after: (a) POP, (b) PUSH 50, (c) POP, (d) POP.[4]
✅ Mark scheme
(a) POP → removes 40 → stack: [10, 20, 30] top = 30 [1]; (b) PUSH 50 → stack: [10, 20, 30, 50] top = 50 [1]; (c) POP → removes 50 → stack: [10, 20, 30] top = 30 [1]; (d) POP → removes 30 → stack: [10, 20] top = 20 [1]. Award 1 mark per correct trace step — must show correct top element after each operation.
Q3A queue contains [A, B, C, D] with A at the front and D at the rear. Show the state after: (a) DEQUEUE, (b) ENQUEUE E, (c) DEQUEUE, (d) ENQUEUE F.[4]
✅ Mark scheme
(a) DEQUEUE → removes A (front) → queue: [B, C, D] front=B rear=D [1]; (b) ENQUEUE E → queue: [B, C, D, E] front=B rear=E [1]; (c) DEQUEUE → removes B → queue: [C, D, E] front=C rear=E [1]; (d) ENQUEUE F → queue: [C, D, E, F] front=C rear=F [1]. Award 1 mark per step showing correct front and rear.
Q4Explain what is meant by 'stack overflow' and 'stack underflow'. State what should happen in a well-designed program when either occurs.[4]
✅ Mark scheme
Stack overflow: occurs when a PUSH operation is attempted on a stack that is already at maximum capacity — no space remains for the new item [1]; well-designed program: checks IsFull() before pushing and outputs an error message / raises an exception rather than attempting to push [1]; stack underflow: occurs when a POP operation is attempted on an empty stack — there is no item to remove [1]; well-designed program: checks IsEmpty() before popping and outputs an error message / raises an exception rather than attempting to pop from nothing [1].
Q5Explain why a circular queue is more efficient than a simple linear (non-circular) queue when implemented using an array.[4]
✅ Mark scheme
In a linear queue, the front pointer moves forward with each DEQUEUE — this means the slots at the beginning of the array are now empty/wasted [1]; even if only a few items are in the queue, the rear pointer might reach the end of the array — making the queue appear full even though space is available at the start [1]; in a circular queue, the rear pointer wraps around using modulo arithmetic (RearPtr ← (RearPtr MOD MaxSize) + 1) — so when the rear reaches the end, it loops back to index 1 if those slots are free [1]; this reuses the vacated slots and makes more efficient use of the fixed-size array without needing to shift all items [1].
Q6State two applications where a stack would be used and two applications where a queue would be used. For each, briefly explain why that structure is appropriate.[4]
✅ Mark scheme
Stack application 1: function call stack — when a function is called, its frame is pushed; when it returns, the frame is popped; LIFO ensures the most recently called function returns first [1]; Stack application 2: undo history — each user action is pushed; Ctrl+Z pops the last action to reverse it; LIFO ensures the most recent action is undone first [1]; Queue application 1: print queue — print jobs are enqueued as sent; the printer dequeues one at a time; FIFO ensures jobs are printed in the order submitted [1]; Queue application 2: CPU scheduling — processes waiting for CPU are queued; FIFO (or round-robin circular queue) ensures processes are served in arrival order and no process is perpetually starved [1].
Q7A circular queue of size 5 uses integer variables Front, Rear, and Size. Initially Front = 0, Rear = 4, Size = 5 (full). An item is dequeued. State the new values of Front and Size. Then, using the formula Rear = (Rear + 1) MOD MaxSize, state the new Rear if one item is then enqueued.[4]
✅ Mark scheme
After dequeue: Front = (0 + 1) MOD 5 = 1 [1]; Size = 4 [1]; After enqueue: Rear = (4 + 1) MOD 5 = 0 [1]; Size = 5 [1]. Accept equivalent correct working.
Q8State two differences between a stack and a queue. For each, give a real-world use case that exploits that specific property.[4]
✅ Mark scheme
Difference 1: Stack is LIFO (last in, first out); Queue is FIFO (first in, first out) [1]; Stack use: undo/redo functionality — the most recent action is reversed first [1]; Difference 2: Stack has one access point (top); Queue has two (front for removal, rear for insertion) [1]; Queue use: print job scheduling — documents print in the order they were submitted [1]. Accept other valid differences and use cases.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.3.1 Stacks & Queues
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Which principle does a stack use?
Q2A stack currently contains [5, 10, 15] with 15 at the top. After PUSH(20) and then POP(), what is at the top?
Q3Which term describes trying to remove an item from an empty stack or queue?
Q4In a queue, where are new items added and where are items removed?
Q5Which of the following is a real application of a queue?
Section B — Short Answer [5 marks]
Q6Write pseudocode for a PUSH procedure that adds an integer to a stack array of size 5 (1-indexed). Include an overflow check.
Mark schemePROCEDURE Push(Item: INTEGER); IF TopPtr = 5 THEN OUTPUT "Overflow" [1]; ELSE TopPtr ← TopPtr + 1 [1]; Stack[TopPtr] ← Item [1]; ENDIF; ENDPROCEDURE. Full marks: correct overflow check [1] + TopPtr increment before assignment [1] + correct array assignment [1]. Deduct 1 if TopPtr is incremented AFTER assignment (off-by-one error).
Q7Explain the difference between the peek() operation and the pop() operation on a stack.
Mark schemePeek(): returns the value at the top of the stack WITHOUT removing it — the top pointer does not change and the item remains in the stack [1]; pop(): removes AND returns the top item — the top pointer decrements and the item is no longer in the stack [1]; both operations require checking isEmpty first (underflow check) [1]. They have the same return value but pop() modifies the stack structure while peek() leaves it unchanged.
Q8A queue is stored in an array of size 5. The current state is: Queue = [_, C, D, E, _] with FrontPtr=2 and RearPtr=4. What happens when the program tries to ENQUEUE F using a linear (non-circular) implementation?
Mark schemeRearPtr = 4 = MaxSize, so the linear implementation would report overflow (queue full) [1]; however there is actually one empty slot at index 1 (position where C was) — this illustrates the wasted space problem with linear queues [1]; in a circular queue, RearPtr would wrap around: RearPtr ← (4 MOD 5) + 1 = 0 + 1 = 1, so F would be stored at index 1 [1]. This is why circular queues are more efficient for continuous enqueue/dequeue patterns.
Q9State what happens to the function call stack when a function calls another function, and what happens when the called function returns.
Mark schemeWhen a function is called: a new stack frame is PUSHED onto the call stack — this frame contains the function's local variables, parameters, and the return address (the address of the instruction to execute after the function returns) [1]; when the function returns: its stack frame is POPPED from the call stack — control returns to the return address stored in that frame, and the calling function resumes execution [1]; LIFO ordering means the most recently called function returns first — this correctly handles nested function calls and recursion [1].
Q10Describe what an Abstract Data Type (ADT) is. Explain how stacks and queues are examples of ADTs.
Mark schemeAn ADT is a data structure defined by its behaviour (the operations it supports and their effects) rather than its implementation in memory [1]; the ADT specifies WHAT operations are available (push, pop, enqueue, dequeue, etc.) and what they do, but not HOW they are implemented internally [1]; stacks and queues are ADTs because: they are defined by their logical behaviour (LIFO and FIFO respectively) — both can be implemented using arrays OR linked lists, and the user of the ADT does not need to know which implementation is used; the behaviour (LIFO/FIFO) remains the same regardless of implementation [1].