10.4 Queue Abstract Data Types - A-Level Computer Science

Learning Objectives

By the end of this lesson, you will be able to:

Show understanding that an ADT is a collection of data and a set of operations on those data
Show understanding that a stack, queue and linked list are examples of ADTs
Use a stack, queue and linked list to store data
Describe how a queue, stack and linked list can be implemented using arrays
Describe key features of stack, queue and linked list and justify their use for a given situation
Add, edit and delete data from queue data structures
Understand and implement circular queues to avoid moving items in arrays

Key Terms

Abstract Data Type (ADT)

A collection of data and a set of operations on those data

Queue

A list containing several items operating on first in, first out (FIFO) principle

FIFO

First In, First Out - principle where first item added is first item removed

Enqueue

Operation to add an item to the end of a queue

Dequeue

Operation to remove an item from the front of a queue

FrontOfQueuePointer

Pointer indicating the front (start) of the queue

EndOfQueuePointer

Pointer indicating the end (rear) of the queue

Circular Queue

A queue implemented as a circular structure to avoid moving items in array

Linear Structure

Data structure where elements are arranged in a sequential order

HeadIndex

Index pointing to the front/head of a circular queue

TailIndex

Index pointing to the end/tail of a circular queue

Empty Queue

A queue with no elements, typically indicated by EndOfQueuePointer = -1

Queue Basics

A queue is an Abstract Data Type (ADT) that operates on the First In, First Out (FIFO) principle. It's like a real-world queue (line) where the first person to join is the first person to be served.

What is a Queue?

A list containing several items
Operates on FIFO (First In, First Out) principle
Items can be added to queue (enqueue)
Items can be removed from queue (dequeue)
First item added is first item to be removed
Has start (front) and end (rear) pointers

Key Insight:

Think of a queue like a cafeteria line - first person in line gets served first.

Queue Visualization

Empty Queue: EndOfQueuePointer = -1

Empty

Queue with 5 items:

FrontOfQueuePointer

EndOfQueuePointer

When queue is empty, EndOfQueuePointer has value -1. When a value joins queue, EndOfQueuePointer is incremented before adding value.

Queue Operations Simulation

Interactive Queue Simulator

Use the buttons below to enqueue (add) and dequeue (remove) items from the queue. Watch how the pointers change.

Front Pointer

Rear Pointer

Queue Size

-1

Front Index

-1

Rear Index

How it works:

Enqueue: Adds item to end (rear) of queue. Rear pointer moves forward.
Dequeue: Removes item from front of queue. Front pointer moves forward.
When queue is empty: Front = -1, Rear = -1
First item added = First item removed (FIFO)

Real-Life Example: Printer Queue

When multiple people send documents to a shared printer, the printer uses a queue:

Alice sends DocumentA to printer → Enqueue(DocumentA)
Bob sends DocumentB to printer → Enqueue(DocumentB)
Printer processes → Dequeue() = DocumentA (Alice's document prints first)
Printer processes → Dequeue() = DocumentB (Bob's document prints next)
Queue: [DocumentA, DocumentB] → DocumentA (first in) prints first

This ensures fair processing - first person to send a document gets it printed first.

Activity 1: Queue Operations Practice

Trace the operations on an initially empty queue:

Enqueue(A), Enqueue(B), Enqueue(C)
Dequeue(), Enqueue(D), Enqueue(E)
Dequeue(), Dequeue(), Enqueue(F)
What is the front item after all operations?
What is the rear item after all operations?

Solution:

Step 1:
Start: [] (empty)
Enqueue(A) → [A]
Enqueue(B) → [A, B]
Enqueue(C) → [A, B, C]
Step 2:
Dequeue() → [B, C] (A removed)
Enqueue(D) → [B, C, D]
Enqueue(E) → [B, C, D, E]
Step 3:
Dequeue() → [C, D, E] (B removed)
Dequeue() → [D, E] (C removed)
Enqueue(F) → [D, E, F]
Front item: D (first item in current queue)
Rear item: F (last item added)

Check Your Understanding: Queue Basics

1. What does FIFO stand for and what does it mean for a queue? [2 marks]

Answer

[1 mark] FIFO stands for First In, First Out
[1 mark] It means the first item added to the queue is the first item to be removed from the queue
[Additional] Like a real-world queue: first person in line is first person served

2. What are the two main operations on a queue and what do they do? [2 marks]

Answer

[1 mark] Enqueue: Adds an item to the end (rear) of the queue
[1 mark] Dequeue: Removes an item from the front (start) of the queue
[Additional] Enqueue increases Rear pointer, Dequeue increases Front pointer

3. What value does EndOfQueuePointer have when a queue is empty? [1 mark]

Answer

[1 mark] EndOfQueuePointer = -1 when queue is empty
[Additional] Front pointer would also be -1 or 0 depending on implementation

4. Describe what happens to the pointers during enqueue and dequeue operations. [2 marks]

Answer

[1 mark] Enqueue: EndOfQueuePointer (rear pointer) is incremented before adding value
[1 mark] Dequeue: FrontOfQueuePointer (front pointer) is incremented after removing value
[Additional] Front pointer changes after dequeue, rear pointer changes after enqueue

Queue Implementation Using Arrays

A queue can be implemented using a 1D array and a set of pointers. Since arrays have finite size, we need to handle when the queue becomes full.

Array Implementation Steps

Implementation Steps

Declare a 1D array of suitable size and data type
Declare integer variable for FrontOfQueuePointer
Declare integer variable for EndOfQueuePointer
Initialise FrontOfQueuePointer and EndOfQueuePointer to represent empty queue
Declare integer variable for NumberInQueue and initialise
Declare integer variable for SizeOfQueue and initialize to limit max items
For circular queue manage 'wrap' - pointers reset to first index when reaching maximum

Pointer Changes

Operation	Front Pointer	Rear Pointer	Queue Length
Initial State	1	4	4
After Dequeue (27 removed)	2	4	3
After Enqueue (31 added)	2	5	4

Front pointer changes after dequeue, rear pointer changes after enqueue.

Array Implementation Visualization

See how a queue is stored in a 1D array with front and rear pointers:

Front Pointer: 0

Points to front of queue

Rear Pointer: -1

Points to rear of queue

Queue Size: 0/10

Items in queue / Array capacity

How it works:

Array has fixed size (10 elements in this simulation)
Front pointer starts at 0, rear pointer at -1 (empty queue)
Enqueue: Increment rear pointer, add value at that index
Dequeue: Return value at front pointer, increment front pointer
Problem: As items are removed, front moves right, wasting space at left

Real-Life Example: Cinema Ticket Counter

A cinema ticket counter uses a queue system with a fixed number of service points (like array indices):

Service Points (Array indices 0-9): [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Customer A arrives → Enqueue(A) → [A] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Customer B arrives → Enqueue(B) → [A] [B] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Customer A served → Dequeue() → [ ] [B] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Customer C arrives → Enqueue(C) → [ ] [B] [C] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Problem: Empty space at index 0 can't be reused without moving all customers!

This shows the limitation of simple array implementation - wasted space at the beginning.

Activity 2: Array Queue Operations

Given an array of size 8, trace the operations with front and rear pointers:

Initial: Front = 0, Rear = -1, Array empty
Enqueue(10), Enqueue(20), Enqueue(30)
Dequeue(), Dequeue()
Enqueue(40), Enqueue(50), Enqueue(60)
What are Front and Rear pointer values now?
What's the problem with this implementation?

Solution:

Step 1: Initial state
Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Front = 0, Rear = -1
Step 2: After enqueues
Enqueue(10): Rear = 0, Array[0] = 10
Enqueue(20): Rear = 1, Array[1] = 20
Enqueue(30): Rear = 2, Array[2] = 30
Array: [10] [20] [30] [ ] [ ] [ ] [ ] [ ]
Front = 0, Rear = 2
Step 3: After dequeues
Dequeue(): Return 10, Front = 1
Dequeue(): Return 20, Front = 2
Array: [ ] [ ] [30] [ ] [ ] [ ] [ ] [ ]
Front = 2, Rear = 2
Step 4: More enqueues
Enqueue(40): Rear = 3, Array[3] = 40
Enqueue(50): Rear = 4, Array[4] = 50
Enqueue(60): Rear = 5, Array[5] = 60
Array: [ ] [ ] [30] [40] [50] [60] [ ] [ ]
Front = 2, Rear = 5
Final pointers: Front = 2, Rear = 5
Problem: Array indices 0 and 1 are empty but can't be used! Wasted space.

Check Your Understanding: Array Implementation

1. Why do we need to declare SizeOfQueue when implementing queue with array? [2 marks]

Answer

[1 mark] Arrays have a finite/fixed size
[1 mark] To limit the maximum number of items allowed in the queue
[Additional] To check if queue is full before enqueue operation

2. What is the problem with simple array implementation of queue? [2 marks]

Answer

[1 mark] As items are removed from front, front pointer moves right
[1 mark] Empty spaces at beginning of array cannot be reused
[Additional] This wastes memory space even when queue is not full

3. How do FrontOfQueuePointer and EndOfQueuePointer change during operations? [2 marks]

Answer

[1 mark] FrontOfQueuePointer changes after dequeue operation
[1 mark] EndOfQueuePointer changes after enqueue operation
[Additional] Both pointers only increase (in simple array implementation)

Circular Queues

To solve the problem of wasted space in array implementation, we use a circular queue. The queue is managed as circular to avoid moving the position of items in the array every time an item is removed.

What is a Circular Queue?

Circular Queue Concept

Implemented using array with finite number of elements
Managed as a circular structure
Both frontPointer and rearPointer are used
Pointers "wrap around" to beginning when reaching end of array
Avoids moving items in array when queue position changes
More efficient use of array space

Key Difference:

In circular queue, when pointer reaches last element (upper bound), it wraps to first element (lower bound).

Pointer Wrapping

When rearPointer reaches last array index and there's space at beginning:

After enqueue(57): Rear pointer wraps to index 4

Both pointers wrap to first index (0) when they reach last index (array size - 1).

Important: Understanding Circular Queue Wrapping

Students often struggle with pointer wrapping in circular queues. Here's a clear explanation:

When does wrapping occur?

Enqueue operation: When rearPointer reaches last array index AND front ≠ 0
Dequeue operation: When frontPointer reaches last array index
Pointer assigned to first index (0) when it reaches maximum index
This creates a "circular" effect

How to calculate next position?

Simple formula: nextIndex = (currentIndex + 1) % arraySize
Example: Array size = 5, current = 4
next = (4 + 1) % 5 = 0 (wraps to start)
This works for both enqueue and dequeue
% (modulus) gives remainder after division

Key Insight: Why Circular Queues?

Without circular queue: Front pointer keeps moving right, wasting left space. Array appears "full" even with empty spaces.
With circular queue: Pointers wrap around, reusing empty spaces. All array positions can be used efficiently.

Visualizing the Circle

Index 4 connects back to index 0 - forming a circle!

Circular Queue Simulator

Watch how pointers wrap around in a circular queue with 10 elements:

HeadIndex

TailIndex

Queue Length

Example: Circular queue "MyNumbers" has 10 elements. Current state: HeadIndex = 2, TailIndex = 8

Index:   0   1   2   3   4   5   6   7   8   9
Data:         31  45  89  500 23  2

Empty cells at indices 0,1,9 can be used when pointers wrap around.

Example: Circular Queue Operations

State of queue after operations: Enqueue(23), Enqueue(100), Dequeue(), Dequeue(), Enqueue(50)

Index	0	1	2	3	4	5	6	7	8	9
Initial			31	45	89	500	23	2
Final	50				89	500	23	2	23	100

Initial:

HeadIndex: 2, TailIndex: 8

Final:

HeadIndex: 4, TailIndex: 1

Notice how TailIndex wrapped from 9 to 0 to 1 when adding 50!

Real-Life Example: Bus Station with Circular Platform

A bus station with circular platform (like those at airports) uses circular queue principles:

Platform has 8 bays (0-7) arranged in a circle
Bus A arrives → Bay 0: [Bus A] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Bus B arrives → Bay 1: [Bus A] [Bus B] [ ] [ ] [ ] [ ] [ ] [ ]
Bus C arrives → Bay 2: [Bus A] [Bus B] [Bus C] [ ] [ ] [ ] [ ] [ ]
Bus A departs → Bay 0 empty: [ ] [Bus B] [Bus C] [ ] [ ] [ ] [ ] [ ]
Bus D arrives → Uses Bay 3 (not Bay 0 in simple queue): [ ] [Bus B] [Bus C] [Bus D] [ ] [ ] [ ] [ ]
After more buses... Bay 7 full, next bus uses Bay 0 (wraps around!)

This efficiently uses all platform bays without leaving empty spaces.

Exam Style Question

ESQ# Identify and describe Queue abstract data type.

Answer:

Queue
Linear structure
First in first out structure
Has start and end of queue pointers
Can be circular
Uses enqueue to add item to end of queue
Uses dequeue to remove item from start of queue

Additional question: A circular queue has 8 elements. HeadIndex = 5, TailIndex = 2. How many items are in the queue? Show your calculation.

Solution:

Queue ADT Description

Queue is an Abstract Data Type (ADT)
Linear structure with start and end pointers
Operates on FIFO (First In First Out) principle
Can be implemented as circular queue
Uses enqueue operation to add items to end
Uses dequeue operation to remove items from start

Circular Queue Calculation

For circular queue with HeadIndex = 5, TailIndex = 2, array size = 8:

When TailIndex < HeadIndex, queue wraps around end of array
Number of items = (arraySize - HeadIndex) + (TailIndex + 1)
= (8 - 5) + (2 + 1)
= 3 + 3
= 6 items in queue

Alternative formula: (TailIndex - HeadIndex + arraySize) % arraySize
= (2 - 5 + 8) % 8 = 5 % 8 = 5? Wait, that's not right for this case... Actually when Tail < Head, we need different calculation.

Check Your Understanding: Circular Queues

1. Why is a circular queue more efficient than simple array implementation? [2 marks]

Answer

[1 mark] Avoids moving items in array when queue position changes
[1 mark] Reuses empty spaces at beginning of array by wrapping pointers
[Additional] More efficient use of array space, less memory wasted

2. What does "wrapping" mean in circular queues? [2 marks]

Answer

[1 mark] When pointer reaches last element of array (upper bound)
[1 mark] It is updated to point to first element (lower bound) instead
[Additional] Creates circular movement: ... → index 8 → index 9 → index 0 → index 1 → ...

3. what are HeadIndex and TailIndex after the operations? [2 marks]

Answer

[1 mark] HeadIndex: 4
[1 mark] TailIndex: 1
[Additional] After: Enqueue(23), Enqueue(100), Dequeue(), Dequeue(), Enqueue(50)

4. How do you check if a circular queue is full? [2 marks]

Answer

[1 mark] Check if (TailIndex + 1) % arraySize == HeadIndex
[1 mark] Or check if NumberInQueue == SizeOfQueue
[Additional] In circular queue, full condition is when next position after tail equals head

Key Takeaways

Queue is an Abstract Data Type (ADT) with FIFO (First In, First Out) principle
Items are added to the end (enqueue) and removed from the front (dequeue)
First item added to queue is first item to be removed
Queue has FrontOfQueuePointer (front/start) and EndOfQueuePointer (rear/end)
When queue is empty, EndOfQueuePointer = -1
Queue can be implemented using 1D array with pointers
Front pointer changes after dequeue, rear pointer changes after enqueue
Simple array implementation wastes space as front pointer moves right
Circular queue solves this by wrapping pointers to beginning of array
In circular queue, pointers wrap to first index when reaching last index
Circular queue avoids moving items in array and uses space efficiently
Queue is a linear structure with start and end pointers
Queue can be circular to handle finite array size efficiently
Common applications: printer queues, message buffers, CPU scheduling

Question Bank

1. Explain the FIFO principle and how it applies to queues. [4 marks]

Marking Scheme & Answer

[1 mark] FIFO stands for First In, First Out
[1 mark] First item added to queue is first item to be removed
[1 mark] Like a real-world queue: first person in line is first served
[1 mark] Applied through enqueue (add to end) and dequeue (remove from front) operations
[Additional] Opposite of LIFO (Last In, First Out) used in stacks

2. Describe how a queue is implemented using a 1D array. [5 marks]

Marking Scheme & Answer

[1 mark] Declare a 1D array of suitable size and data type
[1 mark] Declare integer variable for FrontOfQueuePointer
[1 mark] Declare integer variable for EndOfQueuePointer
[1 mark] Initialise pointers to represent empty queue (Front = 0, Rear = -1)
[1 mark] Declare integer variables for NumberInQueue and SizeOfQueue
[Additional] Enqueue: increment rear pointer, add value. Dequeue: return front value, increment front pointer.

3. What is the problem with simple array implementation of queue and how does circular queue solve it? [6 marks]

Marking Scheme & Answer

[2 marks] Problem: As items are dequeued, front pointer moves right, creating empty spaces at beginning of array that cannot be reused
[2 marks] Solution: Circular queue wraps pointers to beginning when they reach end of array
[1 mark] Pointers are updated to point to first element after reaching last element
[1 mark] This avoids moving items and efficiently uses all array positions
[Additional] Example: When rear pointer reaches index 9 (in 10-element array), next enqueue wraps to index 0 if empty

4. Trace the operations on a queue: Start empty, then Enqueue(A), Enqueue(B), Dequeue(), Enqueue(C), Enqueue(D), Dequeue(). What is the queue content? [4 marks]

Marking Scheme & Answer

[1 mark] Start: [] (empty)
[1 mark] Enqueue(A) → [A]
[1 mark] Enqueue(B) → [A, B]
[1 mark] Dequeue() → [B] (A removed)
[1 mark] Enqueue(C) → [B, C]
[1 mark] Enqueue(D) → [B, C, D]
[1 mark] Dequeue() → [C, D] (B removed)

Final queue content: [C, D] (C at front, D at rear)

5. Explain what happens to the pointers during enqueue and dequeue operations. [4 marks]

Marking Scheme & Answer

[2 marks] Enqueue: EndOfQueuePointer (rear pointer) is incremented before adding value to array element where pointer is pointing to
[2 marks] Dequeue: FrontOfQueuePointer (front pointer) is incremented after removing value from front of queue
[Additional] In circular queue, increment includes wrap-around: (current + 1) % arraySize

6. What is an Abstract Data Type (ADT)? Give examples. [4 marks]

Marking Scheme & Answer

[2 marks] An ADT is a collection of data and a set of operations on those data
[2 marks] Examples: stack, queue, and linked list are examples of ADTs
[Additional] ADT defines what operations can be performed, not how they're implemented

7. Circular queue example with HeadIndex=2 and TailIndex=8, how many items are in the queue? [3 marks]

Marking Scheme & Answer

[1 mark] Queue occupies indices 2, 3, 4, 5, 6, 7, 8
[1 mark] That's 7 positions (2 to 8 inclusive)
[1 mark] But from diagram, only 6 items: 31, 45, 89, 500, 23, 2
[Additional] Actually indices 2-7 have data (6 items), index 8 is Tail but empty in diagram

8. What are the key features of a queue data structure? [5 marks]

Marking Scheme & Answer

[1 mark] Linear structure
[1 mark] First In First Out (FIFO) structure
[1 mark] Has start and end of queue pointers (front and rear)
[1 mark] Can be implemented as circular queue
[1 mark] Uses enqueue to add item to end, dequeue to remove from start
[Additional] Items maintain order of insertion

9. When would you use a queue instead of other data structures? Give an example. [4 marks]

Marking Scheme & Answer

[2 marks] When you need to process items in the order they arrive (FIFO)
[1 mark] Example: Printer queue - documents print in order received
[1 mark] Example: Customer service line - first come, first served
[Additional] Other examples: Message buffers, CPU scheduling, breadth-first search

10. Explain the concept of pointer wrapping in circular queues with an example. [5 marks]

Marking Scheme & Answer

[1 mark] Pointer wrapping means when pointer reaches last array element, it goes to first element
[1 mark] For array of size 10: index 9 → next becomes index 0
[1 mark] Formula: nextIndex = (currentIndex + 1) % arraySize
[1 mark] Example: Current TailIndex = 9, array size = 10
[1 mark] After enqueue: TailIndex = (9 + 1) % 10 = 10 % 10 = 0
[Additional] TailIndex went from 9 to 0 to 1 after adding 50