21CSC201J - DATA STRUCTURES AND ALGORITHMS LABORATORY

The objective of this lab is to teach students various data structures and to explain them the
importance of Data Structures in the context of writing algorithms for performing various
operations on these data structures. Students will gain practical knowledge by writing and
executing programs in C and C++ using learning the basic concepts related to the ‘C’ language
along with various data structures such as arrays, linked lists, stacks, queues, trees, graphs, hash
tables and search trees.

OUTCOMES:

Upon the completion of Data Structures practical course, the student will be able to:

1. Design and analyze the time and space efficiency of the data structure.
2. Identify the appropriate data structure for a given problem.
3. Understand the applications of data structures.
4. Choose the appropriate data structure and algorithm design method for a specified
application.
5. Understand which algorithm or data structure to use in different scenarios.
6. Understand and apply fundamental algorithmic problems including Tree traversals,
Graph traversals.
7. Compare different implementations of data structures and to recognize the
advantages and disadvantages of them.
8. Compare between different data structures. Pick an appropriate data structure for a
design situation.

21CSC201J - DATA STRUCTURES AND ALGORITHMS LABORATORY

The objective of this lab is to teach students various data structures and to explain them the
importance of Data Structures in context of writing algorithms for performing various
operations on these data structures. Students will gain practical knowledge by writing and
executing programs in C and C++ using various data structures such as arrays, linked lists,
stacks, queues, trees, graphs, hash tables and search trees.

COURSE LEARNING RATIONALE

The purpose of learning this course is to:

CLR-1: Utilize linked list in developing applications
CLR-2: Utilize stack and queues in processing data for real-time applications
CLR-3: Utilize tree data storage structure for real-time applications
CLR-4: Utilize algorithms to find shortest data search in graphs for real-time application
development
CLR-5: Utilize the different types of data structures and its operations for real-time
programming applications
COURSE LEARNING OUTCOMES

At the end of this course, learners will be able to:

CLO-1: Identify linear and non-linear data structures. Create algorithms for searching and
sorting
CLO-2: Create the different types of linked lists and evaluate its operations
CLO-3: Construct stack and queue data structures and evaluate its operations
CLO-4: Create tree data structures and evaluate its types and operations
CLO-5: Create graph data structure, evaluate its operations, implement algorithms to
identify shortest path Construct the different data structures and evaluate their types and
operations.

DATA STRUCTURES AND ALGORITHMS LAB SYLLABUS

S.No. List of Experiments Course Learning
Outcome (CLO)
1. Implementation of Structures CLO - 1
2. Implementation of Structures using Pointers CLO - 1
3. Implementation of Matrix Multiplication - Dynamic Memory CLO - 1
Allocation
4. Array Implementation of List CLO - 2
5. Implementation of Linked List CLO - 2
6. Implementation of Doubly Linked List CLO - 2
7. Implementation of Stack using Array and Linked List CLO - 3
8. Implementation of Queue using Array and Linked List CLO - 3
9. Applications of Stack, Queue CLO - 3
10. Implementation of Trees using Array CLO - 4
11. Implementation of BST using Linked List CLO - 4
12. Implementation of B - Trees CLO - 4
13. Implementation of Graph using Array CLO - 5
14. Implementation of Shortest path Algorithm CLO - 5
15. Implementation of Minimal Spanning Tree CLO - 5
Total No. of Programs 15
Exp. No: 1 Implementation of Structures

Aim:
To perform the implementation of structures using C language.

Algorithm:
1. Define a structure with multiple structure members.
2. Declare a structure variable to the structure type.
3. Read the input for structure variable by accessing all the structure members of the variable.
5. Print the structure variables by accessing all the structure members of the variable.

Pseudocode
// Create a structure
struct student
// Declare variables inside the structure
int roll_no;
char name[20];
float marks;
// create a structure variable
struct student S1;
// Read the values for structure variable- Accessing Structure members
S1. roll_no = value
S1.name= value2
S1. marks= value3
// Print the values - Accessing Structure members
S1.roll_no
S1.name
S1.marks

Sample input and output:

Provide the roll No
Provide your name
Provide your mark
Roll No: 101
Name: John
Marks: 85.50
Result:
The implementation of structures using pointers was performed using dynamic memory
allocation and inputs, outputs are validated.
Exp No: 2 Implementation of Structures using Pointers

Aim:
To perform the implementation of structures using pointers.

Algorithm:
1. Define a structure with multiple variables.
2. Declare a pointer to the structure type.
3. Allocate memory to the structure pointer using the malloc function.
4. Initialize the variables of the structure using the ‘operator.
5. Print the variables of the structure using the '->' operator.
6. Free the memory allocated to the structure pointer using the 'free' function.

Pseudocode
// Create Structure
struct student

// Declare variables inside the structure

int roll_no;
char name[20];
float marks;

// create a pointer object to the structure

struct student *ptr;

// Dynamic Memory allocation is created based on the size of structure student

ptr = (struct student*)malloc(sizeof(struct student));

// Provide values to the variables using -> pointer

ptr->roll_no = 101

// string copy of
ptr->name as "John"
ptr->marks = 85.5

// Print the values

ptr->roll_no
ptr->name
ptr->marks
// Now remove the memory allotted by pointer variables
free(ptr);

Sample input and output:

Provide the roll No
Provide your name
Provide your mark
Roll No: 101
Name: John
Marks: 85.50

Result:
The implementation of structures using pointers was performed using dynamic memory
allocation and inputs, outputs are validated.
Exp No: 3 Matrix multiplication using dynamic memory allocation

Aim:
To perform the matrix multiplication using dynamic memory allocation.

Algorithm:
1. Declaring pointer for matrix multiplication.
2. Declaring integer variables for row and columns of two matrices.
3. Declaring indexes and requests the user to input number of columns of the matrices.
4. Allocating memory for three matrix rows and columns.
5. Request the input for Matrix 1 and 2.
6. Calculation for the resultant matrix.
7. Printing the contents of third matrix.

Pseudocode for matrix multiplication using dynamic memory allocation

// Define the dimensions of the matrices
int rows1, cols1, rows2, cols2; // Set these to your desired values

// Allocate memory for the matrices

int** matrix1 = new int*[rows1];
for (int i = 0; i < rows1; i++) {
matrix1[i] = new int[cols1];
}

int** matrix2 = new int*[rows2];

for (int i = 0; i < rows2; i++) {
matrix2[i] = new int[cols2];
}

// Initialize the matrices with values (you can modify this as needed)
// For example, fill matrix1 and matrix2 with your desired values

// Create a result matrix

int** result = new int*[rows1];
for (int i = 0; i < rows1; i++) {
result[i] = new int[cols2];
}

// Perform matrix multiplication

for (int i = 0; i < rows1; i++) {
 for (int j = 0; j < cols2; j++) {
result[i][j] = 0;
for (int k = 0; k < cols1; k++) {
result[i][j] += matrix1[i][k] * matrix2[k][j];
}
}
}

// Now, 'result' contains the result of the matrix multiplication

Sample input and output:

Enter No. of rows for First Matrix: 3

Enter No. of Columns for First Matrix: 3

Enter first matrix- 123

456
789
Enter No. of Rows for Second Matrix: 3
Enter No. of Columns for Second Matrix: 3

Enter second matrix- 1 2 3

456
789

The matrix multiplication is- 30 36 42

66 81 96
102 126 150

Result: The matrix multiplication was performed using dynamic memory allocation and inputs,
outputs are validated.
Exp No: 4 Array Implementation of List

Aim:
To implement the LIST ADT using arrays.

Algorithm

Step 1: start the program

Step 2: Declare the array of size n
Step 3: Declare the function to be called
Step 4: Use switch case select the operation to be performed
Step 5: If choice is 1, call insertion function
Step 6: If choice is 2, call deletion function
Step 7: If choice is 3, call find function
Step 8: If choice is 4, call find previous function
Step 9: If choice is 5, call print list function.
Step10: if choice > 5 then exit.

INSERTION:

Step 1: Read the value to be inserted into the list

Step 2: Read the position/data to insert the new data.
Step 3: Shift the data in the position towards right and insert the new value in position.
Step 4: Return

DELETION:

Step1: Read the element to be deleted

Step 2: Get the address of previous value of the element
Step 3: Shift the next data of the deleting value towards left
Step 4: Return

FIND:

Step 1: Get the element to be found

Step 2: Traverse the list starting from first node
Step 3: Return address of the node in which the element is present
FIND PREVIOUS:

Step 1: Get the element to be found

Step 2: Traverse the list starting from first node
Step 3: Return the previous address of the node in which the element is present.
PRINTLIST:

Step 1: SET I=0

Step 2: Repeat Step 3 and 4 till the end of the list
Step 3: Print the data in Ith index.
Step 4: Increment I
Step 5: Exit

Pseudocode:
Operations on arrays:
1. Traversing an array
2. Inserting an element in an array
3. Deleting an element from an array

1. Traversing an array
Traversing an array means accessing each and every element of the array for a specific
purpose.

Step 1: [INITIALIZATION] SET I = lower_bound

Step 2: Repeat Steps 3 to 4 while I <= upper_bound
Step 3: Apply Process to A[I]
Step 4: SET I = I + 1 [END OF LOOP]
Step 5: EXIT

2. Inserting an element in an array

Inserting an element means adding an element at the given index

i) Inserting an element at the end of an array

Step 1: Set upper_bound = upper_bound + 1

Step 2: Set A[upper_bound] = VAL
Step 3: EXIT

ii) Inserting an Element in the Middle of an Array

Step 1: [INITIALIZATION] SET I = N

Step 2: Repeat Steps 3 and 4 while I >= POS
Step 3: SET A[I + 1] = A[I]
Step 4: SET I = I – 1 [END OF LOOP]
Step 5: SET N = N + 1
Step 6: SET A[POS] = VAL Step 7: EXIT

3. Deleting an element from an array

Deleting an element from an array means removing a data element from an already
existing array.
i) Deleting the last element of an array
Step 1: SET upper_bound = upper_bound - 1
Step 2: EXIT
ii) Deleting an element from the middle of an array
Step 1: [INITIALIZATION] SET I = POS
Step 2: Repeat Steps 3 and 4 while I <= N – 1
Step 3: SET A[I] = A[I + 1]
Step 4: SET I = I + 1 [END OF LOOP]
Step 5: SET N = N – 1 Step 6: EXIT

Sample Input and Output

Array Implementation of List

1.Create
2.Insert
3.Delete
4.Display
5.Search
6.Exit
Enter your choice: 1
Enter the number of elements to be added in the list: 5
Enter the array elements: 1 2 3 4 5
**********Elements in the array**********
12345
Array Implementation of List
1.Create
2.Insert
3.Delete
4.Display
5.Search
6.Exit
Enter your choice: 2
Enter the data to be inserted: 3
Enter the position at which element to be inserted: 1
**********Elements in the array**********
312345
Array Implementation of List
1.Create
2.Insert
3.Delete
4.Display
5.Search
6.Exit
Enter your choice: 3
Enter the position of the data to be deleted: 4
The data deleted is: 3
**********Elements in the array**********
31245
Array Implementation of List
1.Create
2.Insert
3.Delete
4.Display
5.Search
6.Exit
Enter your choice: 5
Enter the element to be searched: 1
Element present in the list
Array Implementation of List
1.Create
2.Insert
3.Delete
4.Display
5.Search
6.Exit
Enter your choice:6

Result:

Thus, the program for implementing List ADT using array was written and executed
successfully.
Exp No: 5 Implementation of Linked List

Aim

To implement Singly Linked List ADT.

Algorithm

Step 1: start the program

Step 2: Declare the structure for node which contains data and next pointer fields.
Step 3: Declare the function to be called
Step 4: Use switch case select the operation to be performed
Step 5: If choice is 1, call insertion function
Step 6: If choice is 2, call deletion function
Step 7: If choice is 3, call find function
Step 8: If choice is 4, call find previous function
Step 9: If choice is 5, call print list function.
Step10: if choice > 5 then exit.

INSERTION:

Step 1: Create a new node using malloc function

Step 2: Assign the value to the node
Step 3: Get the position/data to insert the new data.
Step 4: New node is added to the list
Step 5: Return

DELETION:

Step1: Get the element to be deleted

Step 2: Get the address of previous node of the element
Step 3: Change the link field of previous node
Step 4: Free the space of the deleted node
Step 5: Return

FIND:

Step 1: Get the element to be found

Step 2: Traverse the list starting from first node
Step 3: Return address of the node in which the element is present
FIND PREVIOUS:

Step 1: Get the element to be found

Step 2: Traverse the list starting from first node
Step 3: Return the previous address of the node in which the element is present.

PRINTLIST:

Step 1: Store the linked list header address to a temporary variable.

Step 2: If head pointer is null return empty list and go to step 6.
Step 3: Else Repeat Step 4 and 5 till the end of the list
Step 4: Print the current node data.
Step 5: Move the pointer to the next node
Step 6: Exit

PSEUDOCODE:

Node Structure

struct node
{
int DATA;
struct node *NEXT;
};

1. Inserting a node from a LinkedList

i) Inserting a Node at the Beginning of a Linked List

Step 1: IF AVAIL = NULL

Write OVERFLOW Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE->DATA = VAL
Step 5: SET NEW_NODE -> NEXT = START Step 6: SET START = NEW_NODE
Step 7: EXIT

ii) Inserting a Node at the end of a Linked List

Step 1: IF AVAIL = NULL

 Write OVERFLOW Go to Step 1
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE->DATA = VAL
Step 5: SET NEW_NODE->NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR- >NEXT! =NULL
Step 8: SET PTR = PTR->NEXT
[END OF LOOP]
Step 9: SET PTR->NEXT = NEW_NODE Step 10: EXIT

iii) Inserting the node before a given node in a linked list

Step 1: IF AVAIL = NULL

Write OVERFLOW Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR->DATA! = NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR->NEXT
[END OF LOOP]
Step 10: PREPTR->NEXT = NEW_NODE
Step 11: SET NEW_NODE->NEXT = PTR
Step 12: EXIT

iv) Inserting the Node After a Given Node in a Linked List

Step 1: IF AVAIL = NULL

Write OVERFLOW Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET NEW_NODE->DATA = VAL Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR->DATA! = NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR->NEXT [END OF LOOP]
Step 10: PREPTR->NEXT = NEW_NODE
Step 11: SET NEW_NODE->NEXT = PTR
Step 12: EXIT

2. Deleting a node from a LinkedList

i) Deleting the First Node from a Linked List

Step 1: IF START = NULL

Write UNDERFLOW
Go to Step 5 [END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START -> NEXT
Step 4: FREE PTR
Step 5: EXIT

ii) Deleting the Last Node from a Linked List

Step 1: IF START = NULL

Write UNDERFLOW
Go to Step 8 [END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR->NEXT! = NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR->NEXT [END OF LOOP]
Step 6: SET PREPTR -> NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT

iii) Deleting the Node After a Given Node in a Linked List

Step 1: IF START = NULL

Write UNDERFLOW
Go to Step 1 [END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR->DATA! = NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR->NEXT [END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR->NEXT = PTR->NEXT
Step 9: FREE TEMP
Step 10: EXIT

3. FIND

STEP 1: SET PTR = HEAD

STEP 2: Set POS = 0
STEP 3: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 8
END OF IF
STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR! = NULL
STEP 5: if PTR → DATA = item
write POS+1
End of IF
STEP 6: POS = POS + 1
STEP 7: PTR = PTR → NEXT
[END OF LOOP]
STEP 8: Return POS
STEP 9: EXIT

4. FINDPREVIOUS

STEP 1: SET PTR = HEAD

STEP 2: Set POS = 0, PREV=0;
STEP 3: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 8
END OF IF
STEP 4: REPEAT STEP 5 TO 7 UNTIL PTR! = NULL
STEP 5: if PTR → DATA = item
return POS
End of IF
STEP 6: POS = POS + 1
STEP 7: PTR = PTR → NEXT
[END OF LOOP]
STEP 8: Return POS
STEP 9: EXIT
5. PRINTLIST

STEP 1: SET PTR = HEAD

STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 8
END OF IF
STEP 3: REPEAT STEP 4 AND 5 UNTIL PTR! = NULL
STEP 4: PRINT PTR→ DATA
STEP 5: PTR = PTR → NEXT
[END OF LOOP]
STEP 6: EXIT

Sample Input and Output

Implementation of Linked List

1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit

Enter your choice: 2

Enter the data to be inserted: 3
Enter the position at which element to be inserted: 1

**********Elements in the array**********

3
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit

Enter your choice: 1

Enter the data to be inserted: 4
Enter the position at which element to be inserted: 2
**********Elements in the array**********
34
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit

Enter your choice: 1

Enter the data to be inserted: 5
Enter the position at which element to be inserted: 2

**********Elements in the array**********

354
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit
Enter your choice: 2
Enter the position of the data to be deleted: 2
The data deleted is: 5
**********Elements in the array**********
34
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit

Enter your choice: 3

Enter the data to be searched: 4
Position of 4: 2
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit
Enter your choice: 4
Enter the data whose previous value to be searched: 4
Previous of 4: 3

Implementation of Linked List

1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit
Enter your choice: 5
**********Elements in the array**********
34
Implementation of Linked List
1.Insert
2.Delete
3.Find
4.FindPrevious
5.Printlist
6.Exit
Enter your choice: 6

Result:

Thus, the program for implementing Singly Linked List ADT was written and executed
successfully.
Exp no- 06

Implementation of doubly linked list

Aim

Write a C or C++ program for implementation of doubly linked list

Algorithm

1.Define a struct to represent a node in the doubly linked list.

The node struct defines a node in the doubly linked list. Each node has
three fields: data, prev, and next. The data field stores the data of the
node, the prev field points to the previous node in the list, and the next
field points to the next node in the list.

2. Declare a global variable to point to the head of the doubly linked list.

3. Implement a function to insert a new node at the beginning of the doubly

linked list.

4. Implement a function to print the doubly linked list to the console.

5. Use the `insert_at_head()` and `print_list()` functions to create and

print a doubly linked list.

Pseudo Code

1.Create a node struct to store the data, the previous pointer, and the next pointer

struct node {

int data;

struct node *prev;

struct node *next;

};

2. Create a head pointer to store the head of the doubly linked list
struct node *head = NULL;

3.Function to insert a new node at the beginning of the doubly linked list

void insert_at_head(int data) {

Create a new node

struct node *new_node = malloc(sizeof(struct node));

// Initialize the new node's data field

new_node->data = data;

// Set the new node's prev field to NULL

new_node->prev = NULL;

4.Set the new node's next field to the current head of the doubly linked list

new_node->next = head;

5.If the doubly linked list is not empty, set the current head's prev field to point to the
new node

if (head != NULL) {

head->prev = new_node;

Update the head pointer to point to the new node

head = new_node;
}

Function to print the doubly linked list

void print_list() {

Create a temporary pointer to iterate over the doubly linked list

struct node *temp = head;

While the temporary pointer is not NULL, print the data of the current node and move
the temporary pointer to the next node

while (temp != NULL) {

printf("%d ", temp->data);

temp = temp->next;

Print a newline character at the end of the list

printf("\n");

Sample input and output

Enter the elements of the doubly linked list: 10 20 30

30 20 10

Result:

Thus, the program for implementing Doubly Linked List ADT was written and executed
successfully.
Exp no -7

Implementation of Stack using Array and Linked List

Aim

Write a C or C++ program for implementing stack using array and linked list

Algorthim

1. We begin with a class named Stack.

2. Create a pointer top which we will use to carry out all operations
3. Initialize an array in which we'll be storing our data
4. Initialize a constructor as top = -1 indicating that stack is empty
5. Push() - function, we use this function to insert data into the stack, so first we
check if top==full i.e stack is full and data cannot be inserted. Else increment the
top pointer and insert the data.
6. Pop() - function, this function is used to remove data from the stack, first we check
if top==-1 i.e if stack is empty nothing is there to delete. Else delete the element in
top pointer and decrement it.
7. isEmpty() - function check whether stack is empty i.e to p== - 1 or top < 0
8. display() - function to display the contents of the stack, we iterate through the
array from the beginning till we reach the top pointer.

Pseudo code:

Stack using array:

// Declare a fixed-size array to store the elements of the stack

int stack[MAX_SIZE];

// Declare a top pointer to track the top of the stack

int top = -1;

// Function to push an element onto the stack

void push(int data) {

// Check if the stack is full

if (top == MAX_SIZE - 1) {

printf("Stack overflow.\n");

return;

// Increment the top pointer

top++;

// Add the element to the stack at the top pointer

stack[top] = data;

// Function to pop an element from the stack

int pop() {

// Check if the stack is empty

if (top == -1) {

printf("Stack underflow.\n");

return -1;

}
 // Decrement the top pointer

top--;

// Return the element at the top pointer

return stack[top];

// Function to check if the stack is empty

bool is_empty() {

return top == -1;

// Function to check if the stack is full

bool is_full() {

return top == MAX_SIZE - 1;

Stack using linked list:

// Create a node struct to store the data and the next pointer

struct node {

int data;

struct node *next;

};

// Create a head pointer to store the top of the stack

struct node *head = NULL;

// Function to push an element onto the stack

void push(int data) {

// Create a new node

struct node *new_node = malloc(sizeof(struct node));

// Initialize the new node's data field

new_node->data = data;

// Set the new node's next field to point to the current head of the stack

new_node->next = head;

// Update the head pointer to point to the new node

head = new_node;

// Function to pop an element from the stack

int pop() {

// Check if the stack is empty

 if (head == NULL) {

printf("Stack underflow.\n");

return -1;

// Get the data at the head of the stack

int data = head->data;

// Update the head pointer to point to the next node in the stack

head = head->next;

// Free the popped node

free(head);

// Return the popped data

return data;

// Function to check if the stack is empty

bool is_empty() {

return head == NULL;

}
Sample input and output

Choose one from the below options.

1.Push

2.Pop

3.Show

4.Exit

After pushing 20 30

Printing stack elements 30 20

Result:

Thus, the program for implementing Stack ADT using arrays and Linked list was written and
executed successfully.
Exp no – 8

Implementation of Queue using Array and Linked List

Aim

Write a C or C++ program for the implementation of queue using array and linked list

Algorithm

1. Declare an array to store the elements of the queue.

2. Declare two variables, front and rear, to track the front and rear of the queue.

3. Implement a function to enqueue an element to the queue.

4. Implement a function to dequeue an element from the queue.

5. Implement a function to check if the queue is empty.

Pseudo code:

Queue using array

// Declare a fixed-size array to store the elements of the queue

int queue[MAX_SIZE];

// Declare two pointers, front and rear, to track the front and rear of the queue

int front = 0;

int rear = 0;

// Function to enqueue an element onto the queue

void enqueue(int data) {

 // Check if the queue is full

if (rear == MAX_SIZE) {

printf("Queue overflow.\n");

return;

// Add the element to the queue at the rear pointer

queue[rear] = data;

// Increment the rear pointer

rear++;

// Function to dequeue an element from the queue

int dequeue() {

// Check if the queue is empty

if (front == rear) {

printf("Queue underflow.\n");

return -1;

// Get the data at the front of the queue

int data = queue[front];

 // Increment the front pointer

front++;

// Return the dequeued data

return data;

// Function to check if the queue is empty

bool is_empty() {

return front == rear;

// Function to check if the queue is full

bool is_full() {

return rear == MAX_SIZE;

}
 Queue using linked list:

Pseudo code

// Create a node struct to store the data and the next pointer

struct node {

int data;

struct node *next;

};

// Declare a head pointer to store the front of the queue

struct node *head = NULL;

// Declare a rear pointer to store the rear of the queue

struct node *rear = NULL;

// Function to enqueue an element onto the queue

void enqueue(int data) {

// Create a new node

struct node *new_node = malloc(sizeof(struct node));

// Initialize the new node's data field

new_node->data = data;
 // Set the new node's next field to NULL

new_node->next = NULL;

// If the queue is empty, set the head and rear pointers to point to the new node

if (head == NULL) {

head = new_node;

rear = new_node;

return;

// Add the new node to the rear of the queue

rear->next = new_node;

// Update the rear pointer to point to the new node

rear = new_node;

// Function to dequeue an element from the queue

int dequeue() {

// Check if the queue is empty

if (head == NULL) {

printf("Queue underflow.\n");
 return -1;

// Get the data at the front of the queue

int data = head->data;

// Update the head pointer to point to the next node in the queue

head = head->next;

// If the queue is empty after dequeueing, set the rear pointer to NULL

if (head == NULL) {

rear = NULL;

// Free the dequeued node

free(head);

// Return the dequeued data

return data;

// Function to check if the queue is empty

bool is_empty() {
 return head == NULL;

Sample input and output

***********Main Menu**********

==============================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice 1

Enter value?

123

***********Main Menu**********

==============================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice 1

Enter value?

90

***********Main Menu**********

==============================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice 3

printing values .....

123

90

***********Main Menu**********

==============================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice 2

***********Main Menu**********

==============================
1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Enter your choice 3

printing values .....

90

***********Main Menu**********

==============================

1.insert an element

2.Delete an element

3.Display the queue

4.Exit

Result:

Thus, the program for implementing Queue ADT using arrays and Linked list was written and
executed successfully.
Exp no – 9

Applications of stack and queue

Aim

To write a C or C++ program for applications of stack and queue

Algorithm

1. First of all, it will Create an empty stack.

2. After that, it Scan the expression from left to right.
3. If an operand is encountered, it push it onto the stack.
4. If an operator is encountered, pop the top two operands from the stack, perform
the operation, and push the result back onto the stack.
5. After that, it Continue scanning the expression until all tokens have been
processed.
6. When the expression has been fully scanned, the result will be the top element of
the stack.

Pseudo Code :

// Create a stack to store the operands of the expression

Stack stack;

// Iterate over the postfix expression from left to right

for each character in the expression:

// If the character is an operand, push it onto the stack

if the character is an operand:

stack.push(character);
 // If the character is an operator, pop two operands from the stack and evaluate the
operator

else if the character is an operator:

operand2 = stack.pop();

operand1 = stack.pop();

result = evaluate(operand1, operand2, operator);

stack.push(result);

// When the end of the expression is reached, the stack will contain the result of the
expression

result = stack.pop();

// Return the result

return result;

// Function to evaluate an operator

function evaluate(operand1, operand2, operator):

// Evaluate the operator and return the result

switch (operator):

case '+':

return operand1 + operand2;

case '-':

return operand1 - operand2;

case '*':
 return operand1 * operand2;

case '/':

return operand1 / operand2;

default:

// Throw an error if the operator is not recognized

raise an error;

Sample Input and Output

Input : 5 6 7 + * 8 -

The output of the above program will be:

Result: 57

Result:

Thus, the program for implementing Stack ADT using Linked list to demonstrate the
application of the same, was written and executed successfully.
9b.) Applications of Queue

Aim :

To write a C or C ++ program for the implementation of Job scheduling for First come
First serve (FCFS)

Algorithm

1- Input the processes along with their burst time (bt).

2- Find waiting time (wt) for all processes.

3- As first process that comes need not to wait so

waiting time for process 1 will be 0 i.e. wt[0] = 0.

4- Find waiting time for all other processes i.e. for

process i ->

wt[i] = bt[i-1] + wt[i-1].

5- Find turnaround time = waiting_time + burst_time

for all processes.

6- Find average waiting time =

total_waiting_time / no_of_processes.

7- Similarly, find average turnaround time =

total_turn_around_time / no_of_processes.

Pseudo Code:

Declare a queue to store the jobs

Queue queue;
Declare variables to store the average waiting time and turnaround time

float average_waiting_time = 0.0;

float average_turnaround_time = 0.0;

Iterate over the jobs in the order that they arrive

for each job in the jobs:

Add the job to the queue

queue.enqueue(job);

Initialize the current time

current_time = 0.0;

While the queue is not empty

while not queue.is_empty():

Get the next job from the queue

job = queue.dequeue();

Calculate the waiting time for the job

waiting_time = current_time - job.arrival_time;

Update the average waiting time

average_waiting_time += waiting_time;
 Execute the job

job.execute();

Update the current time

current_time += job.execution_time;

Calculate the turnaround time for the job

turnaround_time = current_time - job.arrival_time;

Update the average turnaround time

average_turnaround_time += turnaround_time;

Calculate the average waiting time and turnaround time

average_waiting_time /= len(jobs);

average_turnaround_time /= len(jobs);

Print the average waiting time and turnaround time

print("Average waiting time:", average_waiting_time);

print("Average turnaround time:", average_turnaround_time);

Sample Input and Output

PID AT BT CT TAT WT
0 0 10 10 10 0
1 10 5 15 5 0
2 15 8 23 8 0
Avg_turnaround:7.666666666666667
Avg_Waitingtime:0.0

Result:

Thus, the program for implementing Queue ADT using Linked list to demonstrate the
application of the same, was written and executed successfully.
 10. IMPLEMENTATION OF TREE USING ARRAY

Aim:

To implement tree using array.

Assumption

In order to represent a tree using an array, the numbering of nodes can start either from 0–(n-1)
or 1– n

Pseudocode:

Note: father, left_son and right_son are the values of indices of the array.
Case 1: (0—n-1)
if (say)father=p;
then left_son=(2*p)+1;
and right_son=(2*p)+2;
Case 2: 1—n
if (say)father=p;
then left_son=(2*p);
and right_son=(2*p)+1;
Sample I/O:

Input:

A(0)
/ \
B(1) C(2)
/ \ \
D(3) E(4) F(6)
OR,
A(1)
/ \
B(2) C(3)
/ \ \
D(4) E(5) F(7)

root('A');
set_left('B',0);
set_right('C', 0);
set_left('D', 1);
set_right('E', 1);
set_right('F', 2);
print_tree();

Output:

ABCDE-F---

Result:

Thus, the program for implementing Tree ADT using array was written and executed
successfully.
 11. IMPLEMENTATION OF BINARY SEARCH TREE USING LINKED LIST

Aim:

To implement a Binary Search Tree

Operations in BST:

1. Inserting a node in BST

2. Searching
3. Traversing
4. Deleting a node in BST

Pseudocode:

1. Inserting a node in BST

New node is inserted into the left or right subtree BST based on value of the data.

Insert (TREE, VAL)

Step 1: IF TREE = NULL

Allocate memory for TREE

SET TREE -> DATA = VAL

SET TREE-> LEFT = TREE-> RIGHT = NULL

ELSE

IF VAL < TREE-> DATA

Insert(TREE-> LEFT, VAL)

ELSE

Insert(TREE-> RIGHT, VAL)

[END OF IF]

[END OF IF]

Step 2: END

2. Searching
Following is a recursive code to search an element from BST.
 searchElement(TREE, VAL)
Step 1: IF TREE🡪DATA = VAL OR TREE = NULL
Return TREE
ELSE
IF VAL < TREE DATA
Return searchElement(TREE🡪 LEFT, VAL)
ELSE
Return searchElement(TREE🡪RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END

3. Tree Traversal
Traversal – visiting all node only once. Based on the order of visiting, we have the following
tree traversal techniques:

– In – order traversal
– Pre – order traversal
– Post – order traversal
Algorithm: Inorder traversal

Inorder(Tree)

1. Repeat step 2 – 4 while Tree != Null

2. Inorder(Tree->left)
3. Write(Tree->Data)
4. Inorder(Tree->right)
5. End
Algorithm: Preorder traversal

Preorder(Tree)

1. Repeat step 2 – 4 while Tree != Null

2. Write(Tree->Data)
3. Preorder(Tree->left)
4. Preorder(Tree->right)
5. End
Algorithm: postorder traversal

Postorder(Tree)

1. Repeat step 2 – 4 while Tree != Null

2. Postorder(Tree->left)
 3. Postorder(Tree->right)
4. Write(Tree->Data)
End

4. Delete a node from BST

Node deletion falls under any one of the following cases:
Case 1: Deleting a Leaf node (A node with no children)
Case 2: Deleting a node with one child
Case 3: Deleting a node with two children

Delete (TREE, VAL)

Step 1:
IF TREE = NULL
Write "VAL not found in the tree"
ELSE IF VAL < TREE🡪 DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE🡪 DATA
Delete(TREE🡪 RIGHT, VAL)
ELSE IF TREE🡪LEFT AND TREE🡪RIGHT
SET TEMP = findLargestNode(TREE🡪 LEFT) ( INORDER PREDECESSOR)
(OR)
SET TEMP = findSmallestNode(TREE🡪 RIGHT) ( INORDER SUCESSOR)
SET TREE🡪 DATA = TEMP🡪 DATA
Delete(TREE🡪 LEFT, TEMP 🡪DATA) (OR) Delete(TREE🡪 RIGHT, TEMP🡪 DATA)
ELSE
SET TEMP = TREE
IF TREE🡪 LEFT = NULL AND TREE🡪 RIGHT = NULL
SET TREE = NULL

ELSE IF TREE🡪 LEFT != NULL

SET TREE = TREE 🡪LEFT
ELSE
SET TREE = TREE 🡪RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: END

Sample I/O:
Input

root = new_node(20);
 insert(root, 5);
insert(root, 1);
insert(root, 15);
insert(root, 9);
insert(root, 7);
insert(root, 12);
insert(root, 30);
insert(root, 25);
insert(root, 40);
insert(root, 45);
insert(root, 42);
root = delete(root, 1);
root = delete(root, 40);
root = delete(root, 45);
root = delete(root, 9);
Output

1 5 7 9 12 15 20 25 30 40 42 45

5 7 12 15 20 25 30 42

Result:

Thus, the program for implementing Binary Search Tree ADT was written and executed
successfully.
 12. IMPLEMENTATION OF B-TREES

Aim:

To implement a B Tree

Operations:

Search
Create
Insert

Pseudocode:

B-TREE-SEARCH(x, k)
i 1
while i n[x] and k keyi[x]
do i i + 1
if i n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else DISK-READ(ci[x])
return B-TREE-SEARCH(ci[x], k)

B-TREE-CREATE(T)
x ALLOCATE-NODE()
leaf[x] TRUE
n[x] 0
DISK-WRITE(x)
root[T] x

B-TREE-SPLIT-CHILD(x,i,y)
z ALLOCATE-NODE()
leaf[z] leaf[y]
n[z] t - 1
for j 1 to t - 1
do keyj[z] keyj+t[y]
if not leaf [y]
then for j 1 to t
do cj[z] cj+t[y]
n[y] t - 1
 for j n[x] + 1 downto i + 1
do cj+1[x] cj[x]
ci+1[x] z
for j n[x] downto i
do keyj+1[x] keyj[x]
keyi[x] keyt[y]
n[x] n[x] + 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)

B-TREE-INSERT(T,k)
r root[T]
if n[r] = 2t - 1
then s ALLOCATE-NODE()
root[T] s
leaf[s] FALSE
n[s] 0
c1[s] r
B-TREE-SPLIT-CHILD(s,1,r)
B-TREE-INSERT-NONFULL(s,k)
else B-TREE-INSERT-NONFULL(r,k)
Sample I/O:

Input:

insertion (8);
insertion (9);
insertion (10);
insertion (11);
insertion (15);
insertion (16);
insertion (17);
insertion (18);
insertion (20);
insertion (23);
traversal (root)
Output:
8 9 10 11 15 16 17 18 20 23
Result:

Thus, the program for implementing B-Tree was written and executed successfully.
 13. IMPLEMENTATION OF GRAPH USING ARRAY
Aim:
To implement graph using arrays
Assume: The total number of edges is known, Very fast and memory-efficient
Pseudocode:
Have two arrays E of size m and LE of size n –
E contains the edges
LE contains the starting pointers of the edge lists
Initialize LE[i] = -1 for all i – LE[i] = 0 is also fine if the arrays are 1-indexed
Inserting a new edge from u to v with ID k
E[k].to = v
E[k].nextID = LE[u]
LE[u] = k
Iterating over all edges starting at u:
for(ID = LE[u]; ID != -1; ID = E[ID].nextID)
// E[ID] is an edge starting from u
Sample I/O:
Input
int adjMatrix[V][V];
init(adjMatrix);
insertEdge(adjMatrix, 0, 1);
insertEdge(adjMatrix, 0, 2);
insertEdge(adjMatrix, 1, 2);
insertEdge(adjMatrix, 2, 0);
insertEdge(adjMatrix, 2, 3);
printAdjMatrix(adjMatrix);
Output

Result:

Thus, the program for implementing graph using array was written and executed successfully.
 14. IMPLEMENTATION OF SHORTEST PATH ALGORITHM

Aim:

Implementation of Shortest Path Algorithm – Dijikstra’s Algorithm

Pseudocode:

function Dijkstra(Graph, source):

for each vertex v in Graph.Vertices:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u still in Q:
alt ← dist[u] + Graph.Edges(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]

Sample I/O:
Input
{ { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

Output
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

Result:

Thus, the program for implementing Shortest Path was written and executed successfully.
 IMPLEMENTATION OF MINIMUM SPANNING TREE
Aim:
Implementation of Minimum Spanning Tree – Kruskal’s & Prim’s Algorithm
Pseudocode:
Kruskal’s Algorithm
Kruskal's algorithm to find minimum cost spanning tree uses greedy approach. This algorithm
treats the graph as a forest and every node it as an individual tree. A tree connects to another
only and only if it has least cost among all available options and does not violate MST
properties.
Step 1 - Remove all loops & Parallel Edges
Step 2 - Arrange all edges in their increasing order of weight
Step 3 - Add the edge which has least weightage
Pseudocode for Kruskal’s Algorithm

Algorithm
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle
is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Prims Algorithm
Prim's algorithm to find minimum cost spanning tree (as Kruskal's algorithm) uses greedy
approach. Prim's algorithm shares similarity with shortest path first algorithms. Prim's
algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree and keeps on
adding new nodes to the spanning tree from the given graph.
Step 1 - Remove all loops & Parallel Edges
Step 2 - Choose any arbitrary node as root node
Step 3 - Check outgoing edges and select the one with less cost
Pseudocode for Prim’s Algorithm

Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE.
Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
a) Pick a vertex u which is not there in mstSet and has minimum key value.
b) Include u to mstSet.
c) Update key value of all adjacent vertices of u. To update the key values, iterate through
all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the
previous key value of v, update the key value as weight of u-v
Sample I/O:

Result:

Thus, the program for implementing Minimum Spanning Tree was written and executed
successfully.