AQA 7517 · Paper 1 · 4.2.4

Stacks
LIFO

AQA A-Level Computer Science · Section 4.2 Fundamentals of Data Structures

WHAT YOU'LL LEARN

LIFO principle · Push/Pop/Peek/isEmpty · Stack pointer · Call stack · Applications

AQA SPEC LINK

4.2.4 — Stacks and their implementation

LIFO

Stack — Last In, First Out

A stack is an abstract data type (ADT) where items are added and removed from only one end — the top. The last item pushed in is the first to be popped out: LIFO.

C ← TOP

B

A

BOTTOM

Items pushed in order A, B, C.
C is on top — it will be popped first.
A will be popped last.

Stack Operations

Core Stack Operations

Operation	Description	Complexity
Push(item)	Add item to the top of the stack	O(1)
Pop()	Remove and return top item	O(1)
Peek()	Return top item without removing	O(1)
isEmpty()	Returns True if stack has no items	O(1)
isFull()	Returns True if stack is at capacity	O(1)

⚠️ Popping from an empty stack = underflow. Pushing to a full stack = overflow. Always check isEmpty() before Pop().

Stack Pointer

Implementing a Stack with an Array

A stack can be implemented using an array plus a stack pointer (SP) — an integer that tracks the index of the top element.

stack ← [0,0,0,0,0]   ← array of capacity 5
SP ← -1              ← -1 means empty

PUSH: SP ← SP+1; stack[SP] ← item
POP:  item ← stack[SP]; SP ← SP-1
PEEK: RETURN stack[SP]
isEmpty: RETURN SP = -1

Call Stack

The Call Stack in Programs

The call stack is the OS/language runtime's built-in stack that tracks subroutine calls. When a function is called, a stack frame is pushed containing local variables, parameters, and return address.

When the function returns, its frame is popped. This is how recursion works — each recursive call pushes a new frame. Too many calls without a base case = stack overflow.

Trace Example

Tracing Stack Operations

Operation	Stack (bottom→top)	SP	Return
Push(5)	[5]	0	—
Push(3)	[5, 3]	1	—
Push(8)	[5, 3, 8]	2	—
Peek()	[5, 3, 8]	2	8
Pop()	[5, 3]	1	8
Pop()	[5]	0	3

Applications

Real-World Uses of Stacks

Call stack — tracking subroutine calls and local variables in programs

Undo/Redo — each action pushed; undo pops most recent

Browser back button — visited pages pushed onto a stack

Bracket matching — check ( ) [ ] { } are balanced in code editors

RPN evaluation — operands pushed, operators pop and compute

DFS graph traversal — uses a stack to track vertices to visit

Bracket Matching

Stack Application: Bracket Checker

SUBROUTINE checkBrackets(expr)
  stack ← []
  FOR char IN expr
    IF char = '(' THEN stack.push(char)
    ELSEIF char = ')' THEN
      IF stack.isEmpty() THEN RETURN False
      ELSE stack.pop()
    ENDIF
  ENDFOR
  RETURN stack.isEmpty()
ENDSUBROUTINE

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

The following operations are performed on an initially empty stack:
Push(7), Push(2), Push(9), Pop(), Push(4), Peek()

(a) What value does Pop() return? [1]
(b) What value does Peek() return? [1]
(c) What does the stack contain after all operations, bottom to top? [2]

[4 marks]

1 mark

(a) Pop() returns 9 (last item pushed)

1 mark

(b) Peek() returns 4 (new top after push)

2 marks

(c) Stack contains: 7, 2, 4 (bottom to top)

Summary

Key Points to Remember

Stack = LIFO — Last In, First Out; all operations at the top

Push (add) · Pop (remove+return) · Peek (view) · isEmpty

Stack pointer tracks the index of the top element; -1 = empty

Pop from empty = underflow; Push to full = overflow

Used in: call stack, undo, RPN evaluation, DFS traversal

🎉 Lesson complete — move to the quiz!