UNIT III LINEAR DATA STRUCTURES

Abstract Data Types (ADTs) – List ADT – Array-Based Implementation – Linked List –
Doubly- Linked Lists – Circular Linked List – Stack ADT – Implementation of Stack –
Applications – Queue ADT – Priority Queues – Queue Implementation – Applications.

Introduction to Data Structure

Definition: The data structure can be defined as the collection of elements and all the possible operations
which are required for those set of elements.

For example: Consider a set of elements which are required to store in an array. Various operations such
as reading of the elements and storing them at appropriate index can be performed. If we want to access
any particular element then that element can be retrieved from the array. Thus reading, printing, searching
would be the operations required to perform these tasks for the elements. Thus data object integer elements
and set of operations form the data structure-array.

Types of Data Structures

The data structures can be divided into two basic types Primitive and Non primitive data structures The
Fig. 3.1.1. shows various types of data structures.

Figure 1: Types of Data Structure

Linear data structures are the data structures in which data is arranged in a list or in a straight sequence.
For example: Arrays, List.
Non linear data structures are the data structures in which data may be arranged in hierarchical manner.
For example: Trees, Graphs

1. Abstract Data Types (ADTs)

 An Abstract Data Type (ADT) in data structures is a theoretical model that defines
a data type purely by its behavior from the user's perspective, not by its
implementation.

1
 It specifies the operations that can be performed on the data and the rules for those
operations, without revealing how the data is stored or the operations are carried
out internally.

 Examples include Stack (LIFO behavior), Queue (FIFO behavior) and List
(sequence of elements). ADTs help in designing efficient algorithms by focusing
on what data does, rather than how it does it.

ADT Operations
While modeling the problems the necessary details are separated out from the unnecessary
details. This process of modeling the problem is called abstraction.

Figure 2: Abstract Modelling

The model defines an abstract view to the problem. Thus the model focuses only on related
problem.

Various Abstract Data Type operations are

1. Create: This operation creates the database

2. Display: This operation is for displaying all the elements of the data structure.
3. Insertion: By this operation the element can be inserted at any desired position.
4. Deletion: By this operation any desired element can be deleted from the data structure.
5. Modification: This operation modifies the desired element's value by any desired new
value.
ADT Data Structures
The ADT operations are carried out with the help of data structure. This part describes the
structure of the data used in the ADT in an informal way. Various data structures that can
be used for ADT are Arrays, Set, Linked list, Stack, Queues and so on.
Examples:
1. ADT for Set
To write ADT for a set of integers, use following method
2
AbstractDataType Set
{
Instances: Set is a collection of integer type of elements.
Preconditions: none
Operations:
1. Store (): This operation is for storing the integer element in a set.
2. Retrieve (): This operation is for retrieving the desired element from the given set.
3. Display (): This operation is for displaying the contents of set.
}
It begin with keyword AbstractDataType which is then followed by name of the data
structure. Using Preconditions or Postconditions to mention specific conditions that must
be satisfied before or after execution of corresponding function. Then a listing of all the
required operations must be given.
2. ADT for Arrays
AbstractDataType Array
{
Instances: An array A of some size, index i and total number of elements in the array n.
Operations:
1. Store () - This operation stores the desired elements at each successive location.
2. display () This operation displays the elements of the array.
}

2. List ADT
 List is a collection of elements in sequential order.
 In memory to store the list in two ways,
 One way is to store the elements in sequential memory locations. This is known as
arrays.
 And the other way is, we can use pointers or links to associate the elements
sequentially. This known as Linked Lists.

3
In ADT the implementation details are hidden. Hence the ADT will be -

AbstractDataType List
{
Instances: List is a collection of elements which are arranged in a linear manner.
Operations: Various operations that can be carried out on list are -
1. Insertion: This operation is for insertion of element in the list.
2. Deletion: This operation removed the element from the list.
3. Searching: Based on the value of the key element the desired element can be searched.
4. Modification: The value of the specific element can be changed without changing its
location.
5. Display: The list can be displayed in forward or in backward manner.
}

The List can be implemented by two ways

1. Array based implementation
2. Linked based implementation

3. Array Based Implementation

In an array-based implementation of the List ADT, the list is represented using a

fixed-size array. The elements are stored in contiguous memory locations and each element
can be accessed directly by its index.

To show the list using arrays it have 'data' and 'link' fields in the array.

The array can be created as array of structure as

struct node {
int data;
int next;
} a[10];

4
• For instance: Consider a list of (10,20,30,40,50). It can be store it in arrays as follows:

Figure: Static Linked List

First node. The next field in this node gives the index as 0. Then we get the address of
next node. We can further trace the list using next field.
Last node. The next field gives the index as - 1 and - 1 is not any subscript in the array.
Hence - 1 is taken as end of the list.
• Various operations that can be performed on static linked list are:
1. Creation of list.
2. Display of list.
3. Insertion of any element in the list.
4. Deletion of any element from the list.
5. Searching of desired element in the list.
1. Creation of list
The list can be created by placing the node of list in an array. Each node consists of two
fields 'data' and 'next' pointer. We need to give the address of starting node which is to be
placed in the array.
Thus the list can be created as follows

5
While creating the list we have to first enter
the location in an array where the first node
is placed and then input the pair: data and
next.

Int Create()
{
int head,i;
printf("\n Enter the index for first node");
scanf("%d", &i);
head=i;
while(i!= -1)/*means terminate*/
{
Printf(“\n Enter the data and index of the first element”);
Scanf(“%d %d”, &a[i].data, &a[i].next);
i=a[i].next;
}
return head; }
2. Display
After creation to display the list. Normally when the list is displayed simply the data fields
are to be displayed.
void Display(int i)
{ printf("(");
while(i!= -1) { if(a[i].data==-1) /*no data item present at a[i]*/
printf(" ");
else
{ printf("%d, ",a[i].data); }
i=a[i].next; }
printf(" NULL)"); }

6
3. Insertion of a node
Given a Linked List, the task is to insert a new node in this given Linked List at the
following positions:
 At the front of the linked list
 After a given node.
 At a specific position.
 At the end of the linked list.
Insert a Node at the Front/Beginning of Linked List
To insert a new node at the front, we create a new node and point its next reference to the
current head of the linked list.

Insert a Node after a Given Node in Linked List

To insert a new node after a specific node, first locate that node. Once find it, to set the new
node’s next reference to point to the node that follows the given node. Then, update the
given node’s next to point to the new node. This requires traversing the list to find the
specified node.

Insert a Node at the End of Linked List

Inserting at the end involves traversing the entire list until to reach the last node. We then
set the last node’s next reference to point to the new node, making the new node the last
element in the list.

7
4. Deletion of a node
Deleting a node in a Linked List is an important operation and can be done in three main
ways: removing the first node, removing a node in the middle or removing the last node.

Example: Implementation of various List operations using arrays

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // Define the maximum size of the array
// Structure to represent the list
typedef struct {
int array[MAX_SIZE]; // Array to hold list elements
int size; // Current size of the list
} ArrayList;
// Function to initialize the list
void init(ArrayList *list) {
list->size = 0; // Set initial size to 0
}
// Function to insert an element at a given index
void insert(ArrayList *list, int index, int value) {
if (list->size >= MAX_SIZE) { // Check if array is full
8
printf("Array is full, cannot insert.\n");
return; }
if (index < 0 || index > list->size) { // Check for valid index
printf("Index out of bounds.\n");
return; }
// Shift elements to the right to create space for the new element
for (int i = list->size; i > index; i--) {
list->array[i] = list->array[i - 1]; }
list->array[index] = value; // Insert the new element
list->size++; // Increment the size of the list
}
// Function to delete an element at a given index
void delete(ArrayList *list, int index) {
if (index < 0 || index >= list->size) { // Check for valid index
printf("Index out of bounds.\n");
return; }
// Shift elements to the left to fill the gap
for (int i = index; i < list->size - 1; i++) {
list->array[i] = list->array[i + 1];
}
list->size--; // Decrement the size of the list
}
// Function to access an element at a given index
int access(ArrayList *list, int index) {
if (index < 0 || index >= list->size) { // Check for valid index
printf("Index out of bounds.\n");
return -1; // Return -1 if the index is out of bounds

9
}
return list->array[index]; // Return the element at the index
}
// Function to display the list
void display(ArrayList *list) {
if (list->size == 0) {
printf("List is empty.\n");
return;
}
for (int i = 0; i < list->size; i++) {
printf("%d ", list->array[i]);
}
printf("\n");
}
int main() {
ArrayList list;
int choice, index, value;
init(&list); // Initialize the list
do {
// Display the menu
printf("\nMenu:\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Access\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");

10
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter index to insert: ");
scanf("%d", &index);
printf("Enter value to insert: ");
scanf("%d", &value);
insert(&list, index, value);
break;
case 2:
printf("Enter index to delete: ");
scanf("%d", &index);
delete(&list, index);
break;
case 3:
printf("Enter index to access: ");
scanf("%d", &index);
value = access(&list, index);
if (value != -1) {
printf("Element at index %d: %d\n", index, value);
}
break;
case 4:
printf("List contents: ");
display(&list);
break;
case 5:

11
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 5);
return 0;
}
4. Linked List
A linked list is a set of nodes where each node has two fields 'data' and a 'link'. Where data
field stores the actual piece of information and 'link' field is used to point to next node.
Basically link field is the address only.
• Note that the link field of last node consists of 'NULL' which indicates end of linked list.

Types of Linked list

1. Singly Linked list
2. Doubly Linked list

Singly Linked List

In a singly linked list, each node contains a value and a pointer to the next node in the
sequence. The last node in the list has a pointer to NULL, indicating the end of the list.

Figure: Singly linked list

12
5. Doubly Linked list

In a Singly Linked List, traversal is possible only in one direction, from head to tail.
Reverse traversal, i.e., from tail to head, is not possible because each node contains the
address of the next node but lacks any reference to its previous nodes. To overcome this
limitation, a Doubly Linked List can be used.
A doubly linked list is an enhancement of a singly linked list in which each node
consists of 3 components:
 a pointer *prev : address of the previous node
 data : data item
 a pointer *next : address of next node

Representation of a Doubly Linked List in Data Structures

In the given figure,

 A doubly linked list consists of nodes where each node contains a value and two pointers:
“prev”, pointing to the previous node and
“next”, pointing to the next node.
 This structure allows for traversal in both directions. The prev pointer of the first (or
head) node in the list points to “NULL”, indicating the start of the list, while the next
pointer of the last (or tail) node points to NULL, marking the end of the list.
 It is also referred to as a two-way linked list due to the presence of two pointers.
Syntax:
struct node {
int data;
struct node *next;
struct node *prev;
}

13
Operations on Doubly Linked List
 Traversal in Doubly Linked List
 Searching in Doubly Linked List
 Finding Length of Doubly Linked List
Insertion in Doubly Linked List:
 Insertion at the beginning of Doubly Linked List
 Insertion at the end of the Doubly Linked List
 Insertion at a specific position in Doubly Linked List
Deletion in Doubly Linked List:
 Deletion of a node at the beginning of Doubly Linked List
 Deletion of a node at the end of Doubly Linked List
 Deletion of a node at a specific position in Doubly Linked List
Example
#include <stdio.h>
#include <stdlib.h>
// Node structure for doubly linked list
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end of the doubly linked list
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
struct Node* temp = *head;
if (*head == NULL) {
*head = newNode;
return; }
14
while (temp->next != NULL) {
temp = temp->next; }
temp->next = newNode;
newNode->prev = temp;
}
// Function to print the doubly linked list
void printList(struct Node* head) {
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printList(head);
return 0;
}
Output: Doubly Linked List: 10 20 30

6. Circular Linked list

A Circular Linked List is a variation of a linked list in which the last node points back to
the first node instead of NULL. This allows for continuous traversal of the list, as there is
no distinct end; after reaching the last node, the list loops back to the beginning.

15
Operations on Circular Singly linked list:
Insertion
Insertion at beginning: Adding a node into circular singly linked list at the beginning.
Insertion at the end: Adding a node into circular singly linked list at the end.

Deletion & Traversing

Deletion at beginning: Removing the node from circular singly linked list at the beginning.
Deletion at the end : Removing the node from circular singly linked list at the end.
Searching: Compare each element of the node with the given item and return the location at
which the item is present in the list otherwise return null.
Traversing: Visiting each element of the list at least once in order to perform some specific
operation.
7. Stack ADT
A stack is a linear data structure where elements are stored in the LIFO (Last In First Out)
principle where the last element inserted would be the first element to be deleted. A stack is
an Abstract Data Type (ADT), that is popularly used in most programming languages. It is
named stack because it has the similar operations as the real-world stacks, for example − a
pack of cards or a pile of plates, etc.

Working of Stack
A stack operates on the Last-In-First-Out (LIFO) principle. As shown in the figure below,
the stack consists of five memory blocks, giving it a size of 5. Consider storing elements
in this stack, starting from an empty state. The process involves pushing elements one by
one into the stack until it reaches its full capacity.

16
Since the stack has a size of 5 and is now full, it is evident that elements were added starting
from the bottom and extending to the top. As elements were pushed onto the stack, they
were inserted from the bottom up, filling the stack in a Last-In-First-Out (LIFO) manner.
Standard Stack Operations
The following are some common operations implemented on the stack:
push(): When we insert an element in a stack then the operation is known as a push. If the
stack is full then the overflow condition occurs.
pop(): When we delete an element from the stack, the operation is known as a pop. If the
stack is empty means that no element exists in the stack, this state is known as an underflow
state.
isEmpty(): It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.'

PUSH operation
The steps involved in the PUSH operation is given below:
o Before inserting an element in a stack, we check whether the stack is full.
o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.

17
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position of
the top.
o The elements will be inserted until we reach the max size of the stack.

POP operation
The steps involved in the POP operation is given below:
o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then the underflow condition
occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

18
Example: Stack Insertion: push()
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is full*/

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

/* Function to insert into the stack */

int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
19
/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");

// print stack data

for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
return 0;
}

Example 2: Stack Deletion: pop()

#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;

/* Check if the stack is empty */

int isempty(){
if(top == -1)
return 1;
else
return 0;
}

/* Check if the stack is full*/

int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}

20
/* Function to delete from the stack */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}

/* Function to insert into the stack */

int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}

/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");

// print stack data

for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
}
/*printf("Element at top of the stack: %d\n" ,peek());*/
printf("\nElements popped: \n");

// print stack data

21
while(!isempty()) {
int data = pop();
printf("%d ",data);
}
return 0;
}

A stack is a data structure used in various applications, including:

 Expression Evaluation: Used to convert and evaluate infix, postfix, and prefix
expressions.
 Function Call Management: Manages function calls and returns in programming through
the call stack.
 Undo Mechanism: Implements undo features in software by storing previous states.
 Syntax Parsing: Helps in parsing expressions in compilers and interpreters.
 Backtracking: Used in algorithms like maze-solving, where previous decisions are stored
for backtracking.

8. Queue ADT
A Queue is an Abstract Data Type (ADT) in data structures that follows the First-In-First-
Out (FIFO) principle. This means that the first element added to the queue will be the first
one to be removed.

Basic Operations of Queue Data Structure

 Enqueue (Insert): Adds an element to the rear of the queue.
 Dequeue (Delete): Removes and returns the element from the front of the queue.
 Peek: Returns the element at the front of the queue without removing it.
 Empty: Checks if the queue is empty.
 Full: Checks if the queue is full.

22
Enqueue() Operation
The following steps should be followed to insert (enqueue) data element into a queue -
Step 1: Check if the queue is full.
Step 2: If the queue is full, Overflow error.
Step 3: If the queue is not full, increment the rear pointer to point to the next
available empty space.
Step 4: Add the data element to the queue location where the rear is pointing.
Step 5: Here, you have successfully added 7, 2, and -9.

Dequeue() Operation

Obtaining data from the queue comprises two subtasks: access the data where the front is
pointing and remove the data after access. You should take the following steps to remove
data from the queue -
 Step 1: Check if the queue is empty.
 Step 2: If the queue is empty, Underflow error.
 Step 3: If the queue is not empty, access the data where the front pointer is
pointing.
 Step 4: Increment front pointer to point to the next available data element.
 Step 5: Here, you have removed 7, 2, and -9 from the queue data structure.

23
Applications of Queue
 Task scheduling in operating systems
 Data transfer in network communication
 Simulation of real-world systems (e.g., waiting lines)
 Priority queues for event processing queues for event processing

Implementation of Queue
A queue can be represented in different ways depending on the implementation. The most
common representations are:

1. Array Representation
Structure: A fixed-size array is used to store elements. Two pointers, front and rear, are used
to keep track of the first and last elements in the queue.
Operations:
Enqueue: Add an element at the position indicated by “rear”, then increment “rear”.
Dequeue: Remove the element at the position indicated by “front”, then increment “front”.

2. Linked List Representation

Structure: A linked list is used where each node represents an element in the queue. The
front pointer points to the first node, and the rear pointer points to the last node.
Operations:
Enqueue: Create a new node and link it to the end of the list, then update rear to point to
this new node.
Dequeue: Remove the node at the front and update front to point to the next node.

Array Implementation of Queue

#include <stdio.h>
#include <stdlib.h>

struct Queue {
int front, rear, capacity;
int* queue;
};

// Function to initialize the queue

struct Queue* createQueue(int capacity) {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->capacity = capacity;
24
q->front = 0;
q->rear = -1;
q->queue = (int*)malloc(q->capacity * sizeof(int));
return q;
}

// Function to insert an element at the rear of the queue

void enqueue(struct Queue* q, int data) {
// Check if the queue is full
if (q->rear == q->capacity - 1) {
printf("Queue is full\n");
return;
}

// Insert element at the rear

q->queue[++q->rear] = data;
}

// Function to delete an element from the front of the queue

void dequeue(struct Queue* q) {
// If the queue is empty
if (q->front > q->rear) {
printf("Queue is empty\n");
return;
}

// Shift all elements from index 1 till rear to the left by one
for (int i = 0; i < q->rear; i++) {
q->queue[i] = q->queue[i + 1];
}

// Decrement rear
q->rear--;
}

// Function to print queue elements

void display(struct Queue* q) {
if (q->front > q->rear) {
printf("Queue is Empty\n");
return;
}

// Traverse front to rear and print elements

25
for (int i = q->front; i <= q->rear; i++) {
printf("%d <-- ", q->queue[i]);
}
printf("\n");
}

// Function to print the front of the queue

void front(struct Queue* q) {
if (q->rear == -1) {
printf("Queue is Empty\n");
return;
}
printf("Front Element is: %d\n", q->queue[q->front]);
}

int main() {
// Create a queue of capacity 4
struct Queue* q = createQueue(4);

// Print queue elements

display(q);

// Insert elements in the queue

enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);

// Print queue elements

display(q);

// Insert element in the queue

enqueue(q, 60);

// Print queue elements

display(q);

// Dequeue elements
dequeue(q);
dequeue(q);

printf("After two node deletions\n");

26
// Print queue elements
display(q);

printf("After one insertion\n");

enqueue(q, 60);

// Print queue elements

display(q);

// Print front of the queue

front(q);

// Free the allocated memory

free(q->queue);
free(q);

return 0;
}

Output
Queue is Empty
20 <-- 30 <-- 40 <-- 50 <--

Queue is full
20 <-- 30 <-- 40 <-- 50 <--

After two node deletions

40 <-- 50 <--

After one insertion

40 <-- 50 <-- 60 <--

Front Element...

9. Priority Queue
A priority queue is a type of queue that arranges elements based on their priority values.
Elements with higher priority values are typically retrieved or removed before elements
with lower priority values. Each element has a priority value associated with it. When we
add an item, it is inserted in a position based on its priority value.

27
Types of Priority Queue
Priority Queue is of two types:
 Ascending order Priority
 Descending order Priority

Ascending order Priority:

In Ascending order priority queue, the element with least value has the highest priority.
For example,

In the above queue, elements are arranged as per their priority in ascending order. So, if we
need to deque an element from the above queue 5 will be first element to be dequed.

Descending order Priority:

In Descending order priority queue, the element with the highest value has the highest
priority.
For example,

In the above queue, elements are arranged as per their priority in descending order. So, if
we need to deque an element from the above queue 25 will be the first element to be
dequeued.

Operation on Priority Queue

The following operations are performed on a priority queue:

 Insertion
 Deletion
 Peek
Insertion:
Insertion operation is used to insert a new element into the queue. Whenever a new element
is inserted,

28
 The new element is moved to an empty slot top to bottom and left to right.
 If the inserted element is not in the correct position. It will be compared with the
parent element.
 And if the element is not in the correct order, then elements are swapped until the
inserted element gets to the correct position.
Algorithm:
if (the queue is empty)
Create a node
else //when node is already present
Insert the new node at the end of the queue (last node from left to right)
heapify the array

Deletion:
Deletion operation is used to remove any element from the queue, For deleting any element,
 Choose the element which needs to be deleted.
 Swap it with the last element.
 Remove the last element
 Heapify the array.

Algorithm:
if (node== leaf node)
delete node
else //when node is not leaf node
Swap node with leaf node
Delete the leaf node
heapify the array

Peek:
Peeking an element means returning either maximum or minimum element of the array.
Peek operation is used to find out maximum or minimum element of the array. It is just
returning the value of highest or lowest element without deleting that node.

Implementation of Priority Queue

Implementation of a priority queue in C using a binary heap.

Heap are the preferred data structure for the implementation of priority queue as compared
to array and linked list because heaps are most efficient and provide better performance
when compared with other data structure.

29
Key Characteristics of Heap Trees:

Binary Tree Structure:

A heap is a complete binary tree, meaning all levels are fully filled except possibly the last
level, which is filled from left to right.

Heap Property:

Max heap: The max heap is a heap in which the value of the parent node is greater than the
value of the child nodes.

Min heap: The min heap is a heap in which the value of the parent node is less than the
value of the child nodes.

Both the heaps are the binary heap, as each has exactly two child nodes.

30
Applications of Priority Queue

Dijkstra’s Algorithm

Dijkstra’s algorithm is used to find the shortest path between nodes in a graph with non-negative edge
weights. It uses a priority queue to greedily select the vertex with the smallest distance from the source at
each step, ensuring efficient path exploration.

Task Scheduling

Priority queues manage tasks based on their priority, ensuring higher priority tasks are executed first. This
is crucial in operating systems, real-time systems, and job schedulers.

Huffman Coding

In Huffman coding, a priority queue helps build the Huffman tree, where characters with lower frequencies
have higher priorities. This enables efficient data compression with optimal encoding.

Event-driven Simulation

Event-driven simulations use priority queues to process events based on timestamps, ensuring correct event
order and accurate simulations in areas like computer graphics and network simulations.

Load Balancing

In load balancing, priority queues distribute workload by assigning priorities to incoming requests,
optimizing resource utilization and ensuring timely processing of high-priority tasks.

Databases and Operating Systems

Priority queues are essential in databases and operating systems for query optimization, transaction
management, and process scheduling, improving resource allocation and system performance.

Network Routing

Priority queues in network routing help determine the next hop for packets by considering factors like link
cost and congestion, optimizing network performance and ensuring timely data delivery.

*************

31