OCR H446 · A Level Computer Science · ~12 min read
Notes
Video
Slides
Worksheet
Quiz
Stacks — LIFO Data Structure
A stack is a linear data structure that operates on a Last In, First Out (LIFO) basis. The last item added to the stack is the first item to be removed — like a pile of plates.
Stack Operations
Operation
Description
Complexity
push(item)
Add item to the top of the stack
O(1)
pop()
Remove and return the top item
O(1)
peek() / top()
Return top item without removing it
O(1)
isEmpty()
Returns True if stack has no items
O(1)
isFull()
Returns True if static stack is at max capacity
O(1)
Stack pointer (SP): an integer that tracks the index of the top item. Initially SP = −1 (empty). push: increment SP then store item; pop: return item at SP then decrement SP.
Stack overflow: trying to push onto a full stack (SP = max − 1)
Stack underflow: trying to pop from an empty stack (SP = −1)
Real-world Uses of Stacks
Call stack: tracks function calls — return addresses pushed on call, popped on return
Undo functionality: each action pushed; undo pops the last action
Bracket matching: open brackets pushed; closing bracket pops and checks for match
Reverse Polish Notation (RPN): operands pushed; operators pop two values, push result
Recursive algorithms: each recursive call uses the call stack
Queues — FIFO Data Structure
A queue is a linear data structure that operates on a First In, First Out (FIFO) basis. The first item added is the first item to be removed — like a queue at a shop.
Queue Operations
Operation
Description
Complexity
enqueue(item)
Add item to the rear of the queue
O(1)
dequeue()
Remove and return item from the front
O(1)*
peek()
Return front item without removing it
O(1)
isEmpty()
Returns True if queue is empty
O(1)
*O(n) for naive array implementation (shifts all elements); O(1) for circular buffer or linked list.
The Circular Queue (Circular Buffer)
A circular queue wraps around the array to reuse slots freed by dequeue operations, avoiding the need to shift elements:
Maintains front pointer and rear pointer
On dequeue: front = (front + 1) mod size
On enqueue: rear = (rear + 1) mod size, then store item
Empty when front = rear (or a separate count = 0)
Full when (rear + 1) mod size = front (or count = size)
A priority queue dequeues items in order of priority rather than arrival order. Higher-priority items leave first regardless of when they were added. Used in: operating system scheduling, Dijkstra's algorithm, A* search, hospital triage.
Real-world Uses of Queues
Print spooler: jobs processed in arrival order
CPU scheduling: process queues (round-robin = circular queue)
Keyboard buffer: keystrokes buffered and processed in order
Breadth-First Search: uses a queue to explore level by level
Network packet buffering: packets queued for transmission
Comparison: Stack vs Queue
Feature
Stack
Queue
Order
LIFO (Last In, First Out)
FIFO (First In, First Out)
Add
push to top
enqueue to rear
Remove
pop from top
dequeue from front
Analogy
Stack of plates / books
Queue at a till
Algorithm use
DFS, function calls, undo, RPN
BFS, scheduling, buffering
Exam tip: LIFO = Stack = Last In, First Out. FIFO = Queue = First In, First Out. Memorise these — they are the most frequently tested concepts. Also know: the call stack is used by CPUs to manage function calls, recursive procedures, and return addresses.
Exam tip: Circular queues avoid O(n) dequeue. The modular arithmetic: front = (front + 1) % size wraps the pointer around. This is the key advantage over a linear array queue.
⚠ Common Mistakes
Confusing push/pop with enqueue/dequeue — push/pop are stack operations; enqueue/dequeue are queue operations.
Saying a stack is FIFO — stacks are LIFO. Queues are FIFO.
Forgetting that a naive linear array queue is O(n) for dequeue (must shift all elements). A circular queue solves this.
✓ Notes completed!
▶
Video coming soon
Click to advance · Arrow keys also work
Click slide or press arrow keys to navigate
✍
Worksheet — 1.4.2b Stacks and Queues
8 questions · 20 marks · instantly marked
Q1What does LIFO stand for, and which data structure uses this principle? Give a real-world analogy.[3 marks]
✓ Mark scheme
LIFO = Last In, First Out [1]. A stack uses this principle [1]. Real-world analogy: a stack of plates — you always take from the top (last placed); or a stack of books, a Pringles tube [1].
Q2Trace through these stack operations on an initially empty stack and show the stack after each: push(5), push(12), push(3), pop(), push(8), pop().[3 marks]
✓ Mark scheme
push(5): [5], SP=0 [1]; push(12): [5,12], SP=1; push(3): [5,12,3], SP=2; pop() returns 3: [5,12], SP=1 [1]; push(8): [5,12,8], SP=2; pop() returns 8: [5,12], SP=1. Final stack: [5,12], top=12 [1]. Award marks for correct sequence of states.
Q3Explain what is meant by stack overflow and stack underflow. How should a program check for these conditions?[4 marks]
✓ Mark scheme
Stack overflow: occurs when a push is attempted on a full stack (SP has reached maximum index) — no space to add more elements [1]. Stack underflow: occurs when a pop is attempted on an empty stack (SP = −1) — no item to return [1]. Before push: check SP < max − 1 (or isFull() returns False) [1]. Before pop: check SP ≥ 0 (or isEmpty() returns False) [1].
Q4Explain how a circular queue avoids the problem of wasted space in a linear array queue.[3 marks]
✓ Mark scheme
In a linear array queue, dequeue leaves empty slots at the front that cannot be reused (or elements must be shifted, costing O(n)) [1]. A circular queue uses modular arithmetic — the rear pointer wraps around to the start: rear = (rear+1) mod size [1]. This allows previously freed front slots to be reused, making full use of the allocated array without shifting [1].
Q5Trace through these queue operations on an empty queue (capacity 4): enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D), dequeue(). Show front, rear, and contents after each.[4 marks]
Q6Describe how the call stack is used when a program calls a subroutine (function). What is stored on the stack, and what happens when the subroutine returns?[4 marks]
✓ Mark scheme
When a subroutine is called: a stack frame is pushed containing the return address (address of the next instruction to execute after the call) [1]; the values of local variables and parameters [1]; and the state of registers [1]. When the subroutine returns: the stack frame is popped; the return address is retrieved and the program counter is set to it, resuming execution at the correct point [1].
Q7Give two real-world uses of a queue in computing (not using the word 'queue' in your examples).[2 marks]
✓ Mark scheme
Any two of [1 each]: Print spooler — print jobs processed in the order they were sent; keyboard buffer — characters processed in the order typed; CPU scheduling — processes given time slices in order; network packet buffering — packets transmitted in order received; breadth-first search — nodes explored in FIFO order.
Q8What is a priority queue, and how does it differ from a standard queue? Give one computing application.[3 marks]
✓ Mark scheme
A priority queue is a queue where each element has an associated priority value, and items are dequeued in priority order (highest priority first) rather than arrival order [1]. Unlike a standard FIFO queue where earlier arrivals always leave first, in a priority queue a later-arriving item with higher priority is dequeued before earlier items with lower priority [1]. Application: operating system process scheduling — high-priority processes (e.g. system processes) are scheduled before low-priority ones [1]. Also: Dijkstra's shortest path algorithm; hospital emergency triage; A* search.
Topic Quiz
1 of 15
You scored
out of 15
🎯
Mini Test — 1.4.2b Stacks & Queues
10 questions · 10 marks · 10 minutes
5 MCQ + 5 short answer
⏱10:00
10 marks
Section A — Multiple Choice
Q1A stack operates on which principle?
Q2After push(1), push(2), push(3), pop(), what is the top of the stack?
Q3Which operation adds an item to a queue?
Q4The call stack stores what when a function is called?
Q5What is the key advantage of a circular queue over a linear array queue?
Section B — Short Answer
Q6What is stack underflow and when does it occur?
Mark schemeStack underflow occurs when a pop operation is attempted on an empty stack (stack pointer = -1, no items to return). The program should check isEmpty() before any pop to prevent errors. [1 mark]
Q7State one use of a stack in computing systems.
Mark schemeAny one of: call stack (tracking function calls and return addresses); undo functionality; bracket matching; Reverse Polish Notation evaluation; depth-first search; backtracking algorithms. [1 mark]
Q8Explain the difference between a queue and a priority queue.
Mark schemeA standard queue processes items in FIFO order — the first item in is the first out, regardless of importance. A priority queue processes items in priority order — the highest-priority item is dequeued first, even if it arrived later. [1 mark]
Q9What does the peek() operation do on a stack?
Mark schemepeek() (or top()) returns the value of the item at the top of the stack WITHOUT removing it. The stack pointer and contents are unchanged. This allows inspection of the top item without modifying the stack. [1 mark]
Q10Give one real-world computing example that uses a FIFO queue.
Mark schemeAny one of: print spooler (print jobs processed in order received); keyboard input buffer (keystrokes processed in order typed); CPU round-robin scheduling; network packet transmission buffer; breadth-first search algorithm. [1 mark]