4.2.2 Queues — AQA 7517

What is a Queue?

A queue is a linear ADT that operates on the FIFO (First In, First Out) principle — the first item added is the first item removed. Like a real-world queue (e.g. people waiting at a checkout).

Queue Operations

Operation	Description	Condition
Enqueue	Add an item to the back of the queue	Fails if queue is full (overflow)
Dequeue	Remove an item from the front of the queue	Fails if queue is empty (underflow)
Peek / Front	View the front item without removing it	Fails if queue is empty
isEmpty()	Returns TRUE if the queue has no items	—
isFull()	Returns TRUE if the queue is at capacity	—

Linear Queue Implementation

A linear queue can be implemented using an array with two pointers:

Front pointer — points to the position of the first (oldest) item
Rear/Back pointer — points to the next available position for adding items

// Linear queue using an array (size = 5)
Initial state: front = 0, rear = 0, size = 0
// Enqueue "Alice": data[rear] = "Alice"; rear++; size++
// Enqueue "Bob":   data[rear] = "Bob";   rear++; size++
// Dequeue:         return data[front]; front++; size--

Problem with linear queue: After several enqueue/dequeue operations, the front pointer moves right, leaving wasted space at the beginning of the array that cannot be reused. This leads to a "false full" condition.

Circular Queue

A circular queue solves the wasted space problem by treating the array as circular — when the rear pointer reaches the end of the array, it wraps around to position 0 (modulo arithmetic).

// Circular wrap-around:
rear = (rear + 1) MOD maxSize
front = (front + 1) MOD maxSize

This allows space freed by dequeuing to be reused by future enqueues.

Priority Queue

A priority queue is a variant where items are dequeued in order of their priority rather than strictly FIFO. Higher priority items are removed first, regardless of when they arrived.

Applications: task scheduling, Dijkstra's algorithm, hospital triage systems.

Applications of Queues

Application	Why a queue?
Print queue (printer spooler)	Documents print in the order submitted
CPU scheduling	Processes wait in order for CPU time
Keyboard input buffer	Keystrokes processed in order typed
Network packet handling	Packets processed in order received
Breadth-first search	Nodes visited in level order

Exam tip: Know FIFO, enqueue/dequeue operations, and the difference between linear and circular queues. Be ready to trace through queue operations showing front/rear pointer movements. Know why a circular queue is better than a linear queue (no wasted space).

▶

Click through the slides at your own pace. Use arrow keys or click to advance.

Click slide or press arrow keys to navigate

Worksheet — 4.2.2 Queues

8 questions · instantly marked · AQA 7517 standard

Q1What principle does a queue operate on? Define this principle.[2]

✅ Mark scheme

Mark scheme

FIFO — First In, First Out [1]; the first item added to the queue is the first item to be removed [1].

Q2State the five main operations of a queue and describe what each does.[5]

✅ Mark scheme

Mark scheme

Enqueue — add item to the back [1]; Dequeue — remove item from the front [1]; Peek/Front — view front item without removing [1]; isEmpty() — returns TRUE if empty [1]; isFull() — returns TRUE if at capacity [1].

Q3A linear queue has elements [10, 20, 30] with front=0, rear=3. Show the state after: (a) Dequeue, (b) Enqueue 40.[4]

✅ Mark scheme

Mark scheme

(a) Dequeue: removes 10 (front item); front becomes 1; array contains [_, 20, 30]; size decreases [2]; (b) Enqueue 40: 40 added at rear; rear becomes 4; array contains [_, 20, 30, 40] [2].

Q4Explain the problem with a linear queue that makes a circular queue preferable.[3]

✅ Mark scheme

Mark scheme

After dequeue operations the front pointer advances, leaving empty/wasted space at the start of the array [1]; even though space has been freed, the linear queue cannot reuse it — a 'false full' condition occurs [1]; a circular queue uses modulo arithmetic to wrap the rear/front pointers back to position 0, allowing freed space to be reused [1].

Q5Explain how a circular queue updates its rear pointer when an item is enqueued. A queue has maxSize=5 and rear=4.[2]

✅ Mark scheme

Mark scheme

rear = (rear + 1) MOD maxSize [1]; with rear=4 and maxSize=5: (4+1) MOD 5 = 0, so rear wraps to 0 [1].

Q6What is a priority queue? Give one real-world application.[2]

✅ Mark scheme

Mark scheme

A queue variant where items are dequeued in order of their priority rather than FIFO [1]; real-world example: hospital triage (more urgent patients seen first) / OS task scheduling / Dijkstra's algorithm [1].

Q7Give three real-world applications of queues and explain why a queue is appropriate for each.[3]

✅ Mark scheme

Mark scheme

Any three with justification: print queue — documents print in submission order (FIFO) [1]; keyboard buffer — keystrokes processed in the order typed [1]; CPU scheduling — processes wait in order for processor time [1]; network packet handling — packets processed in order received [1]; BFS traversal — nodes explored level by level [1].

Q8Explain what 'overflow' and 'underflow' mean in the context of a queue.[2]

✅ Mark scheme

Mark scheme

Overflow — attempting to enqueue when the queue is full (adding to a full queue) [1]; underflow — attempting to dequeue when the queue is empty (removing from an empty queue) [1].

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 12

Click to reveal definition

🎉

All cards reviewed!

Term	Definition

🔒

Pro Content

Subscribe to unlock all AQA 7517 A-Level lessons.

£7.99/month

Upgrade to Pro

What is a Queue?

Queue Operations

Linear Queue Implementation

Circular Queue

Priority Queue

Applications of Queues

Worksheet — 4.2.2 Queues

Mini Test — Queues