CAIE 9618 · Paper 2 · Topic 2.3.2

Queues

FIFO · Enqueue · Dequeue · Front/Rear Pointers · Linear & Circular Queue

CSZone Cambridge International AS & A Level Computer Science 9618

The Queue ADT

First In, First Out (FIFO)

A queue is a linear ADT where items are added at the rear and removed from the front. The first item added is the first to be removed. Like a queue at a shop — fair, ordered service.

DEQUEUE ← front [ ] rear → ENQUEUE

10203040

front pointer ↑ (index 1) ↑ rear (index 4)

OPERATIONS

ENQUEUE(item) — add item to rear
DEQUEUE() — remove item from front
PEEK() — view front item without removing
isEmpty() — true if front > rear or size = 0
isFull() — rear = MAX_SIZE

Linear Queue Implementation

Front and Rear Pointers

ENQUEUE

IF rear = MAX_SIZE THEN
OUTPUT "Full"
ELSE
rear <- rear + 1
queue[rear] <- item
IF size = 0 THEN front <- 1 ENDIF
size <- size + 1
ENDIF

DEQUEUE

IF size = 0 THEN
OUTPUT "Empty"
ELSE
item <- queue[front]
front <- front + 1
size <- size - 1
OUTPUT item
ENDIF

Problem with linear queue: After many enqueue/dequeue operations, front advances towards MAX_SIZE — wasting space at the start of the array even if it's logically empty. Solution: circular queue.

Circular Queue

Reusing Empty Space at the Start

A circular queue treats the array as a ring. When rear reaches MAX_SIZE, it wraps around to index 1 if front has moved forward, reusing the freed space.

CIRCULAR ENQUEUE (wrap-around)

IF size = MAX_SIZE THEN
OUTPUT "Full"
ELSE
rear <- (rear MOD MAX_SIZE) + 1
queue[rear] <- item
size <- size + 1
ENDIF

CIRCULAR DEQUEUE

IF size = 0 THEN
OUTPUT "Empty"
ELSE
item <- queue[front]
front <- (front MOD MAX_SIZE) + 1
size <- size - 1
OUTPUT item
ENDIF

Exam Practice

Cambridge-style questions

Question 1

State one advantage of a circular queue over a linear queue. Explain how a circular queue avoids the problem you identified.

3 marks

1 mark

A circular queue avoids wasting memory at the front of the array

2 marks

In a linear queue, after many enqueue/dequeue operations, the front pointer moves forward, leaving unused array positions at the start. A circular queue uses MOD arithmetic to wrap the rear (and front) pointer back to the beginning of the array, so those positions are reused rather than wasted.

Common Mistakes

Don't lose easy marks

1

Confusing the direction of queue operations — in a queue, ENQUEUE adds to the rear and DEQUEUE removes from the front. Many students reverse these. Remember: people join the back, are served from the front.

2

Using the wrong full/empty condition in a circular queue — empty: size = 0. Full: size = MAX_SIZE. Do not check front = rear for empty/full without also tracking size, as this is ambiguous (both full and empty states can have front = rear).

3

Forgetting the circular queue uses MOD — the wrap-around formula is: new_rear = (rear MOD MAX_SIZE) + 1. Forgetting MOD means the pointer goes out of bounds.

Topic Summary — 2.3.2

What You Need to Know

QUEUE (FIFO)

Enqueue at REAR · Dequeue from FRONT
Front and rear pointers + size counter
Applications: print queues, CPU scheduling

LINEAR QUEUE PROBLEM

Wasted space as front pointer advances
Cannot reuse slots at start of array

CIRCULAR QUEUE SOLUTION

Wrap-around: new_pos = (pos MOD MAX) + 1
Reuses freed slots at start of array
Full: size = MAX_SIZE · Empty: size = 0

CSZone

Next Video

2.3.3

Linked Lists

Nodes · Pointers · Insertion · Deletion · Traversal

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools