Stacks, Queues and Complexity | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Describe and implement a stack using an array: push, pop, peek, isEmpty

Describe and implement a queue: enqueue, dequeue, isEmpty — including circular queues

Apply Big O notation to describe the time complexity of algorithms

Distinguish between best, average and worst case complexity

Stacks

Stack — LIFO

A stack is a Last In, First Out (LIFO) data structure. Items are added and removed from the top only. Implemented using an array and a top-of-stack pointer.

Operations

push(item): add to top — check stack not full first (overflow check)
pop(): remove and return top item — check not empty first (underflow check)
peek()/top(): return top item without removing
isEmpty(): returns true if top pointer = -1

Real-World Uses

Call stack (subroutine return addresses)
Undo/redo operations in software
Expression evaluation (postfix)
Reversing sequences
Backtracking algorithms (DFS)
Web browser back button

Queues

Queue — FIFO

A queue is a First In, First Out (FIFO) data structure. Items join at the rear and leave from the front. Maintains order of arrival — like a real queue.

Operations

enqueue(item): add to rear — overflow check
dequeue(): remove from front — underflow check
isEmpty(): front = rear (or size = 0)
isFull(): size = max capacity

Circular Queue

In a linear queue, dequeuing wastes space at the front. A circular queue uses modulo arithmetic to wrap the front/rear pointers around, reusing freed spaces. rear ← (rear+1) mod maxSize. More efficient memory use.

Priority Queue

A priority queue is a variant of the queue where each element has a priority. Elements with higher priority are dequeued before those with lower priority, regardless of insertion order.

Items with equal priority are dequeued in FIFO order. Implemented typically using a heap data structure for O(log n) insertion and deletion.

Uses: Dijkstra's shortest path algorithm (process lowest-cost node first), CPU scheduling (higher-priority processes first), hospital triage systems, network packet routing.

OCR H446 expects you to know that priority queues exist and their use cases. Implementation details (heap) may appear in stretch questions.

Big O Complexity

Time and Space Complexity

Big O notation describes the growth rate of an algorithm's running time (or space usage) as a function of input size n. It describes the worst case unless stated otherwise, and ignores constant factors and lower-order terms.

Complexity Classes

O(1) — constant
O(log n) — logarithmic
O(n) — linear
O(n log n) — linearithmic
O(n²) — quadratic
O(2ⁿ) — exponential

Best / Avg / Worst

Best case (Ω): minimum time (e.g. target at position 0 in linear search)
Average (Θ): expected time for typical input
Worst case (O): maximum time — used for Big O. E.g. target not in list for linear search → O(n)

Stack & Queue Complexity

Complexity of Stack and Queue Operations

Stack

push: O(1) — just increment pointer
pop: O(1) — just decrement pointer
peek: O(1) — read top
isEmpty: O(1)
Space: O(n) — n elements in stack

Queue

enqueue: O(1) — add to rear
dequeue: O(1) — remove from front (circular)
isEmpty: O(1)
Space: O(n)
Note: O(n) dequeue for non-circular due to shifting

All fundamental stack and queue operations are O(1) when implemented properly. This makes them ideal for algorithms that need frequent additions and removals from one end (stack) or both ends (queue).

Exam Practice

OCR H446 Style · 5 marks

A stack is implemented using an array of size 4. Trace the following operations and show the state of the stack and the top pointer after each:
push(7), push(3), push(9), pop(), push(5), peek()

[5 marks]

Start: stack=[], top=-1
push(7): stack=[7], top=0
push(3): stack=[7,3], top=1
push(9): stack=[7,3,9], top=2
pop(): returns 9, stack=[7,3], top=1
push(5): stack=[7,3,5], top=2
peek(): returns 5, stack unchanged=[7,3,5], top=2
(1 mark per correct state; award all 5 for fully correct trace)

Common Mistakes

Don't Lose Marks

Saying pop() returns nothing — pop() both removes AND returns the top element. Peek()/top() returns without removing. Students often confuse pop and peek, or say pop "deletes" the element. In an exam trace, always show both the return value and the updated stack state after pop.

Not checking overflow and underflow conditions — when describing stack/queue operations, you must mention checking for overflow before pushing (stack full) and underflow before popping/dequeuing (empty). Omitting these checks in pseudo-code costs marks.

Confusing O(n) dequeue in linear vs circular queues — in a simple linear array queue, removing from the front requires shifting all remaining elements: O(n). In a circular queue, dequeue is O(1) because the front pointer just moves. Know both and be able to justify the circular queue.

Stacks, Queuesand Complexity