SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
CAIE 9618 · Paper 2 · Topic 2.3.1

Stacks

LIFO · Push · Pop · Peek · isEmpty · isFull · Stack Pointer · Applications

CSZone Cambridge International AS & A Level Computer Science 9618
The Stack ADT

Last In, First Out (LIFO)

A stack is a linear abstract data type where items can only be added to and removed from the same end — called the top. The last item pushed is the first item popped. Like a pile of plates.
← PUSH adds here · POP removes from here
30 ← TOP
20
10
BOTTOM (index 1)
OPERATIONS
PUSH(item) — add item to top
POP() — remove and return top item
PEEK() — view top without removing
isEmpty() — is the stack empty?
isFull() — is the stack at capacity?
Stack Implementation (Array)

Stack Pointer Tracks the Top

A stack is often implemented using a 1D array plus a stack pointer (SP) that stores the index of the current top element. SP starts at 0 (empty).
PUSH ALGORITHM
IF SP = MAX_SIZE THEN
OUTPUT "Stack overflow"
ELSE
SP <- SP + 1
stack[SP] <- item
ENDIF
POP ALGORITHM
IF SP = 0 THEN
OUTPUT "Stack underflow"
ELSE
item <- stack[SP]
SP <- SP - 1
OUTPUT item
ENDIF
Applications of Stacks

Where Are Stacks Used?

Call stack / subroutine calls — return addresses pushed onto stack when CALL executes; popped back when RET executes. Enables nested and recursive calls.
Undo functionality — each action pushed to stack; Ctrl+Z pops and reverses the last action
Backtracking in algorithms — e.g. maze solving: push current position, try a direction; if dead end, pop back
Expression evaluation — converting infix to postfix (Reverse Polish Notation) uses a stack to hold operators
Bracket matching — push opening brackets, pop and compare when closing bracket is encountered; empty at end = balanced
Web browser back button — visited pages pushed; back button pops to previous page
Exam Practice

Cambridge-style questions

Question 1
A stack initially contains: [10, 25, 7] (7 at top). Trace the following operations and state the final contents and stack pointer: PUSH(42), POP(), PUSH(13), PEEK()
5 marks
1 mark
PUSH(42): stack = [10, 25, 7, 42], SP = 4
1 mark
POP(): returns 42, stack = [10, 25, 7], SP = 3
1 mark
PUSH(13): stack = [10, 25, 7, 13], SP = 4
1 mark
PEEK(): returns 13 (no change to stack or SP)
1 mark
Final stack: [10, 25, 7, 13] with SP = 4
Common Mistakes

Don't lose easy marks

1
Confusing stack overflow and underflow — overflow occurs when PUSH is attempted on a full stack (SP = max). Underflow occurs when POP is attempted on an empty stack (SP = 0). Know which error belongs to which operation.
2
Saying POP deletes the element from memory — in an array implementation, POP only decrements the stack pointer. The data may still be in the array but is considered logically removed because SP no longer points to it.
3
Forgetting to increment SP before assigning (PUSH) and to read before decrementing (POP) — the order matters. PUSH: SP++ then array[SP] = item. POP: item = array[SP] then SP--.
Topic Summary — 2.3.1

What You Need to Know

STACK (LIFO)
Push/Pop from TOP only
Stack pointer (SP) tracks top index
SP=0 → empty · SP=MAX → full
OPERATIONS
PUSH: check full → SP++ → array[SP]=item
POP: check empty → item=array[SP] → SP--
PEEK: return array[SP] (no SP change)
APPLICATIONS
Call stack (subroutines/recursion)
Undo functionality
Bracket matching · RPN evaluation
Web browser back button
Backtracking algorithms
CSZone

Next Video

2.3.2
Queues
FIFO · Enqueue · Dequeue · Linear & Circular Queue
Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools