Data Structures and Algorithms

CIS-318
Lab Report no.10
Spring 2023
Obtained Marks
Total Marks

Lab Engineer Signature &

Comments

Student Name
1. Anas Zohrab

Section: A (Electronics)
Experiment No: 10 Date of Submission:
May-15-2023
Experiment Title:
Introduction to Priority Queues and its implementation using
LinkList
Batch: Teacher:
BSEE 2019-23 Dr. Kamran Safdar
Semester Lab Engineer:
8th Mr. Ghaznooq Ahmad

Department of Electrical Engineering

2 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

Table of Contents
Introduction to Priority Queues and its implementation using LinkList ........................................................... 1
10.1 Title: Introduction to Priority Queues and its implementation using Link List ...................................... 3
10.2 Abstract: .................................................................................................................................................. 3
10.3 Objectives: .............................................................................................................................................. 3
10.4 Introduction: ............................................................................................................................................ 3
10.5 Results and Code..................................................................................................................................... 4
1. • void enqueue....................................................................................................................................... 4
2. Result:.................................................................................................................................................... 5
........................................................................................................................................................................ 5
1. • int dequeue()....................................................................................................................................... 5
2. Result:.................................................................................................................................................... 5
........................................................................................................................................................................ 5
• void display() .......................................................................................................................................... 5
3. Result:.................................................................................................................................................... 6
........................................................................................................................................................................ 6
• void Peek() ............................................................................................................................................. 6
4. Result:.................................................................................................................................................... 6
........................................................................................................................................................................ 6
10.6 Home Tasks ............................................................................................................................................ 6
10.7 Discussion and Conclusion: .................................................................................................................... 7
10.8 References: .............................................................................................................................................. 7
3 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

10.1 Title: Introduction to Priority Queues and its implementation

using Link List
10.2 Abstract:
This lab report aims to provide a basic understanding of priority queues and their
implementation using linked lists. Priority queues are data structures that store elements based
on their priority level and allow for efficient retrieval of the highest-priority element. In this
lab, we implemented the basic operations of priority queues using linked lists, including
enqueue, dequeue, display, and isEmpty functions.

10.3 Objectives:
✓ Understanding of priority queues
✓ Implementing the basic operations of priority queues using link list
10.4 Introduction:
Priority Queue :
A priority queue is a data structure that stores elements and allows for efficient retrieval of
the highest-priority element. In a priority queue, each element is assigned a priority value,
and the element with the highest priority is always at the front of the queue.

Priority queues are widely used in computer science, particularly in areas such as operating
systems, network routing, and optimization algorithms. They are useful in any application
where it is necessary to retrieve the next element with the highest priority, such as job
scheduling or task management.

Priority queues can be implemented using a variety of data structures, including heaps, binary
trees, and linked lists. Heaps are particularly well-suited for implementing priority queues
because they provide efficient insert and delete operations while maintaining the heap
property, which guarantees that the highest-priority element is always at the root of the heap.

Figure 1 Priority Queue

Basic Operations:
Enqueue: This operation is used to add a new item to the priority queue. In a priority queue, items
are added based on their priority level. The item with the highest priority is added first, followed by
the item with the next highest priority, and so on. To enqueue an item, the priority of the item is
4 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

compared with the priority of other items already in the queue, and the new item is inserted in the
correct position based on its priority level.

Dequeue: This operation is used to remove an item from the priority queue. In a priority queue, the
item with the highest priority is removed first. To dequeue an item, the priority queue checks the
priority of each item and removes the item with the highest priority. If there are multiple items with
the same highest priority, the priority queue removes the item that was added first.

Display: This operation is used to display the contents of the priority queue. In a priority queue, the
items are displayed in order of their priority level, with the item with the highest priority displayed
first. The display operation typically involves iterating over the priority queue and printing the value
of each item.

IsEmpty: This operation is used to check if the priority queue is empty. In a priority queue, the
queue is considered empty if there are no items in it. The IsEmpty operation typically returns a
Boolean value (true or false) indicating whether or not the queue is empty

10.5 Results and Code

Create a class Queues and implement the following functions

1. • void enqueue
void enqueue(int data, int priority) {
Node* newNode = new Node;
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;

if (isEmpty() || priority < head->priority) {

newNode->next = head;
head = newNode;
}

else {
Node* temp = head;
while (temp->next != NULL && temp->next->priority <=
priority) {
temp = temp->next;
}

newNode->next = temp->next;
temp->next = newNode;
}
}
5 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

2. Result:

Figure 2 adding Elements 20 10 40 and 30 where 20 has the highest priority of 1

1. • int dequeue()
int dequeue() {
if (isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
else {
Node* temp = head;
int data = head->data;
head = head->next;
delete temp;
return data;
}
}
2. Result:

Figure 3 removing element “20” and “10” from the Queue

• void display()
void display() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
6 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

3. Result:

Figure 4 Displaying actions in Queue using Display Funcntion.

• void Peek()
bool isEmpty() {
return (head == NULL);
}
4. Result:

Figure 5 Function returning when the Queue is Empty

10.6 Home Tasks

Q1: What are the uses of priority queues
Priority queues are used in a variety of applications where items need to be processed
in a specific order based on their priority. Some common uses of priority queues include:
• Operating systems use priority queues to schedule tasks based on their priority levels.
• In networking, priority queues are used to prioritize packets and ensure that important
data is sent first.
• In graph algorithms like Dijkstra’s algorithm and Prim’s algorithm, priority queues
are used to store vertices in the order of their distance or weight.
• Priority queues can also be used in simulations and event-driven systems to prioritize
events based on their time stamp or priority level.

Q2: Can priority queues be implemented using arrays? If yes then what are the
advantages or disadvantage of using array.
Array-based implementation:
Yes, priority queues can be implemented using arrays. The main advantage of using arrays is
that they provide constant-time access to any element in the array, which makes it easy to
access the highest-priority element in the queue. However, the main disadvantage of using
arrays is that they have a fixed size, so the size of the priority queue needs to be determined in
advance. This can be inefficient if the size of the priority queue needs to be changed
dynamically during the program's execution. Additionally, if the array becomes full, inserting
a new element into the queue can be expensive because all of the existing elements in the queue
need to be shifted to make room for the new element.
7 Lab 10 : Introduction to Priority Queues and its implementation using LinkList

10.7 Discussion and Conclusion:

The objective of this lab report was to understand priority queues and implement
basic operations of priority queues using a linked list. Priority queues are data structures that
store elements and allow for efficient retrieval of the highest-priority element. The priority
queue implemented in this lab report assigns a priority value to each element, and the element
with the highest priority is always at the front of the queue.

The implementation of the basic operations of the priority queue was done using a
linked list. The basic operations implemented in this lab report are Enqueue, Dequeue, Display,
and IsEmpty. The Enqueue operation adds a new item to the priority queue based on its priority
level, while the Dequeue operation removes an item from the priority queue based on its
priority level. The Display operation is used to display the contents of the priority queue, while
the IsEmpty operation is used to check if the priority queue is empty.

In conclusion, this lab report has successfully achieved its objective of understanding
priority queues and implementing basic operations of priority queues using a linked list.
Priority queues are widely used in computer science and are useful in any application where it
is necessary to retrieve the next element with the highest priority. The implementation of the
basic operations of the priority queue using a linked list provided an efficient way to add and
remove items based on their priority level. This lab report has provided a good understanding
of priority queues and their implementation using a linked list.

10.8 References:
• •Tutorials Point. (n.d.). Priority Queues . Retrieved from
https://www.tutorialspoint.com/data_structures_algorithms/queue_data_structure.htm
• •Programiz. (n.d.). Priority Queues in C++. Retrieved from
https://www.programiz.com/dsa/queue
• •GeeksforGeeks. (n.d.). Priority Queues. Retrieved from https://www.geeksforgeeks.org/queue-
data-structure/