SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 1 · 4.2.5

Queues
FIFO

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

WHAT YOU'LL LEARN
FIFO principle · Enqueue/Dequeue · Linear & Circular queues · Priority queues
AQA SPEC LINK
4.2.5 — Queues including circular queues and priority queues
FIFO

Queue — First In, First Out

A queue is an ADT where items are added at the rear (back) and removed from the front. The first item in is the first item out: FIFO. Like a real-world queue.
FRONT →
Alice
Bob
Carol
← REAR
Alice arrived first — she leaves first (Dequeue). New arrivals join at the rear (Enqueue).
Queue Operations

Core Queue Operations

OperationDescriptionComplexity
Enqueue(item)Add item to the rearO(1)
Dequeue()Remove and return front itemO(1)
Peek()Return front item without removingO(1)
isEmpty()Returns True if queue is emptyO(1)
isFull()Returns True if at capacityO(1)
Dequeue from empty queue = underflow. Unlike a stack, front and rear pointers are both needed.
Linear Queue

Linear Queue — Array Implementation

queue ← [0,0,0,0,0]   ← array of capacity 5
front ← 0            ← index of front
rear ← -1            ← index of rear

ENQUEUE: rear ← rear+1; queue[rear] ← item
DEQUEUE: item ← queue[front]; front ← front+1
⚠️ Problem with linear queues: Even after dequeuing, slots at the front are wasted. When rear reaches end, no more space — even if front has moved. Solution: circular queue.
Circular Queue

Circular Queue — Solving the Waste Problem

In a circular queue, when the rear pointer reaches the end of the array, it wraps around to position 0. This reuses the freed front slots, making full use of capacity.
MODULO ARITHMETIC
ENQUEUE: rear ← (rear + 1) MOD capacity
DEQUEUE: front ← (front + 1) MOD capacity
isFull: (rear + 1) MOD capacity = front
Priority Queue

Priority Queue

In a priority queue, each item has a priority value. Items are dequeued in priority order (highest priority first), regardless of arrival order.
REAL-WORLD EXAMPLES
A&E triage — most critical patients treated first, not first arrived
CPU scheduling — higher priority processes scheduled first
Dijkstra's algorithm — uses a priority queue to process nearest node
Queue Trace

Tracing Queue Operations

OperationQueue (front→rear)Return
Enqueue(A)[A]—
Enqueue(B)[A, B]—
Enqueue(C)[A, B, C]—
Dequeue()[B, C]A
Enqueue(D)[B, C, D]—
Dequeue()[C, D]B
Applications

Real-World Uses of Queues

Print spooler — documents queued in order received
CPU scheduling — processes queued for execution (FCFS algorithm)
Keyboard buffer — keystrokes buffered in order typed
BFS graph traversal — uses a queue to process vertices level by level
Network packet handling — packets processed in arrival order
AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style
Explain the difference between a linear queue and a circular queue, and state one advantage of the circular queue.
[4 marks]
1 mark
In a linear queue, the front and rear pointers only move forward — freed slots at the front cannot be reused
1 mark
The linear queue reports full when rear reaches the end, even if there is free space at the front
1 mark
In a circular queue, the pointers wrap around using modulo arithmetic, reusing freed slots
1 mark
Advantage: more efficient use of memory — no space is wasted
Summary

Key Points to Remember

Queue = FIFO — First In, First Out; enqueue at rear, dequeue from front
Enqueue (add rear) · Dequeue (remove front) · Peek · isEmpty
Circular queue uses modulo arithmetic to wrap pointers — reuses freed space
Priority queue — dequeues by priority, not arrival order
Used in: BFS, print spooler, CPU scheduling, keyboard buffer
🎉 Lesson complete — move to the quiz!