Queues (OCR A Level Computer Science)

Revision Note

Written by: Jennifer Page

Reviewed by: James Woodhouse

Implementing Linear Queues

How Do You Program a Queue?

To recap the main operations of Queues and how they work, follow this link
When programming a queue, the main operations listed below must be included in your program
- Initialise the queue
- Enqueue
- Dequeue
- Peek

Algorithm to Implement a Linear Queue

The code below initialises an array and index pointers to service a linear queue
The constant MAX_SIZE informs the size of the array
The front index pointer is initialised to 0 and the rear index pointer is initialised to -1
The rear index pointer will be incremented every time you add an item to the queue, so the initial value will ensure the first item is added into the first position of the array (index 0)
Once the first item has been added, both front and rear will correctly point to the item in the array

Pseudocode	Python	Java
`MAX_SIZE = 6` `ARRAY queue[max_size]` `front = 0` `rear = -1`	`MAX_SIZE = 6` `queue[]` `front = 0` `rear = -1`	`public class Main {` `public static final int MAX_SIZE = 6;` `public static ArrayList<Integer> queue = new ArrayList<>();` `public static int front = 0;` `public static int rear = -1;` `public static void main(String[] args) {` `// Your code here` `}` `}`

Pseudocode

Python

Java

MAX_SIZE = 6

ARRAY queue[max_size]

front = 0

rear = -1

MAX_SIZE = 6

queue[]

front = 0

rear = -1

public class Main {

public static final int MAX_SIZE = 6;

public static ArrayList<Integer> queue = new ArrayList<>();

public static int front = 0;

public static int rear = -1;

public static void main(String[] args) {

// Your code here

}

EnQueue Data

Before adding an item to the queue you need to check that the queue is not full
When the rear index pointer is pointing to the final space in the array there is no room to add new items
A subroutine isFull() is used to carry out the check.
If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue

Pseudocode	Python	Java
`FUNCTION isFull(rear)` `IF(rear+1) == MAX_SIZE THEN` `RETURN True` `ELSE` `RETURN False` `ENDIF` `ENDFUNCTION` `FUNCTION enqueue(queue, rear, data)` `IF isFull(rear) == True THEN` `PRINT (“Full”)` `ELSE` `rear = rear + 1` `queue[rear] = data` `ENDIF` `RETURN rear` `ENDFUNCTION`	`def isFull(rear):` `if rear + 1 == MAX_SIZE:` `return True` `else:` `return False` `def enqueue(queue, rear, data):` `if isFull(rear):` `print("Full")` `else:` `rear = rear + 1` `queue[rear] = data` `return rear` `# Example usage` `queue = [None] * MAX_SIZE` `rear = -1` `rear = enqueue(queue, rear, 10)` `rear = enqueue(queue, rear, 20)` `rear = enqueue(queue, rear, 30)` `print(queue) # [10, 20, 30]`	`public static boolean isFull(int rear) {` `if (rear + 1 == MAX_SIZE) {` `return true;` `} else {` `return false;` `}` `}` `public static int enqueue(int[] queue, int rear, int data) {` `if (isFull(rear)) {` `System.out.println("Full");` `} else {` `rear = rear + 1;` `queue[rear] = data;` `}` `return rear;` `}`

Pseudocode

Python

Java

FUNCTION isFull(rear)

IF(rear+1) == MAX_SIZE THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION enqueue(queue, rear, data)

IF isFull(rear) == True THEN

PRINT (“Full”)

ELSE

rear = rear + 1

queue[rear] = data

ENDIF

RETURN rear

ENDFUNCTION

def isFull(rear):

if rear + 1 == MAX_SIZE:

return True

else:

return False

def enqueue(queue, rear, data):

if isFull(rear):

print("Full")

else:

rear = rear + 1

queue[rear] = data

return rear

# Example usage

queue = [None] * MAX_SIZE

rear = -1

rear = enqueue(queue, rear, 10)

rear = enqueue(queue, rear, 20)

rear = enqueue(queue, rear, 30)

print(queue) # [10, 20, 30]

public static boolean isFull(int rear) {

if (rear + 1 == MAX_SIZE) {

return true;

} else {

return false;

}

public static int enqueue(int[] queue, int rear, int data) {

if (isFull(rear)) {

System.out.println("Full");

} else {

rear = rear + 1;

queue[rear] = data;

}

return rear;

}

DeQueue Data

Before taking an item from the queue you need to make sure that the queue is not empty
A subroutine isEmpty() can be defined for this purpose
The subroutine will check whether the front index pointer is ahead of the rear index pointer
If the queue is not empty the item at the front of the queue is returned and front is incremented by 1

Pseudocode	Python	Java
`FUNCTION isEmpty(front, rear)` `IF front > rear THEN` `RETURN True` `ELSE` `RETURN False` `ENDIF` `ENDFUNCTION` `FUNCTION dequeue(queue, rear, front)` `IF isEmpty(front, rear) THEN` `PRINT (“Empty”)` `dequeuedItem = Null` `ELSE` `dequeuedItem = queue[front]` `front = front + 1` `ENDIF` `RETURN (dequeuedItem, front)` `ENDFUNCTION`	`def isEmpty(front, rear):` `if front > rear:` `return True` `else:` `return False` `def dequeue(queue, rear, front):` `if isEmpty(front, rear):` `print("Empty")` `dequeuedItem = None` `else:` `dequeuedItem = queue[front]` `front = front + 1` `return dequeuedItem, front` `# Example usage` `MAX_SIZE = 100` `queue = [10, 20, 30, 40, 50]` `front = 0` `rear = len(queue) - 1` `dequeuedItem, front = dequeue(queue, rear, front)` `print("Dequeued item:", dequeuedItem)` `print("Front:", front)` `dequeuedItem, front = dequeue(queue, rear, front)` `print("Dequeued item:", dequeuedItem)` `print("Front:", front)`	`import java.util.Arrays;` `public class Main {` `public static boolean isEmpty(int front, int rear) {` `if (front > rear) {` `return true;` `} else {` `return false;` `}` `}` `public static Object[] dequeue(int[] queue, int rear, int front) {` `if (isEmpty(front, rear)) {` `System.out.println("Empty");` `Object[] result = { null, front };` `return result;` `} else {` `Object[] result = { queue[front], front + 1 };` `return result;` `}` `}` `public static void main(String[] args) {` `int MAX_SIZE = 100;` `int[] queue = { 10, 20, 30, 40, 50 };` `int front = 0;` `int rear = queue.length - 1;` `Object[] dequeuedResult = dequeue(queue, rear, front);` `Object dequeuedItem = dequeuedResult[0];` `front = (int) dequeuedResult[1];` `System.out.println("Dequeued item: " + dequeuedItem);` `System.out.println("Front: " + front);` `dequeuedResult = dequeue(queue, rear, front);` `dequeuedItem = dequeuedResult[0];` `front = (int) dequeuedResult[1];` `System.out.println("Dequeued item: " + dequeuedItem);` `System.out.println("Front: " + front);` `}` `}`

Pseudocode

Python

Java

FUNCTION isEmpty(front, rear)

IF front > rear THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION dequeue(queue, rear, front)

IF isEmpty(front, rear) THEN

PRINT (“Empty”)

dequeuedItem = Null

ELSE

dequeuedItem = queue[front]

front = front + 1

ENDIF

RETURN (dequeuedItem, front)

ENDFUNCTION

def isEmpty(front, rear):

if front > rear:

return True

else:

return False

def dequeue(queue, rear, front):

if isEmpty(front, rear):

print("Empty")

dequeuedItem = None

else:

dequeuedItem = queue[front]

front = front + 1

return dequeuedItem, front

# Example usage

MAX_SIZE = 100

queue = [10, 20, 30, 40, 50]

front = 0

rear = len(queue) - 1

dequeuedItem, front = dequeue(queue, rear, front)

print("Dequeued item:", dequeuedItem)

print("Front:", front)

dequeuedItem, front = dequeue(queue, rear, front)

print("Dequeued item:", dequeuedItem)

print("Front:", front)

import java.util.Arrays;

public class Main {

public static boolean isEmpty(int front, int rear) {

if (front > rear) {

return true;

} else {

return false;

}

public static Object[] dequeue(int[] queue, int rear, int front) {

if (isEmpty(front, rear)) {

System.out.println("Empty");

Object[] result = { null, front };

return result;

} else {

Object[] result = { queue[front], front + 1 };

return result;

}

public static void main(String[] args) {

int MAX_SIZE = 100;

int[] queue = { 10, 20, 30, 40, 50 };

int front = 0;

int rear = queue.length - 1;

Object[] dequeuedResult = dequeue(queue, rear, front);

Object dequeuedItem = dequeuedResult[0];

front = (int) dequeuedResult[1];

System.out.println("Dequeued item: " + dequeuedItem);

System.out.println("Front: " + front);

dequeuedResult = dequeue(queue, rear, front);

dequeuedItem = dequeuedResult[0];

front = (int) dequeuedResult[1];

System.out.println("Dequeued item: " + dequeuedItem);

System.out.println("Front: " + front);

}

Implementing Circular Queues

Algorithm to Implement a Circular Queue

When you manipulate the items in a circular queue you must be able to advance the index pointers in such a way that they will reset to 0 once the end has been reached

(pointer + 1) MOD MAX_SIZE

This can be used to calculate the new position for the index pointer
Where the pointer is front or rear and max_size is the maximum number of items in the queue.

Let’s imagine there is an array with 7 items.

Initial Position	Pointer + 1	(Pointer + 1) MOD 7	New Position
0	1	1	1
1	2	2	2
2	3	3	3
3	4	4	4
4	5	5	5
5	6	6	6
6	7	0	0

When the index pointer references the last position in the array, position 6, the next position is calculated as (6+1) MOD 7 which gives the result 0
This allows the index pointer to move back to the reference at the start of the array

Initialise Circular Queue

The initialisation is the same as a linear queue apart from you initialise the front index to -1 as this will allow you to be certain that you have an empty queue

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

MAX_SIZE = 4

cQueue[]

front = -1

rear = -1

public class CircularQueue {

private static final int MAX_SIZE = 4;

private int[] cQueue = new int[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

Enqueue Circular Queue

Before an item can be enqueued the array needs to be checked to see if it’s full
It will be full if the next position to be used is already occupied by the item at the front of the queue
If the queue is not full then the rear index pointer must be adjusted to reference the next free position so that the new item can be added

Pseudocode	Python	Java
`MAX_SIZE = 4` `ARRAY cQueue[max_size]` `front = -1` `rear = -1` `FUNCTION is_full(front, rear)` `IF (rear + 1) MOD MAX_SIZE == front THEN` `RETURN True` `ELSE` `RETURN False` `ENDIF` `ENDFUNCTION` `FUNCTION enqueue(queue, front, rear, data)` `IF is_full(front, rear) == True THEN` `PRINT("Queue is full")` `ELSE` `rear = (rear + 1) MOD MAX_SIZE` `queue[rear] = data` `IF front = -1 THEN // First item to be queued` `front = 0` `ENDIF` `ENDIF` `RETURN (front, rear)` `ENDFUNCTION`	`MAX_SIZE = 4` `cQueue = [None] * MAX_SIZE` `front = -1` `rear = -1` `def is_full(front, rear):` `if (rear + 1) % MAX_SIZE == front:` `return True` `else:` `return False` `def enqueue(queue, front, rear, data):` `if is_full(front, rear):` `print("Queue is full")` `else:` `rear = (rear + 1) % MAX_SIZE` `queue[rear] = data` `if front == -1: # First item to be queued` `front = 0` `return front, rear`	`public class CircularQueue {` `private static final int MAX_SIZE = 4;` `private int[] cQueue = new int[MAX_SIZE];` `private int front = -1;` `private int rear = -1;` `public static void main(String[] args) {` `CircularQueue circularQueue = new CircularQueue();` `// Use the circularQueue object to perform operations on the circular queue` `}` `}`

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

FUNCTION is_full(front, rear)

IF (rear + 1) MOD MAX_SIZE == front THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION enqueue(queue, front, rear, data)

IF is_full(front, rear) == True THEN

PRINT("Queue is full")

ELSE

rear = (rear + 1) MOD MAX_SIZE

queue[rear] = data

IF front = -1 THEN // First item to be queued

front = 0

ENDIF

RETURN (front, rear)

ENDFUNCTION

MAX_SIZE = 4

cQueue = [None] * MAX_SIZE

front = -1

rear = -1

def is_full(front, rear):

if (rear + 1) % MAX_SIZE == front:

return True

else:

return False

def enqueue(queue, front, rear, data):

if is_full(front, rear):

print("Queue is full")

else:

rear = (rear + 1) % MAX_SIZE

queue[rear] = data

if front == -1: # First item to be queued

front = 0

return front, rear

public class CircularQueue {

private static final int MAX_SIZE = 4;

private int[] cQueue = new int[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

DeQueue Circular Queue

Before dequeuing the array needs to be checked if it’s empty. If the queue is not empty then the item at the front is dequeued
If this is the only item that was in the queue, the rear and front pointers are reset
Otherwise the pointer moves to reference the next item in the queue

Pseudocode

Python

Java

MAX_SIZE = 4

ARRAY cQueue[max_size]

front = -1

rear = -1

FUNCTION is_empty(rear)

IF front == -1 THEN

RETURN True

ELSE

RETURN False

ENDIF

ENDFUNCTION

FUNCTION dequeue(queue, front, rear)

IF is_empty(rear) == True THEN

PRINT("Queue is empty - nothing to dequeue")

dequeued_item = Null

ELSE

dequeued_item = queue[front]

// Check if the queue is empty

IF front == rear THEN

front = -1

rear = -1

ELSE

front = (front + 1) MOD maxsize

ENDIF

RETURN (dequeued_item, front, rear)

ENDFUNCTION

def is_empty(front):

if front == -1:

return True

else:

return False

def dequeue(queue, front, rear):

if is_empty(front):

print("Queue is empty - nothing to dequeue")

dequeued_item = None

else:

dequeued_item = queue[front]

if front == rear:

front = -1

rear = -1

else:

front = (front + 1) % MAX_SIZE

return dequeued_item, front, rear

public class CircularQueue {

private static final int MAX_SIZE = 4;

private Object[] cQueue = new Object[MAX_SIZE];

private int front = -1;

private int rear = -1;

public static void main(String[] args) {

CircularQueue circularQueue = new CircularQueue();

// Use the circularQueue object to perform operations on the circular queue

}

private boolean isEmpty(int front) {

if (front == -1) {

return true;

} else {

return false;

}

private void dequeue(Object[] queue, int front, int rear) {

if (isEmpty(front)) {

System.out.println("Queue is empty - nothing to dequeue");

Object dequeuedItem = null;

} else {

Object dequeuedItem = queue[front];

if (front == rear) {

front = -1;

rear = -1;

} else {

front = (front + 1) % MAX_SIZE;

}

Implementing Priority Queues

Algorithm to Implement a Priority Queue

A priority queue is where each item in the queue has a priority
When new items are added, they are inserted ahead of those with a lower priority and behind items of equal priority
If you want to implement a priority queue it is best to use OOP
Encapsulating the data and methods within class definitions provides a neat solution and once written, the class can be reused in other applications that require a queue

Pseudocode

FUNCTION enqueue(queue, element, priority)

// Insert the element into the queue based on its priority

// Higher priority elements are placed towards the front

IF queue is empty OR priority is higher than the first element's priority

Insert element at the front of the queue

ELSE IF priority is lower than or equal to the last element's priority

Insert element at the end of the queue

ELSE

Find the appropriate position in the queue to insert the element based on priority

Shift the elements to the right to make space for the new element

Insert the element at the determined position

ENDIF

ENDFUNCTION

FUNCTION dequeue(queue)

// Remove and return the element with the highest priority from the queue

IF queue is empty

Return an error indicating that the queue is empty

ELSE

Remove and return the element from the front of the queue

ENDIF

ENDFUNCTION

FUNCTION peek(queue)

// Return the element with the highest priority without removing it from the queue

IF queue is empty

Return an error indicating that the queue is empty

ELSE

Return the element from the front of the queue

ENDIF

ENDFUNCTION

FUNCTION is_empty(queue)

// Check if the queue is empty

IF queue is empty

Return True

ELSE

Return False

ENDIF

ENDFUNCTION

Python

class PriorityQueue:

def __init__(self):

self.queue = []

def enqueue(self, element, priority):

# Insert the element into the queue based on its priority

# Higher priority elements are placed towards the front

if len(self.queue) == 0 or priority > self.queue[0][1]:

self.queue.insert(0, (element, priority))

elif priority <= self.queue[-1][1]:

self.queue.append((element, priority))

else:

index = 0

while index < len(self.queue) and priority <= self.queue[index][1]:

index += 1

self.queue.insert(index, (element, priority))

def dequeue(self):

# Remove and return the element with the highest priority from the queue

if self.is_empty():

raise IndexError("Queue is empty - nothing to dequeue")

else:

return self.queue.pop(0)[0]

def peek(self):

# Return the element with the highest priority without removing it from the queue

if self.is_empty():

raise IndexError("Queue is empty - nothing to peek")

else:

return self.queue[0][0]

def is_empty(self):

# Check if the queue is empty

return len(self.queue) == 0

Java

import java.util.ArrayList;

import java.util.List;

class PriorityQueue {

private List<Element> queue;

public PriorityQueue() {

this.queue = new ArrayList<>();

}

public void enqueue(Object element, int priority) {

// Insert the element into the queue based on its priority

// Higher priority elements are placed towards the front

if (queue.isEmpty() || priority > queue.get(0).getPriority()) {

queue.add(0, new Element(element, priority));

} else if (priority <= queue.get(queue.size() - 1).getPriority()) {

queue.add(new Element(element, priority));

} else {

int index = 0;

while (index < queue.size() && priority <= queue.get(index).getPriority()) {

index++;

}

queue.add(index, new Element(element, priority));

}

public Object dequeue() {

// Remove and return the element with the highest priority from the queue

if (isEmpty()) {

throw new IndexOutOfBoundsException("Queue is empty - nothing to dequeue");

} else {

return queue.remove(0).getElement();

}

public Object peek() {

// Return the element with the highest priority without removing it from the queue

if (isEmpty()) {

throw new IndexOutOfBoundsException("Queue is empty - nothing to peek");

} else {

return

Last updated: 12 September 2024

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Test yourself

Did this page help you?

Previous:StacksNext:Linked Lists

Queues (OCR A Level Computer Science)

Revision Note

Implementing Linear Queues

How Do You Program a Queue?

Algorithm to Implement a Linear Queue

EnQueue Data

DeQueue Data

Implementing Circular Queues

Algorithm to Implement a Circular Queue

Initialise Circular Queue

Enqueue Circular Queue

DeQueue Circular Queue

Implementing Priority Queues

Algorithm to Implement a Priority Queue

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

1. The Characteristics of Contemporary Processors, Input, Output & Storage Devices

1.1 Structure & Function of the Processor

Components of the CPU

Fetch-Decode-Execute Cycle

CPU Performance

Pipelining

Von Neumann & Harvard Architecture

1.2 Types of Processor

CISC vs RISC

Graphics Processing Unit (GPU)

Multicore & Parallel Processors

1.3 Input, Output & Storage

Input, Output & Storage

RAM & ROM

2. Software & Software Development

2.1 Systems Software

Operating Systems

Memory Management

System Interrupts

Scheduling

Types of Operating System

BIOS

Device Drivers

Virtual Machines

2.2 Applications Generation

Application Software

Utility Software

Open Source & Closed Source Software

Translators

Stages of Compilation

Libraries, Linkers & Loaders

2.3 Software Development

Waterfall Lifecycle

Agile Programming

Spiral Model

Rapid Application Development (RAD)

Comparing Software Development Models

2.4 Types of Programming Language

Programming Paradigms

Procedural Programming

Assembly Language & Little Man Computer

Modes of Addressing

2.5 Object Oriented Languages

Classes (OOP)

Objects (OOP)

Methods (OOP)

Attributes (OOP)

Inheritance (OOP)

Encapsulation (OOP)

Polymorphism (OOP)

3. Exchanging Data

3.1 Compression, Encryption & Hashing

Lossy & Lossless Compression

Run Length Encoding & Dictionary Coding

Symmetric vs Asymmetric Encryption

Hashing

3.2 Databases

Relational Databases

Data Normalisation

Entity Relationship Diagrams

Capturing, Selecting, Managing & Exchanging Data

SQL

Referential Integrity