(23A05201P) DATA STRUCTURES LAB

(Common to CSE, IT & allied branches)

List of Experiments:
Exercise 1: Array Manipulation
i) Write a program to reverse an array.
ii) C Programs to implement the Searching Techniques – Linear & Binary Search
iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort

Exercise 2: Linked List Implementation

i) Implement a singly linked list and perform insertion and deletion operations.
ii) Develop a program to reverse a linked list iteratively and recursively.
iii) Solve problems involving linked list traversal and manipulation.

Exercise 3: Linked List Applications

i) Create a program to detect and remove duplicates from a linked list.
ii) Implement a linked list to represent polynomials and perform addition.
iii) Implement a double-ended queue (deque) with essential operations.

Exercise 4: Double Linked List Implementation

i) Implement a doubly linked list and perform various operations to understand its
properties and applications.
ii) Implement a circular linked list and perform insertion, deletion, and traversal.

Exercise 5: Stack Operations

i) Implement a stack using arrays and linked lists.
ii) Write a program to evaluate a postfix expression using a stack.
iii) Implement a program to check for balanced parentheses using a stack.

Exercise 6: Queue Operations

i) Implement a queue using arrays and linked lists.
ii) Develop a program to simulate a simple printer queue system.
iii) Solve problems involving circular queues.

Exercise 7: Stack and Queue Applications

i) Use a stack to evaluate an infix expression and convert it to postfix.
ii) Create a program to determine whether a given string is a palindrome or not.
iii) Implement a stack or queue to perform comparison and check for symmetry.

Exercise8: Binary Search Tree

i) Implementing a BST using Linked List.
ii) Traversing of BST.

Exercise 9: Hashing
i) Implement a hash table with collision resolution techniques.
ii) Write a program to implement a simple cache using hashing.

P BHANU PRAKASH 9551234604 [email protected] 1

Exercise 1: Array Manipulation
i) Write a program to reverse an array.
ii) C Programs to implement the Searching Techniques – Linear & Binary Search
iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort
1. Write a program to reverse an array.
#include <stdio.h>
int main()
{
int n,i;
// Inputting the size of the array
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
// Inputting the array
printf("Enter an array: ");
for ( i = 0; i< n; i++)
{
scanf("%d", &arr[i]);
}
// Printing the reverse of the array
printf("Reversed array: ");
for (i = n-1; i>=0; i--)
{
printf("%d ", arr[i]);
}
return 0;
}
Output:
Enter the size of the array: 6
Enter an array: 2 3 4 6 71 5
Reversed array: 5 71 6 4 3 2

2. C Programs to implement the Searching Techniques – Linear & Binary Search

Linear search
#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int size, int key)
{
int i;
for (i = 0; i < size; i++)
{
if (arr[i] == key)
{
return i; // Return the index where the key is found
}

P BHANU PRAKASH 9551234604 [email protected] 2

 }
return -1; // Return -1 if the key is not found
}
int main()
{
int size, i,key;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array: ");
for (i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the key to search: ");
scanf("%d", &key);
int result = linearSearch(arr, size, key);
if (result != -1)
{
printf("key found at index: %d\n", result);
}
else
{
printf("key not found in the array.\n");
}
return 0;
}
Output:
Enter the size of the array: 5
Enter the elements of the array: 3 4 5 7 6
Enter the key to search: 4
key found at index: 1

Binary Search
#include <stdio.h>
// Function to perform binary search (array must be sorted)
int binarySearch(int arr[], int size, int key)
{
int low = 0;
int high = size - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
return mid; // Return the index where the key is found
}

P BHANU PRAKASH 9551234604 [email protected] 3

else if (arr[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1; // Return -1 if the key is not found
}
int main()
{
int size, i,key;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array in sorted order: ");
for (i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the key to search: ");
scanf("%d", &key);
int result = binarySearch(arr, size, key);
if (result != -1)
{
printf("key found at index: %d\n", result);
}
else
{
printf("key not found in the array.\n");
}
return 0;
}
OUTPUT
Enter the size of the array: 6
Enter the elements of the array in sorted order: 3 4 5 6 8 9
Enter the key to search: 8
key found at index: 4

3. C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort

BUBBLE SORT:
#include <stdio.h>
void bubbleSort(int arr[], int size)
{
int i,j;
for (i = 0; i < size - 1; i++)
{
for (j = 0; j < size - i - 1; j++)

P BHANU PRAKASH 9551234604 [email protected] 4

 {
if (arr[j] > arr[j + 1])
{
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main()
{
int size, i;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array: ");
for (i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Original array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
bubbleSort(arr, size);
printf("Sorted array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
OUTPUT
Enter the size of the array: 10
Enter the elements of the array: 2 4 3 7 1 9 44 22 18 38
Original array: 2 4 3 7 1 9 44 22 18 38
Sorted array: 1 2 3 4 7 9 18 22 38 44

SELECTION SORT
#include <stdio.h>
void selectionSort(int arr[], int size)
{
int i,j;
for (i = 0; i < size - 1; i++)
{

P BHANU PRAKASH 9551234604 [email protected] 5

 int minIndex = i;
for (j = i + 1; j < size; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// Swap arr[i] and arr[minIndex]
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
int main()
{
int size,i;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array: ");
for (i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Original array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr, size);
printf("Sorted array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
OUTPUT
Enter the size of the array: 10
Enter the elements of the array: 2 9 1 8 2 4 7 3 6 5
Original array: 2 9 1 8 2 4 7 3 6 5
Sorted array: 1 2 2 3 4 5 6 7 8 9

INSERTION SORT:
#include <stdio.h>
void insertionSort(int arr[], int size)
{

P BHANU PRAKASH 9551234604 [email protected] 6

 int i;
for (i = 1; i < size; i++)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main()
{
int size,i;
printf("Enter the size of the array: ");
scanf("%d", &size);
int arr[size];
printf("Enter the elements of the array: ");
for (i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Original array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr, size);
printf("Sorted array: ");
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
OUTPUT:
Enter the size of the array: 10
Enter the elements of the array: 3 8 2 9 7 4 6 5 11 66
Original array: 3 8 2 9 7 4 6 5 11 66
Sorted array: 2 3 4 5 6 7 8 9 11 66

P BHANU PRAKASH 9551234604 [email protected] 7

Exercise 2: Linked List Implementation
i) Implement a singly linked list and perform insertion and deletion operations.
ii) Develop a program to reverse a linked list iteratively and recursively.
iii) Solve problems involving linked list traversal and manipulation.
1. Implement a singly linked list and perform insertion and deletion operations
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node in the linked list
struct Node
{
int data;
struct Node* next;
};
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data)
{
// Allocate memory for new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// Assign data to the new node
new_node->data = new_data;
// Set the next of new node to the current head
new_node->next = *head_ref;
// Move the head to point to the new node
*head_ref = new_node;
}
// Function to delete a node with given key from the linked list
void deleteNode(struct Node** head_ref, int key)
{
// Store head node
struct Node* temp = *head_ref, *prev;
// If head node itself holds the key to be deleted
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next; // Changed head
free(temp); // Free old head
return;
}
// Search for the key to be deleted, keep track of the previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL)
return;

P BHANU PRAKASH 9551234604 [email protected] 8

 // Unlink the node from linked list
prev->next = temp->next;
// Free memory
free(temp);
}
// Function to print the linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Function to delete the entire linked list
void deleteList(struct Node** head_ref)
{
struct Node* current = *head_ref;
struct Node* next;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
*head_ref = NULL;
}
// Driver program to test above functions
int main()
{
struct Node* head = NULL;
int data;
char choice;
do {
printf("Enter data for the new node: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
printf("Do you want to insert another node? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
printf("Linked list after insertion: ");
printList(head);
printf("\n");
// Example deletion
int key;
printf("Enter a value to delete from the list: ");

P BHANU PRAKASH 9551234604 [email protected] 9

 scanf("%d", &key);
deleteNode(&head, key);
printf("Linked list after deletion: ");
printList(head);
printf("\n");
// Free the linked list memory
deleteList(&head);
return 0;
}
OUTPUT:
Enter data for the new node: 2
Do you want to insert another node? (y/n): y
Enter data for the new node: 3
Do you want to insert another node? (y/n): y
Enter data for the new node: 5
Do you want to insert another node? (y/n): y
Enter data for the new node: 7
Do you want to insert another node? (y/n): y
Enter data for the new node: 9
Do you want to insert another node? (y/n): n
Linked list after insertion: 9 7 5 3 2
Enter a value to delete from the list: 5
Linked list after deletion: 9 7 3 2
2 . Develop a program to reverse a linked list iteratively and recursively.
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node in the linked list
struct Node
{
int data;
struct Node* next;
};
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data)
{
// Allocate memory for new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// Assign data to the new node
new_node->data = new_data;
// Set the next of new node to the current head
new_node->next = *head_ref;
// Move the head to point to the new node
*head_ref = new_node;
}
// Function to print the linked list
void printList(struct Node* node)

P BHANU PRAKASH 9551234604 [email protected] 10

 {
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

// Function to reverse the linked list iteratively

void reverseIterative(struct Node** head_ref)
{
struct Node *prev = NULL, *current = *head_ref, *next = NULL;
while (current != NULL)
{
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead
prev = current;
current = next;
}
*head_ref = prev; // Set head to the last node
}
// Function to reverse the linked list recursively
void reverseRecursive(struct Node** head_ref)
{
struct Node* first;
struct Node* rest;
// Empty list or list with only one element
if (*head_ref == NULL || (*head_ref)->next == NULL)
return;
first = *head_ref; // First node
rest = first->next; // Rest of the list
// Reverse the rest of the list
reverseRecursive(&rest);
// Link first node to the last of the reversed list
first->next->next = first;
first->next = NULL;
// Update head to point to the last node after reversal
*head_ref = rest;
}
// Function to delete the entire linked list
void deleteList(struct Node** head_ref)
{
struct Node* current = *head_ref;

P BHANU PRAKASH 9551234604 [email protected] 11

 struct Node* next;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
*head_ref = NULL;
}
// Driver program to test above functions
int main()
{
struct Node* head = NULL;
int data;
char choice;
do {
printf("Enter data for the new node: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
printf("Do you want to insert another node? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
printf("Linked list before reversing: ");
printList(head);
printf("\n");
printf("Choose traversal method for reversed list:\n");
printf("1. Iterative\n");
printf("2. Recursive\n");
printf("Enter your choice: ");
int traversalChoice;
scanf("%d", &traversalChoice);
// Reverse the linked list
reverseIterative(&head); // or reverseRecursive(&head);
printf("Linked list after reversal: ");
switch (traversalChoice)
{
case 1:
printList(head); // Iterative traversal
break;
case 2:
reverseRecursive(&head); // Reverse again before recursive traversal
printList(head); // Recursive traversal
break;
default:
printf("Invalid choice.\n");
}

P BHANU PRAKASH 9551234604 [email protected] 12

 printf("\n");
// Free the linked list memory
deleteList(&head);
return 0;
}
OUTPUT
Enter data for the new node: 2
Do you want to insert another node? (y/n): y
Enter data for the new node: 3
Do you want to insert another node? (y/n): y
Enter data for the new node: 5
Do you want to insert another node? (y/n): n
Linked list before reversing: 5 3 2
Choose traversal method for reversed list:
1. Iterative
2. Recursive
Enter your choice: 2
Linked list after reversal: 5 3 2
3.Solve problems involving linked list traversal and manipulation
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node in the linked list
struct Node
{
int data;
struct Node* next;
};
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data)
{
// Allocate memory for new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// Assign data to the new node
new_node->data = new_data;
// Set the next of new node to the current head
new_node->next = *head_ref;
// Move the head to point to the new node
*head_ref = new_node;
}
// Function to insert a new node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data)
{
// Allocate memory for new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// Assign data to the new node
new_node->data = new_data;

P BHANU PRAKASH 9551234604 [email protected] 13

 // Set next of new node to NULL, as it will be the last node
new_node->next = NULL;
// If the linked list is empty, make the new node as head
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
// Traverse to the last node
struct Node* last = *head_ref;
while (last->next != NULL)
last = last->next;
// Change the next of the last node
last->next = new_node;
}
// Function to print the linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Function to remove all occurrences of a specific value from the linked list
void removeValue(struct Node** head_ref, int value)
{
struct Node* current = *head_ref;
struct Node* prev = NULL;
struct Node* temp = NULL;
// Traverse the list
while (current != NULL)
{
// If current node has the value to be removed
if (current->data == value)
{
// If it's the head node
if (current == *head_ref)
{
temp = current;
*head_ref = current->next;
current = *head_ref;
}
else
{
// If it's not the head node

P BHANU PRAKASH 9551234604 [email protected] 14

 temp = current;
prev->next = current->next;
current = current->next;
}
free(temp);
}
else
{
// Move to the next node
prev = current;
current = current->next;
}
}
}
// Driver program to test above functions
int main()
{
struct Node* head = NULL;
int data;
char choice;
// Dynamically insert elements into the linked list
do {
printf("Enter data for the new node: ");
scanf("%d", &data);
// Ask user for choice of insertion
printf("Where would you like to insert the new node?\n");
printf("1. At the beginning\n");
printf("2. At the end\n");
printf("Enter your choice: ");
int insertionChoice;
scanf("%d", &insertionChoice);
// Perform insertion based on user's choice
if (insertionChoice == 1)
insertAtBeginning(&head, data);
else if (insertionChoice == 2)
insertAtEnd(&head, data);
else
printf("Invalid choice. Node not inserted.\n");
printf("Do you want to insert another node? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
// Print original linked list
printf("Original linked list: ");
printList(head);
printf("\n");
// Dynamically input the value to remove

P BHANU PRAKASH 9551234604 [email protected] 15

 int valueToRemove;
printf("Enter the value to remove: ");
scanf("%d", &valueToRemove);
// Remove the specified value from the linked list
removeValue(&head, valueToRemove);
// Print modified linked list after removal
printf("Linked list after removing %d: ", valueToRemove);
printList(head);
printf("\n");
// Free the linked list memory
struct Node* current = head;
struct Node* next;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
return 0;
}
OUTPUT :
Enter data for the new node: 4
Where would you like to insert the new node?
1. At the beginning
2. At the end
Enter your choice: 1
Do you want to insert another node? (y/n): y
Enter data for the new node: 6
Where would you like to insert the new node?
1. At the beginning
2. At the end
Enter your choice: 2
Do you want to insert another node? (y/n): y
Enter data for the new node: 8
Where would you like to insert the new node?
1. At the beginning
2. At the end
Enter your choice: 1
Do you want to insert another node? (y/n): n
Original linked list: 8 4 6
Enter the value to remove: 4
Linked list after removing 4: 8 6

P BHANU PRAKASH 9551234604 [email protected] 16

Exercise 3: Linked List Applications
i) Create a program to detect and remove duplicates from a linked list.
ii) Implement a linked list to represent polynomials and perform addition.
iii) Implement a double-ended queue (deque) with essential operations.

1.Create a program to detect and remove duplicates from a linked list.

#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node
{
int data;
struct Node* next;
};
// Function to create a new node
struct Node* newNode(int data)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Function to insert a new node at the end of the list
void insertNode(struct Node** head, int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL)
{
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
// Function to remove duplicates from a sorted linked list
// Function to remove duplicates from the linked list
void removeDuplicates(struct Node* head)
{
struct Node *current, *temp, *dup;

P BHANU PRAKASH 9551234604 [email protected] 17

 current = head;
while (current != NULL && current->next != NULL) {
temp = current;
// Compare current node with all the nodes after it
while (temp->next != NULL)
{
// If duplicate is found, delete it
if (current->data == temp->next->data)
{
dup = temp->next;
temp->next = temp->next->next;
free(dup);
}
else
{
temp = temp->next;
}
}
current = current->next;
}
}
// Function to print the linked list
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function
int main() {
struct Node* head = NULL;
int num_elements, data;
// Ask the user for the number of elements in the linked list
printf("Enter the number of elements: ");
scanf("%d", &num_elements);
// Insert elements into the linked list
printf("Enter the elements: \n");
for (int i = 0; i < num_elements; i++) {
scanf("%d", &data);
insertNode(&head, data);
}
printf("Original Linked List: \n");

P BHANU PRAKASH 9551234604 [email protected] 18

 printList(head);
// Remove duplicates from the linked list
removeDuplicates(head);
printf("\nLinked List after removing duplicates: \n");
printList(head);

return 0;
}

OUTPUT
Enter the number of elements: 7
Enter the elements:
10
20
30
20
40
30
50
Original Linked List:
10 20 30 20 40 30 50
Linked List after removing duplicates:
10 20 30 40 50

2. Implement a linked list to represent polynomials and perform addition.

#include <stdio.h>
#include <stdlib.h>
// Node structure for a term in a polynomial
struct Term
{
int coefficient;
int exponent;
struct Term* next;
};
// Function to create a new term node
struct Term* createTerm(int coefficient, int exponent)
{
struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term));
newTerm->coefficient = coefficient;
newTerm->exponent = exponent;
newTerm->next = NULL;
return newTerm;
}
// Function to insert a term into the polynomial
void insertTerm(struct Term** poly, int coefficient, int exponent)
{

P BHANU PRAKASH 9551234604 [email protected] 19

 struct Term* newTerm = createTerm(coefficient, exponent);
if (*poly == NULL)
{
*poly = newTerm;
return;
}
struct Term* temp = *poly;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newTerm;
}
// Function to add two polynomials
struct Term* addPolynomials(struct Term* poly1, struct Term* poly2)
{
struct Term* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exponent > poly2->exponent)
{
insertTerm(&result, poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
}
else if (poly1->exponent < poly2->exponent)
{
insertTerm(&result, poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
}
else
{
int sum_coefficients = poly1->coefficient + poly2->coefficient;
if (sum_coefficients != 0)
{
insertTerm(&result, sum_coefficients, poly1->exponent);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
}
// Append remaining terms of poly1
while (poly1 != NULL)
{
insertTerm(&result, poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
}
// Append remaining terms of poly2

P BHANU PRAKASH 9551234604 [email protected] 20

 while (poly2 != NULL)
{
insertTerm(&result, poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
}
return result;
}
// Function to display a polynomial
void displayPolynomial(struct Term* poly)
{
struct Term* temp = poly;
while (temp != NULL)
{
printf("%dx^%d ", temp->coefficient, temp->exponent);
temp = temp->next;
if (temp != NULL)
printf("+ ");
}
printf("\n");
}
// Function to free the memory allocated for a polynomial
void freePolynomial(struct Term* poly)
{
struct Term* temp;
while (poly != NULL)
{
temp = poly;
poly = poly->next;
free(temp);
}
}
// main function
int main()
{
struct Term *poly1 = NULL, *poly2 = NULL, *result = NULL;
int num_terms, coefficient, exponent;

printf("Enter the number of terms in the first polynomial: ");

scanf("%d", &num_terms);
printf("Enter the terms of the first polynomial (coefficient exponent):\n");
for (int i = 0; i < num_terms; i++)
{
scanf("%d %d", &coefficient, &exponent);
insertTerm(&poly1, coefficient, exponent);
}
printf("Enter the number of terms in the second polynomial: ");

P BHANU PRAKASH 9551234604 [email protected] 21

 scanf("%d", &num_terms);
printf("Enter the terms of the second polynomial (coefficient exponent):\n");
for (int i = 0; i < num_terms; i++)
{
scanf("%d %d", &coefficient, &exponent);
insertTerm(&poly2, coefficient, exponent);
}
printf("First Polynomial: ");
displayPolynomial(poly1);
printf("Second Polynomial: ");
displayPolynomial(poly2);
result = addPolynomials(poly1, poly2);
printf("Sum of Polynomials: ");
displayPolynomial(result);
// Free memory
freePolynomial(poly1);
freePolynomial(poly2);
freePolynomial(result);
return 0;
}

OUTPUT:
Enter the number of terms in the first polynomial: 3
Enter the terms of the first polynomial (coefficient exponent):
13
42
71
Enter the number of terms in the second polynomial: 2
Enter the terms of the second polynomial (coefficient exponent):
42
67
First Polynomial: 1x^3 + 4x^2 + 7x^1
Second Polynomial: 4x^2 + 6x^7
Sum of Polynomials: 1x^3 + 8x^2 + 6x^7 + 7x^1

3.Implement a double-ended queue (deque) with essential operations.

#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the deque
struct Node
{
int data;
struct Node* prev;
struct Node* next;
};
// Structure to represent a deque

P BHANU PRAKASH 9551234604 [email protected] 22

 struct Deque
{
struct Node* front;
struct Node* rear;
};
// Function to create a new node
struct Node* createNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to create an empty deque
struct Deque* createDeque()
{
struct Deque* deque = (struct Deque*)malloc(sizeof(struct Deque));
if (deque == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
deque->front = NULL;
deque->rear = NULL;
return deque;
}
// Function to check if the deque is empty
int isEmpty(struct Deque* deque)
{
return deque->front == NULL;
}
// Function to insert an element at the front of the deque
void insertFront(struct Deque* deque, int data)
{
struct Node* newNode = createNode(data);
if (isEmpty(deque))
{
deque->front = newNode;
deque->rear = newNode;
}
else

P BHANU PRAKASH 9551234604 [email protected] 23

 {
newNode->next = deque->front;
deque->front->prev = newNode;
deque->front = newNode;
}
}
// Function to insert an element at the rear of the deque
void insertRear(struct Deque* deque, int data)
{
struct Node* newNode = createNode(data);
if (isEmpty(deque))
{
deque->front = newNode;
deque->rear = newNode;
}
else
{
newNode->prev = deque->rear;
deque->rear->next = newNode;
deque->rear = newNode;
}
}
// Function to delete an element from the front of the deque
int deleteFront(struct Deque* deque)
{
if (isEmpty(deque))
{
printf("Deque is empty!\n");
exit(1);
}
struct Node* temp = deque->front;
int data = temp->data;
deque->front = deque->front->next;
if (deque->front == NULL)
{
deque->rear = NULL;
}
else
{
deque->front->prev = NULL;
}
free(temp);
return data;
}
// Function to delete an element from the rear of the deque
int deleteRear(struct Deque* deque)

P BHANU PRAKASH 9551234604 [email protected] 24

 {
if (isEmpty(deque))
{
printf("Deque is empty!\n");
exit(1);
}
struct Node* temp = deque->rear;
int data = temp->data;
deque->rear = deque->rear->prev;
if (deque->rear == NULL)
{
deque->front = NULL;
}
else
{
deque->rear->next = NULL;
}
free(temp);
return data;
}
// Function to display the elements of the deque from front to rear
void displayDeque(struct Deque* deque)
{
if (isEmpty(deque))
{
printf("Deque is empty!\n");
return;
}
struct Node* temp = deque->front;
printf("Deque from front to rear: ");
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
//Main function
int main()
{
struct Deque* deque = createDeque();
int num_elements, data, i;
// Ask the user for the number of elements in the deque
printf("Enter the number of elements: ");
scanf("%d", &num_elements);
// Insert elements at front

P BHANU PRAKASH 9551234604 [email protected] 25

 printf("Enter the elements to be inserted at the front: ");
for (i = 0; i < num_elements; i++)
{
scanf("%d", &data);
insertFront(deque, data);
}
// Insert elements at rear
printf("Enter the elements to be inserted at the rear: ");
for (i = 0; i < num_elements; i++)
{
scanf("%d", &data);
insertRear(deque, data);
}
displayDeque(deque);
// Delete elements from front and rear
printf("Deleted element from front: %d\n", deleteFront(deque));
printf("Deleted element from rear: %d\n", deleteRear(deque));
displayDeque(deque);
// Free memory
free(deque);
return 0;
}

OUTPUT:
Enter the number of elements: 3
Enter the elements to be inserted at the front: 12
34
32
Enter the elements to be inserted at the rear: 76
45
98
Deque from front to rear: 32 34 12 76 45 98
Deleted element from front: 32
Deleted element from rear: 98
Deque from front to rear: 34 12 76 45

P BHANU PRAKASH 9551234604 [email protected] 26

Exercise 4: Double Linked List Implementation
i) Implement a doubly linked list and perform various operations to understand its
properties and applications.
ii) Implement a circular linked list and perform insertion, deletion, and traversal.

i. Implement a doubly linked list and perform various operations to understand its
properties and applications.
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the 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));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(struct Node** head, int data)
{
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
}
else
{
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}

// Function to insert a node at the end of the list

void insertAtEnd(struct Node** head, int data)

P BHANU PRAKASH 9551234604 [email protected] 27

 {
struct Node* newNode = createNode(data);
if (*head == NULL)
{
*head = newNode;
}
else
{
struct Node* temp = *head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// Function to insert a node after a given node
void insertAfter(struct Node* prevNode, int data)
{
if (prevNode == NULL)
{
printf("Previous node cannot be NULL!\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
if (prevNode->next != NULL)
{
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
newNode->prev = prevNode;
}
// Function to delete the first occurrence of a node with a given key
void deleteNode(struct Node** head, int key)
{
if (*head == NULL)
{
printf("List is empty!\n");
return;
}
struct Node* temp = *head;
if (temp->data == key)
{
*head = temp->next;

P BHANU PRAKASH 9551234604 [email protected] 28

 if (*head != NULL)
{
(*head)->prev = NULL;
}
free(temp);
return;
}
while (temp != NULL && temp->data != key)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Key not found in the list!\n");
return;
}
temp->prev->next = temp->next;
if (temp->next != NULL)
{
temp->next->prev = temp->prev;
}
free(temp);
}
// Function to reverse the doubly linked list
void reverseList(struct Node** head)
{
struct Node *temp = NULL, *current = *head;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL)
{
*head = temp->prev;
}
}
// Function to display the doubly linked list
void displayList(struct Node* head)
{
if (head == NULL)
{
printf("List is empty!\n");
return;

P BHANU PRAKASH 9551234604 [email protected] 29

 }
printf("Doubly Linked List: ");
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
//main function
int main()
{
struct Node* head = NULL;
int choice, data, key;
do
{
printf("\n1. Insert at the beginning\n2. Insert at the end\n3. Insert after a node\n4. Delete a
node\n5. Reverse the list\n6. Display the list\n7. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter the data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter the data of the node after which you want to insert: ");
scanf("%d", &key);
struct Node* temp = head;
while (temp != NULL && temp->data != key)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Node with given data not found!\n");
}
else
{
printf("Enter the data to be inserted after %d: ", key);

P BHANU PRAKASH 9551234604 [email protected] 30

 scanf("%d", &data);
insertAfter(temp, data);
}
break;
case 4:
printf("Enter the data of the node to be deleted: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 5:
reverseList(&head);
printf("List reversed successfully!\n");
break;
case 6:
displayList(head);
break;
case 7:
printf("Exiting...\n");
break;
default:
printf("Invalid choice! Please enter a valid option.\n");
}
} while (choice != 7);
return 0;
}

OUTPUT:
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 1
Enter the data to insert at the beginning: 345
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 1
Enter the data to insert at the beginning: 234
1. Insert at the beginning

P BHANU PRAKASH 9551234604 [email protected] 31

 2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 2
Enter the data to insert at the end: 678
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 3
Enter the data of the node after which you want to insert: 2
Node with given data not found!
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 3
Enter the data of the node after which you want to insert: 678
Enter the data to be inserted after 678: 547
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 6
Doubly Linked List: 234 345 678 547
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 5
List reversed successfully!

P BHANU PRAKASH 9551234604 [email protected] 32

 1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 6
Doubly Linked List: 547 678 345 234
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 4
Enter the data of the node to be deleted: 678
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 6
Doubly Linked List: 547 345 234
1. Insert at the beginning
2. Insert at the end
3. Insert after a node
4. Delete a node
5. Reverse the list
6. Display the list
7. Exit
Enter your choice: 7
Exiting...

2. Implement a circular linked list and perform insertion, deletion, and traversal.
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a node in the circular linked list
struct Node
{
int data;
struct Node* next;
};

P BHANU PRAKASH 9551234604 [email protected] 33

 // Function to create a new node
struct Node* createNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(struct Node** head, int data)
{
struct Node* newNode = createNode(data);
if (*head == NULL)
{
*head = newNode;
newNode->next = *head;
}
else
{
struct Node* temp = *head;
while (temp->next != *head)
{
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
*head = newNode;
}
}
// Function to insert a node at the end of the circular linked list
void insertAtEnd(struct Node** head, int data)
{
struct Node* newNode = createNode(data);
if (*head == NULL)
{
*head = newNode;
newNode->next = *head;
}
else
{
struct Node* temp = *head;

P BHANU PRAKASH 9551234604 [email protected] 34

 while (temp->next != *head)
{
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
}
// Function to delete the first occurrence of a node with a given key
void deleteNode(struct Node** head, int key)
{
if (*head == NULL)
{
printf("List is empty!\n");
return;
}
struct Node* temp = *head, *prev = NULL;
if (temp->data == key)
{
while (temp->next != *head)
{
temp = temp->next;
}
temp->next = (*head)->next;
free(*head);
*head = temp->next;
return;
}
while (temp->next != *head && temp->data != key)
{
prev = temp;
temp = temp->next;
}
if (temp->data != key)
{
printf("Key not found in the list!\n");
return;
}
prev->next = temp->next;
free(temp);
}
// Function to display the circular linked list
void displayList(struct Node* head)
{
if (head == NULL)
{

P BHANU PRAKASH 9551234604 [email protected] 35

 printf("List is empty!\n");
return;
}
struct Node* temp = head;
printf("Circular Linked List: ");
do
{
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
//main function
int main()
{
struct Node* head = NULL;
int choice, data, key;
do
{
printf("\n1. Insert at the beginning\n");
printf("2. Insert at the end\n");
printf("3. Delete a node\n");
printf("4. Display the list\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter the data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter the data of the node to be deleted: ");
scanf("%d", &data);
deleteNode(&head, data);
break;
case 4:
displayList(head);
break;

P BHANU PRAKASH 9551234604 [email protected] 36

 case 5:
printf("Exiting...\n");
break;
default:
printf("Invalid choice! Please enter a valid option.\n");
}
} while (choice != 5);
return 0;
}

OUTPUT:
1. Insert at the beginning
2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 1
Enter the data to insert at the beginning: 356

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 1
Enter the data to insert at the beginning: 456

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 1
Enter the data to insert at the beginning: 345

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 2
Enter the data to insert at the end: 765

1. Insert at the beginning

2. Insert at the end
3. Delete a node

P BHANU PRAKASH 9551234604 [email protected] 37

 4. Display the list
5. Exit
Enter your choice: 2
Enter the data to insert at the end: 657

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 2
Enter the data to insert at the end: 567

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 4
Circular Linked List: 345 456 356 765 657 567

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 3
Enter the data of the node to be deleted: 567

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 4
Circular Linked List: 345 456 356 765 657

1. Insert at the beginning

2. Insert at the end
3. Delete a node
4. Display the list
5. Exit
Enter your choice: 5
Exiting...

P BHANU PRAKASH 9551234604 [email protected] 38

Exercise 5: Stack Operation
i) Implement a stack using arrays and linked lists.
ii) Write a program to evaluate a postfix expression using a stack.
iii) Implement a program to check for balanced parentheses using a stack.

1.Implement a stack using arrays and linked lists

#Stack using arrays
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
void peek(void);
int isfull(void);
int isempty(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.PEEK\n\t 4.DISPLAY\n\t 5.ISFULL\n\t 6.ISEMPTY\n\t
7.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
peek();
break;
}
case 4:

P BHANU PRAKASH 9551234604 [email protected] 39

 {
display();
break;
}
case 5:
{
if(isfull())
printf("The stack is full");
else
printf("The stack is not full");
break;
}
case 6:
{
if(isempty())
printf("The stack is empty");
else
printf("The stack is not empty");
break;
}
case 7:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=7);
return 0;
}
void push()
{
if(isfull())
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;

P BHANU PRAKASH 9551234604 [email protected] 40

 }
}
void pop()
{
if(isempty())
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(isempty())
{
printf("\n STACK is empty");
}
else
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
}
void peek(){
if(isempty()) printf("Stack is empty");
else printf("The peek element is %d",stack[top]);
}
int isfull(){
if(top>=n-1)
return 1;
else return 0;
}
int isempty(){
if(top<=-1) return 1;
else return 0;
}
OUTPUT:
Enter the size of STACK[MAX=100]:5
STACK OPERATIONS USING ARRAY
--------------------------------
1.PUSH

P BHANU PRAKASH 9551234604 [email protected] 41

 2.POP
3.PEEK
4.DISPLAY
5.ISFULL
6.ISEMPTY
7.EXIT
Enter the Choice:1
Enter a value to be pushed:456
Enter the Choice:1
Enter a value to be pushed:324
Enter the Choice:1
Enter a value to be pushed:4
Enter the Choice:1
Enter a value to be pushed:56
Enter the Choice:5
The stack is not full
Enter the Choice:1
Enter a value to be pushed:1
Enter the Choice:1
STACK is over flow
Enter the Choice:4
The elements in STACK
1
56
4
324
456
Press Next Choice
Enter the Choice:2
The popped elements is 1
Enter the Choice:3
The peek element is 56
Enter the Choice:4
The elements in STACK
56
4
324
456
Press Next Choice
Enter the Choice:2
The popped elements is 56
Enter the Choice:6
The stack is not empty
Enter the Choice:2
The popped elements is 4
Enter the Choice:2

P BHANU PRAKASH 9551234604 [email protected] 42

 The popped elements is 324
Enter the Choice:2
The popped elements is 456
Enter the Choice:2
Stack is under flow
Enter the Choice:6
The stack is empty
Enter the Choice:7

#Stack using linkedlist

#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node
struct Node
{
int data;
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->next = NULL;
return newNode;
}
// Structure to represent the stack
struct Stack
{
struct Node* top;
};
// Function to initialize the stack
struct Stack* createStack()
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack)
{
return (stack->top == NULL);
}
// Function to push an element onto the stack
void push(struct Stack* stack, int data)
{

P BHANU PRAKASH 9551234604 [email protected] 43

 struct Node* newNode = createNode(data);
newNode->next = stack->top;
stack->top = newNode;
printf("%d pushed to stack\n", data);
}
// Function to pop an element from the stack
int pop(struct Stack* stack)
{
if (isEmpty(stack))
{
printf("Stack Underflow\n");
return -1;
}
struct Node* temp = stack->top;
int popped = temp->data;
stack->top = stack->top->next;
free(temp);
return popped;
}
// Function to peek the top element of the stack
int peek(struct Stack* stack)
{
if (isEmpty(stack))
{
printf("Stack is empty\n");
return -1;
}
return stack->top->data;
}
// Function to display all elements of the stack
void display(struct Stack* stack)
{
if (isEmpty(stack))
{
printf("Stack is empty\n");
return;
}
printf("Stack elements: ");
struct Node* current = stack->top;
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

P BHANU PRAKASH 9551234604 [email protected] 44

 //main function
int main()
{
struct Stack* stack = createStack();
int choice, data;
printf("\nStack Operations:\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Isempty\n");
printf("6. Exit\n");
do
{
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter element to push: ");
scanf("%d", &data);
push(stack, data);
break;
case 2:
printf("Popped element is %d\n", pop(stack));
break;
case 3:
printf("Top element is %d\n", peek(stack));
break;
case 4:
display(stack);
break;
case 5:
if(isEmpty(stack)) printf("The stack is empty\n");
else printf("The stack is not empty\n");break;
case 6:
printf("\nExiting...\n");
exit(0);
default:
printf("Invalid choice\n");
}
} while (choice != 6);
return 0;
}
OUTPUT:
Stack Operations:

P BHANU PRAKASH 9551234604 [email protected] 45

 1. Push
2. Pop
3. Peek
4. Display
5. Isempty
6. Exit
Enter your choice: 1
Enter element to push: 234
234 pushed to stack
Enter your choice: 1
Enter element to push: 564
564 pushed to stack
Enter your choice: 1
Enter element to push: 345
345 pushed to stack
Enter your choice: 3
Top element is 345
Enter your choice: 4
Stack elements: 345 564 234
Enter your choice: 5
The stack is not empty
Enter your choice: 2
Popped element is 345
Enter your choice: 22
Invalid choice
Enter your choice: 2
Popped element is 564
Enter your choice: 2
Popped element is 234
Enter your choice: 2
Stack Underflow
Popped element is -1
Enter your choice: 5
The stack is empty
Enter your choice: 6

Exiting...

ii.Write a program to evaluate a postfix expression using a stack.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
// Stack variables and functions
int stack[MAX_SIZE];
int top = -1;

P BHANU PRAKASH 9551234604 [email protected] 46

 void push(int item)
{
if (top == MAX_SIZE - 1)
{
printf("Stack Overflow\n");
exit(1);
}
stack[++top] = item;
}
int pop()
{
if (top == -1) {
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
int evaluatePostfix(char *exp)
{
for (int i = 0; exp[i] != '\0'; i++)
{
if (isdigit(exp[i]))
{
push(exp[i] - '0');
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/')
{
int operand2 = pop();
int operand1 = pop();

switch (exp[i])
{
case '+':
push(operand1 + operand2);
break;
case '-':
push(operand1 - operand2);
break;
case '*':
push(operand1 * operand2);
break;
case '/':
push(operand1 / operand2);
break;
}
}

P BHANU PRAKASH 9551234604 [email protected] 47

 }
return pop();
}
int main() {
char exp[MAX_SIZE];
printf("Enter postfix expression: ");
fgets(exp, MAX_SIZE, stdin);
int result = evaluatePostfix(exp);
printf("Result: %d\n", result);
return 0;
}
OUTPUT
Enter postfix expression: 3 5 2 * +
Result 13

ii. Implement a program to check for balanced parentheses using a stack

#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node
struct Node
{
char data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(char data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Structure to represent the stack
struct Stack
{
struct Node* top;
};
// Function to initialize the stack
struct Stack* createStack()
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack)

P BHANU PRAKASH 9551234604 [email protected] 48

 {
return (stack->top == NULL);
}
// Function to push an element onto the stack
void push(struct Stack* stack, char data)
{
struct Node* newNode = createNode(data);
newNode->next = stack->top;
stack->top = newNode;
}
// Function to pop an element from the stack
char pop(struct Stack* stack)
{
if (isEmpty(stack))
{
printf("Stack Underflow\n");
exit(EXIT_FAILURE);
}
struct Node* temp = stack->top;
char popped = temp->data;
stack->top = stack->top->next;
free(temp);
return popped;
}
// Function to check if parentheses are balanced
int areParenthesesBalanced(char* expression)
{
struct Stack* stack = createStack();
for (int i = 0; expression[i] != '\0'; i++)
{
if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{')
{
push(stack, expression[i]);
}
else if (expression[i] == ')' || expression[i] == ']' || expression[i] == '}')
{
if (isEmpty(stack))
{
return 0; // Unbalanced - closing parenthesis encountered without corresponding
opening parenthesis
}
char popped = pop(stack);
if ((expression[i] == ')' && popped != '(') || (expression[i] == ']' && popped != '[') ||
(expression[i] == '}' && popped != '{'))
{
return 0; // Unbalanced - mismatched parentheses

P BHANU PRAKASH 9551234604 [email protected] 49

 }
}
}
return isEmpty(stack); // If stack is empty, parentheses are balanced
}
int main() {
char expression[100];
printf("Enter the expression: ");
fgets(expression, sizeof(expression), stdin);
if (areParenthesesBalanced(expression))
{
printf("Parentheses are balanced\n");
}
else {
printf("Parentheses are not balanced\n");
}
return 0;
}

OUTPUT
Output 1:
Enter the expression: ((a+b)*[c-d])
Parentheses are balanced
Output 2:
Enter the expression: ((a+b)*[c-d]
Parentheses are not balanced

P BHANU PRAKASH 9551234604 [email protected] 50

Exercise 6: Queue Operations
i) Implement a queue using arrays and linked lists.
ii) Develop a program to simulate a simple printer queue system.
iii) Solve problems involving circular queues.

i.Implement a queue using arrays and linked lists.

//Queue using arrays
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = -1, rear = -1;
// Function to check if the queue is empty
int isEmpty()
{
return (front == -1 && rear == -1);
}
// Function to check if the queue is full
int isFull() {
return ((rear + 1) % MAX_SIZE == front);
}
// Function to add an element to the rear of the queue (enqueue)
void enqueue(int item)
{
if (isFull())
{
printf("Queue Overflow\n");
return;
}
if (isEmpty())
{
front = rear = 0;
}
else
{
rear = (rear + 1) % MAX_SIZE;
}
queue[rear] = item;
printf("%d enqueued to the queue\n", item);
}
// Function to remove an element from the front of the queue (dequeue)
int dequeue()
{
if (isEmpty())
{
printf("Queue Underflow\n");

P BHANU PRAKASH 9551234604 [email protected] 51

 return -1;
}
int dequeued = queue[front];
if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % MAX_SIZE;
}
return dequeued;
}
// Function to display all elements of the queue
void display()
{
if (isEmpty())
{
printf("Queue is empty\n");
return;
}
printf("Queue elements: ");
int i = front;
while (i != rear) {
printf("%d ", queue[i]);
i = (i + 1) % MAX_SIZE;
}
printf("%d\n", queue[rear]);
}
// Function to return the element at the front of the queue
int getFront()
{
if (isEmpty())
{
printf("Queue is empty\n");
return -1;
}
return queue[front];
}
int main()
{
int choice, element;
do
{
printf("\nQueue Operations:\n");
printf("1. Enqueue\n");

P BHANU PRAKASH 9551234604 [email protected] 52

 printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Front\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter element to enqueue: ");
scanf("%d", &element);
enqueue(element);
break;
case 2:
printf("Dequeued element: %d\n", dequeue());
break;
case 3:
display();
break;
case 4:
printf("Front element: %d\n", getFront());
break;
case 5:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice\n");
}
} while (choice != 5);
return 0;
}
OUTPUT:
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 234
234 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display

P BHANU PRAKASH 9551234604 [email protected] 53

 4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 22
22 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 123
123 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 123
123 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 2
Dequeued element: 234

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 3
Queue elements: 22 123 123

Queue Operations:
1. Enqueue

P BHANU PRAKASH 9551234604 [email protected] 54

 2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 4
Front element: 22

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 5
Exiting...

//Queue using linked list

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent the queue
struct Queue
{
int* array;
int front, rear;
int capacity;
};
// Function to initialize the queue
struct Queue* createQueue(int capacity)
{
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->array = (int*)malloc(capacity * sizeof(int));
queue->front = -1;
queue->rear = -1;
queue->capacity = capacity;
return queue;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue)
{
return (queue->front == -1);
}
// Function to check if the queue is full
int isFull(struct Queue* queue)
{
return ((queue->rear + 1) % queue->capacity == queue->front);

P BHANU PRAKASH 9551234604 [email protected] 55

 }
// Function to add an element to the rear of the queue (enqueue)
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
{
printf("Queue Overflow\n");
return;
}
if (isEmpty(queue))
{
queue->front = 0;
queue->rear = 0;
}
else
{
queue->rear = (queue->rear + 1) % queue->capacity;
}
queue->array[queue->rear] = item;
printf("%d enqueued to the queue\n", item);
}
// Function to remove an element from the front of the queue (dequeue)
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
{
printf("Queue Underflow\n");
return -1;
}
int dequeued = queue->array[queue->front];
if (queue->front == queue->rear)
{
queue->front = -1;
queue->rear = -1;
}
else
{
queue->front = (queue->front + 1) % queue->capacity;
}
return dequeued;
}
// Function to display all elements of the queue
void display(struct Queue* queue)
{
if (isEmpty(queue))
{

P BHANU PRAKASH 9551234604 [email protected] 56

 printf("Queue is empty\n");
return;
}
printf("Queue elements: ");
int i = queue->front;
do
{
printf("%d ", queue->array[i]);
i = (i + 1) % queue->capacity;
} while (i != (queue->rear + 1) % queue->capacity);
printf("\n");
}
// Function to return the element at the front of the queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
{
printf("Queue is empty\n");
return -1;
}
return queue->array[queue->front];
}
int main()
{
struct Queue* queue = createQueue(MAX_SIZE);
int choice, element;
do
{
printf("\nQueue Operations:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Front\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter element to enqueue: ");
scanf("%d", &element);
enqueue(queue, element);
break;
case 2:
printf("Dequeued element: %d\n", dequeue(queue));
break;

P BHANU PRAKASH 9551234604 [email protected] 57

 case 3:
display(queue);
break;
case 4:
printf("Front element: %d\n", front(queue));
break;
case 5:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice\n");
}
} while (choice != 5);
return 0;
}

OUTPUT:
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 345
345 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 235
235 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 567
567 enqueued to the queue

P BHANU PRAKASH 9551234604 [email protected] 58

 Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 234
234 enqueued to the queue

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 2
Dequeued element: 345

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 3
Queue elements: 235 567 234

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 4
Front element: 235

Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 5
Exiting...

P BHANU PRAKASH 9551234604 [email protected] 59

ii.Develop a program to simulate a simple printer queue system.
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a job in the printer queue
typedef struct Job
{
int jobId;
struct Job* next;
} Job;
// Structure to represent the printer queue
typedef struct
{
Job* front;
Job* rear;
} PrinterQueue;
// Function prototypes
void initPrinterQueue(PrinterQueue *pq);
void enqueue(PrinterQueue *pq, int jobId);
int dequeue(PrinterQueue *pq);
int isEmpty(PrinterQueue *pq);
int main()
{
PrinterQueue printerQueue;
initPrinterQueue(&printerQueue);
int choice, jobId;
printf("Simple Printer Queue System\n");
do
{
printf("\n1. Add Job\n");
printf("2. Print Job\n");
printf("3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter Job ID: ");
scanf("%d", &jobId);
enqueue(&printerQueue, jobId);
printf("Job added to the printer queue.\n");
break;
case 2:
if (!isEmpty(&printerQueue))
{
jobId = dequeue(&printerQueue);
printf("Job ID %d printed.\n", jobId);

P BHANU PRAKASH 9551234604 [email protected] 60

 }
else
{
printf("Printer queue is empty. No jobs to print.\n");
}
break;
case 3:
printf("Exiting...\n");
break;
default:
printf("Invalid choice\n");
}
} while(choice != 3);
return 0;
}
// Initialize printer queue
void initPrinterQueue(PrinterQueue *pq)
{
pq->front = NULL;
pq->rear = NULL;
}
// Check if the printer queue is empty
int isEmpty(PrinterQueue *pq)
{
return pq->front == NULL;
}
// Enqueue a job into the printer queue
void enqueue(PrinterQueue *pq, int jobId)
{
Job* newJob = (Job*)malloc(sizeof(Job));
if (newJob == NULL)
{
printf("Memory allocation failed.\n");
exit(1);
}
newJob->jobId = jobId;
newJob->next = NULL;
if (isEmpty(pq))
{
pq->front = newJob;
pq->rear = newJob;
}
else
{
pq->rear->next = newJob;
pq->rear = newJob;

P BHANU PRAKASH 9551234604 [email protected] 61

 }
}
// Dequeue a job from the printer queue
int dequeue(PrinterQueue *pq)
{
if (isEmpty(pq))
{
printf("Printer queue is empty.\n");
exit(1);
}
int jobId;
Job* temp = pq->front;
jobId = temp->jobId;
if (pq->front == pq->rear)
{
pq->front = NULL;
pq->rear = NULL;
}
else
{
pq->front = pq->front->next;
}
free(temp);
return jobId;
}

OUTPUT:

Simple Printer Queue System

1. Add Job
2. Print Job
3. Exit
Enter your choice: 1
Enter Job ID: 101
Job added to the printer queue.
1. Add Job
2. Print Job
3. Exit
Enter your choice: 1
Enter Job ID: 102
Job added to the printer queue.
1. Add Job
2. Print Job
3. Exit
Enter your choice: 2
Job ID 101 printed.

P BHANU PRAKASH 9551234604 [email protected] 62

 1. Add Job
2. Print Job
3. Exit
Enter your choice: 2
Job ID 102 printed.
1. Add Job
2. Print Job
3. Exit
Enter your choice: 2
Printer queue is empty. No jobs to print.
1. Add Job
2. Print Job
3. Exit
Enter your choice: 3
Exiting...

iii.Solve problems involving circular queues.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent the circular queue
struct CircularQueue
{
int* array;
int front, rear;
int capacity;
};
// Function to initialize the circular queue
struct CircularQueue* createCircularQueue(int capacity)
{
struct CircularQueue* queue = (struct CircularQueue*)malloc(sizeof(struct CircularQueue));
queue->array = (int*)malloc(capacity * sizeof(int));
queue->front = -1;
queue->rear = -1;
queue->capacity = capacity;
return queue;
}
// Function to check if the circular queue is empty
int isEmpty(struct CircularQueue* queue)
{
return (queue->front == -1);
}
// Function to check if the circular queue is full
int isFull(struct CircularQueue* queue)
{
return ((queue->rear + 1) % queue->capacity == queue->front);

P BHANU PRAKASH 9551234604 [email protected] 63

 }
// Function to add an element to the rear of the circular queue (enqueue)
void enqueue(struct CircularQueue* queue, int item)
{
if (isFull(queue))
{
printf("Circular Queue Overflow\n");
return;
}
if (isEmpty(queue))
{
queue->front = 0;
queue->rear = 0;
}
else
{
queue->rear = (queue->rear + 1) % queue->capacity;
}
queue->array[queue->rear] = item;
printf("%d enqueued to the circular queue\n", item);
}
// Function to remove an element from the front of the circular queue (dequeue)
int dequeue(struct CircularQueue* queue)
{
if (isEmpty(queue))
{
printf("Circular Queue Underflow\n");
return -1;
}
int dequeued = queue->array[queue->front];
if (queue->front == queue->rear)
{
queue->front = -1;
queue->rear = -1;
}
else
{
queue->front = (queue->front + 1) % queue->capacity;
}
return dequeued;
}
// Function to display all elements of the circular queue
void display(struct CircularQueue* queue)
{
if (isEmpty(queue))
{

P BHANU PRAKASH 9551234604 [email protected] 64

 printf("Circular Queue is empty\n");
return;
}
printf("Circular Queue elements: ");
int i = queue->front;
do
{
printf("%d ", queue->array[i]);
i = (i + 1) % queue->capacity;
} while (i != (queue->rear + 1) % queue->capacity);
printf("\n");
}
// Function to return the element at the front of the circular queue
int front(struct CircularQueue* queue)
{
if (isEmpty(queue))
{
printf("Circular Queue is empty\n");
return -1;
}
return queue->array[queue->front];
}
int main()
{
int capacity, choice, element;

printf("Enter the capacity of the circular queue: ");

scanf("%d", &capacity);
struct CircularQueue* queue = createCircularQueue(capacity);
do
{
printf("\nCircular Queue Operations:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Front\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter element to enqueue: ");
scanf("%d", &element);
enqueue(queue, element);
break;

P BHANU PRAKASH 9551234604 [email protected] 65

 case 2:
printf("Dequeued element: %d\n", dequeue(queue));
break;
case 3:
display(queue);
break;
case 4:
printf("Front element: %d\n", front(queue));
break;
case 5:
printf("Exiting...\n");
exit(0);
default:
printf("Invalid choice\n");
}
} while (choice != 5);
return 0;
}

OUTPUT:
Enter the capacity of the circular queue: 6
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 23
23 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 43
43 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1

P BHANU PRAKASH 9551234604 [email protected] 66

 Enter element to enqueue: 54
54 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 35
35 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 34
34 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 345
345 enqueued to the circular queue
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 1
Enter element to enqueue: 23
Circular Queue Overflow
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 2
Dequeued element: 23

P BHANU PRAKASH 9551234604 [email protected] 67

 Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 3
Circular Queue elements: 43 54 35 34 345
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 4
Front element: 43
Circular Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Front
5. Exit
Enter your choice: 5
Exiting...

P BHANU PRAKASH 9551234604 [email protected] 68

Exercise 7: Stack and Queue Applications
i) Use a stack to evaluate an infix expression and convert it to postfix.
ii) Create a program to determine whether a given string is a palindrome or not.
iii) Implement a stack or queue to perform comparison and check for symmetry.

i.Use a stack to evaluate an infix expression and convert it to postfix

//evaluation of infix expression
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
// Structure to represent a stack node
struct StackNode
{
int data;
struct StackNode* next;
};
// Function to create a new stack node
struct StackNode* createNode(int data)
{
struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to check if the stack is empty
int isEmpty(struct StackNode* top)
{
return top == NULL;
}
// Function to push an element onto the stack
void push(struct StackNode** top, int data)
{
struct StackNode* newNode = createNode(data);
newNode->next = *top;
*top = newNode;
}
// Function to pop an element from the stack
int pop(struct StackNode** top)
{
if (isEmpty(*top))
{

P BHANU PRAKASH 9551234604 [email protected] 69

 printf("Stack underflow!\n");
exit(1);
}
struct StackNode* temp = *top;
int data = temp->data;
*top = (*top)->next;
free(temp);
return data;
}
// Function to return the top element of the stack without removing it
int peek(struct StackNode* top)
{
if (isEmpty(top))
{
printf("Stack is empty!\n");
exit(1);
}
return top->data;
}
// Function to determine the precedence of an operator
int precedence(char op)
{
switch (op)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return -1;
}
}
// Function to perform an operation between two operands and an operator
int applyOperation(int a, int b, char op)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':

P BHANU PRAKASH 9551234604 [email protected] 70

 if (b == 0)
{
printf("Division by zero error!\n");
exit(1);
}
return a / b;
default:
printf("Invalid operator!\n");
exit(1);
}
}
// Function to evaluate an infix expression
int evaluateInfix(char* infix)
{
struct StackNode* operandStack = NULL;
struct StackNode* operatorStack = NULL;
int i = 0;
while (infix[i] != '\0')
{
if (isdigit(infix[i]))
{
// If the current character is a digit, parse the operand and push it onto the operand stack
int operand = 0;
while (isdigit(infix[i]))
{
operand = operand * 10 + (infix[i] - '0');
i++;
}
push(&operandStack, operand);
}
else if (infix[i] == '(')
{
// If the current character is an opening parenthesis, push it onto the operator stack
push(&operatorStack, infix[i]);
i++;
}
else if (infix[i] == ')')
{
// If the current character is a closing parenthesis, evaluate the expressions until the corresponding
opening parenthesis is found
while (!isEmpty(operatorStack) && peek(operatorStack) != '(')
{
int operand2 = pop(&operandStack);
int operand1 = pop(&operandStack);
char op = pop(&operatorStack);
int result = applyOperation(operand1, operand2, op);

P BHANU PRAKASH 9551234604 [email protected] 71

 push(&operandStack, result);
}
if (!isEmpty(operatorStack) && peek(operatorStack) == '(')
{
pop(&operatorStack); // Discard the opening parenthesis
}
else
{
printf("Mismatched parentheses!\n");
exit(1);
}
i++;
}
else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/')
{
// If the current character is an operator, evaluate higher precedence operators and push the current
operator onto the operator stack
while (!isEmpty(operatorStack) && precedence(infix[i]) <=
precedence(peek(operatorStack)))
{
int operand2 = pop(&operandStack);
int operand1 = pop(&operandStack);
char op = pop(&operatorStack);
int result = applyOperation(operand1, operand2, op);
push(&operandStack, result);
}
push(&operatorStack, infix[i]);
i++;
}
else
{
// Ignore whitespace characters
i++;
}
}
// Evaluate any remaining operators
while (!isEmpty(operatorStack))
{
int operand2 = pop(&operandStack);
int operand1 = pop(&operandStack);
char op = pop(&operatorStack);
int result = applyOperation(operand1, operand2, op);
push(&operandStack, result);
}
// The final result will be at the top of the operand stack
return pop(&operandStack);

P BHANU PRAKASH 9551234604 [email protected] 72

 }
int main()
{
char infix[100];
printf("Enter the infix expression: ");
scanf("%[^\n]", infix);
int result = evaluateInfix(infix);
printf("Result of evaluation: %d\n", result);
return 0;
}

OUTPUT:
Enter the infix expression: (5 + 3) * 4 - 2 / (1 + 3)
Result of evaluation: 32

//convert infix to postfix

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

// Function to determine the precedence of an operator

int precedence(char op)
{
switch (op)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return -1;
}
}
// Function to convert infix expression to postfix
void infixToPostfix(char* infix, char* postfix)
{
char stack[100]; // Stack to store operators
int top = -1; // Pointer to the top of the stack
int i = 0, j = 0;
while (infix[i] != '\0')
{
if (isdigit(infix[i]))
{
// If the current character is a digit, add it to the postfix expression

P BHANU PRAKASH 9551234604 [email protected] 73

 postfix[j++] = infix[i++];
}
else if (infix[i] == '(')
{
// If the current character is an opening parenthesis, push it onto the stack
stack[++top] = infix[i++];
}
else if (infix[i] == ')')
{
// If the current character is a closing parenthesis, pop operators from the stack and add them to the
postfix expression until an opening parenthesis is encountered
while (top != -1 && stack[top] != '(')
{
postfix[j++] = stack[top--];
}
if (top == -1) {
printf("Invalid expression!\n");
exit(1);
}
top--; // Pop the opening parenthesis from the stack
i++;
}
else
{
// If the current character is an operator, pop operators from the stack and add
them to the postfix expression until an operator with lower precedence or an opening
parenthesis is encountered
while (top != -1 && precedence(infix[i]) <= precedence(stack[top])) {
postfix[j++] = stack[top--];
}
stack[++top] = infix[i++];
}
}
// Pop any remaining operators from the stack and add them to the postfix expression
while (top != -1)
{
if (stack[top] == '(')
{
printf("Invalid expression!\n");
exit(1);
}
postfix[j++] = stack[top--];
}
postfix[j] = '\0'; // Null-terminate the postfix expression
}
int main()

P BHANU PRAKASH 9551234604 [email protected] 74

 {
char infix[100], postfix[100];
printf("Enter the infix expression: ");
scanf("%[^\n]", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}

OUTPUT:
Enter the infix expression: (5+3)*4-2/(1+3)
Postfix expression: 53+4*213+/-

ii.Create a program to determine whether a given string is a palindrome or not.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
// Function to check whether a given string is a palindrome or not
bool isPalindrome(char* str)
{
int left = 0;
int right = strlen(str) - 1;
while (left < right) {
// Ignore non-alphanumeric characters from the left
while (!isalnum(str[left]) && left < right)
{
left++;
}
// Ignore non-alphanumeric characters from the right
while (!isalnum(str[right]) && left < right)
{
right--;
}
// If characters at current positions don't match, return false
if (tolower(str[left]) != tolower(str[right])) {
return false;
}
left++;
right--;
}
// If the loop completes without returning false, the string is a palindrome
return true;
}
int main()
{

P BHANU PRAKASH 9551234604 [email protected] 75

 char str[100];
printf("Enter a string: ");
fgets(str, sizeof(str), stdin);
// Remove the newline character from the end of the string
str[strcspn(str, "\n")] = '\0';
if (isPalindrome(str))
{
printf("The string \"%s\" is a palindrome.\n", str);
} else {
printf("The string \"%s\" is not a palindrome.\n", str);
}
return 0;
}

OUTPUT
Enter a string: program
The string "program" is not a palindrome.

Enter a string: malayalam

The string "malayalam" is a palindrome.

iii.Implement a stack or queue to perform comparison and check for symmetry.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
// Structure to represent a stack node
struct StackNode
{
char data;
struct StackNode* next;
};
// Function to create a new stack node
struct StackNode* createNode(char data)
{
struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;

P BHANU PRAKASH 9551234604 [email protected] 76

 }
// Function to check if the stack is empty
bool isEmpty(struct StackNode* top)
{
return top == NULL;
}
// Function to push an element onto the stack
void push(struct StackNode** top, char data)
{
struct StackNode* newNode = createNode(data);
newNode->next = *top;
*top = newNode;
}
// Function to pop an element from the stack
char pop(struct StackNode** top)
{
if (isEmpty(*top))
{
printf("Stack underflow!\n");
exit(1);
}
struct StackNode* temp = *top;
char data = temp->data;
*top = (*top)->next;
free(temp);
return data;
}
// Function to determine whether a given string is symmetric using a stack
bool isSymmetric(char* str)
{
struct StackNode* stack = NULL;
int length = strlen(str);
int i;
// Push the first half of the string onto the stack
for (i = 0; i < length / 2; i++)
{
push(&stack, str[i]);
}
// If the length of the string is odd, skip the middle character
if (length % 2 != 0) {
i++;
}
// Compare the second half of the string with the elements popped from the stack
while (str[i] != '\0')
{
if (isEmpty(stack) || pop(&stack) != str[i])

P BHANU PRAKASH 9551234604 [email protected] 77

 {
return false;
}
i++;
}
return true;
}
int main() {
char str[MAX_SIZE];
printf("Enter a string: ");
fgets(str, sizeof(str), stdin);
// Remove the newline character from the end of the string
str[strcspn(str, "\n")] = '\0';
if (isSymmetric(str))
{
printf("The string \"%s\" is symmetric.\n", str);
}
else
{
printf("The string \"%s\" is not symmetric.\n", str);
}
return 0;
}
OUTPUT
Enter a string: program
The string "program" is not symmetric.
Enter a string: radar
The string "radar" is symmetric.

P BHANU PRAKASH 9551234604 [email protected] 78

Exercise 8: Binary Search Tree
i) Implementing a BST using Linked List.
ii) Traversing of BST.

i.Implementing a BST using Linked List.

#include <stdio.h>
#include <stdlib.h>
// Define the structure for each node in the Binary Search Tree
struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new tree node
struct TreeNode* createNode(int value)
{
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a value into the BST
struct TreeNode* insert(struct TreeNode* root, int value)
{
if (root == NULL)
{
return createNode(value);
}
if (value < root->data)
{
root->left = insert(root->left, value);
}
else if (value > root->data)
{
root->right = insert(root->right, value);
}
return root;
}
// Function to perform inorder traversal of the BST

P BHANU PRAKASH 9551234604 [email protected] 79

 void inorderTraversal(struct TreeNode* root)
{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Function to perform preorder traversal of the BST
void preorderTraversal(struct TreeNode* root)
{
if (root != NULL)
{
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// Function to perform postorder traversal of the BST
void postorderTraversal(struct TreeNode* root)
{
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
// Function to deallocate memory for the BST nodes
void deallocateBST(struct TreeNode* root)
{
if (root != NULL)
{
deallocateBST(root->left);
deallocateBST(root->right);
free(root);
}
}
int main()
{
// Initialize an empty tree
struct TreeNode* root = NULL;
// Number of nodes to be inserted
int n;
printf("Enter the number of nodes to be inserted: ");
scanf("%d", &n);

P BHANU PRAKASH 9551234604 [email protected] 80

 // Input nodes manually
printf("Enter %d elements to insert into BST:\n", n);
for (int i = 0; i < n; ++i)
{
int val;
printf("Node %d: ", i + 1);
scanf("%d", &val);
root = insert(root, val);
}
// Print the traversals of the BST
printf("Inorder traversal of the BST: ");
inorderTraversal(root);
printf("\n");
printf("Preorder traversal of the BST: ");
preorderTraversal(root);
printf("\n");
printf("Postorder traversal of the BST: ");
postorderTraversal(root);
printf("\n");
// Deallocate memory for the BST nodes
deallocateBST(root);
return 0;
}

OUTPUT:
Enter the number of nodes to be inserted: 5
Enter 5 elements to insert into BST
Node 1:30
Node 2:50
Node 3:60
Node 4:70
Node 5:27
Inorder traversal of the BST: 27 30 50 60 70
Preorder traversal of the BST: 30 27 50 60 70
Postorder traversal of the BST: 27 70 60 50 30

ii.Traversing of BST.
#include <stdio.h>
#include <stdlib.h>
// Define the structure for each node in the Binary Search Tree
struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
};

P BHANU PRAKASH 9551234604 [email protected] 81

 // Function to create a new tree node
struct TreeNode* createNode(int value)
{
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode == NULL)
{
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a value into the BST
struct TreeNode* insert(struct TreeNode* root, int value)
{
if (root == NULL)
{
return createNode(value);
}
if (value < root->data)
{
root->left = insert(root->left, value);
}
else if (value > root->data)
{
root->right = insert(root->right, value);
}
return root;
}
// Function to perform inorder traversal of the BST (without using linked list)
void inorderTraversal(struct TreeNode* root)
{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Function to free memory allocated for the BST
void freeBST(struct TreeNode* root)
{
if (root != NULL)
{

P BHANU PRAKASH 9551234604 [email protected] 82

 freeBST(root->left);
freeBST(root->right);
free(root);
}
}
int main()
{
// Initialize an empty tree
struct TreeNode* root = NULL;
// Number of nodes to be inserted
int n;
printf("Enter the number of nodes to be inserted: ");
scanf("%d", &n);
// Input nodes manually
printf("Enter %d elements to insert into BST:\n", n);
for (int i = 0; i < n; ++i)
{
int val;
printf("Node %d: ", i + 1);
scanf("%d", &val);
root = insert(root, val);
}
// Print inorder traversal of the BST
printf("\nInorder traversal of the BST: ");
inorderTraversal(root);
printf("\n");
// Free allocated memory
freeBST(root);
return 0;
}
OUTPUT
Enter the number of nodes to be inserted: 3
Enter 5 elements to insert into BST
Node 1:56
Node 2:3
Node 3:59
Inorder traversal of the BST: 3 59 56

P BHANU PRAKASH 9551234604 [email protected] 83

Exercise 9: Hashing
i) Implement a hash table with collision resolution techniques.
ii) Write a program to implement a simple cache using hashing.

i.Implement a hash table with collision resolution techniques.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10
// Define a structure for a node in the hash table (used for separate chaining)
struct Node
{
int key;
char *value;
struct Node *next;
};
// Define a structure for the hash table
struct HashTable {
struct Node *table[SIZE];
};
// Function to create a new node
struct Node *createNode(int key, char *value)
{
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed.\n");
exit(1);
}
newNode->key = key;
newNode->value = strdup(value); // strdup dynamically allocates memory for the string
newNode->next = NULL;
return newNode;
}
// Function to initialize the hash table
void initHashTable(struct HashTable *hashTable)
{
for (int i = 0; i < SIZE; i++)
{
hashTable->table[i] = NULL;
}
}
// Function to calculate the hash value
int hash(int key)
{
return key % SIZE;

P BHANU PRAKASH 9551234604 [email protected] 84

 }
// Function to insert a key-value pair into the hash table
void insert(struct HashTable *hashTable, int key, char *value)
{
int index = hash(key);
struct Node *newNode = createNode(key, value);
// If the slot is empty, insert the new node
if (hashTable->table[index] == NULL)
{
hashTable->table[index] = newNode;
}
else
{
// If there is already a node at the slot, append the new node to the end of the linked
list
struct Node *temp = hashTable->table[index];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Function to search for a key in the hash table
char *search(struct HashTable *hashTable, int key)
{
int index = hash(key);
struct Node *temp = hashTable->table[index];
// Traverse the linked list at the index to find the key
while (temp != NULL)
{
if (temp->key == key)
{
return temp->value;
}
temp = temp->next;
}
return NULL; // Key not found
}
int main()
{
struct HashTable hashTable;
initHashTable(&hashTable);
int n;
printf("Enter the number of key-value pairs to insert: ");
scanf("%d", &n);

P BHANU PRAKASH 9551234604 [email protected] 85

 printf("Enter %d key-value pairs (key value):\n", n);
for (int i = 0; i < n; ++i)
{
int key;
char value[100];
printf("Pair %d: ", i + 1);
scanf("%d %s", &key, value);
insert(&hashTable, key, value);
}
// Search for a key
int searchKey;
printf("\nEnter the key to search: ");
scanf("%d", &searchKey);
char *result = search(&hashTable, searchKey);
if (result != NULL) {
printf("Value for key %d: %s\n", searchKey, result);
}
else
{
printf("Key %d not found.\n", searchKey);
}
// Free allocated memory for string values
for (int i = 0; i < SIZE; i++)
{
struct Node *temp = hashTable.table[i];
while (temp != NULL)
{
struct Node *toFree = temp;
temp = temp->next;
free(toFree->value); // Free dynamically allocated string
free(toFree);
}
}
return 0;
}
OUTPUT
Enter the number of key-value pairs to insert: 2 Enter 2 key-value pairs (key value):
Pair 1: 35
Pair 2: 56
Enter the key to search: 5 Value for key 5: 6

ii.Write a program to implement simple cache using hashing

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define CACHE_SIZE 10

P BHANU PRAKASH 9551234604 [email protected] 86

 // Define a structure for a cache entry
struct CacheEntry
{
int key;
char *value;
struct CacheEntry *next;
};
// Define a structure for the cache
struct Cache
{
struct CacheEntry *table[CACHE_SIZE];
};
// Function to create a new cache entry
struct CacheEntry *createCacheEntry(int key, char *value)
{
struct CacheEntry *newEntry = (struct CacheEntry *)malloc(sizeof(struct CacheEntry));
if (newEntry == NULL)
{
printf("Memory allocation failed.\n");
exit(1);
}
newEntry->key = key;
newEntry->value = strdup(value); // strdup dynamically allocates memory for the string
newEntry->next = NULL;
return newEntry;
}
// Function to initialize the cache
void initCache(struct Cache *cache)
{
for (int i = 0; i < CACHE_SIZE; i++) {
cache->table[i] = NULL;
}
}
// Function to calculate the hash value
int hash(int key)
{
return key % CACHE_SIZE;
}
// Function to insert a key-value pair into the cache
void insert(struct Cache *cache, int key, char *value)
{
int index = hash(key);
struct CacheEntry *newEntry = createCacheEntry(key, value);
// If the slot is empty, insert the new entry
if (cache->table[index] == NULL)
{

P BHANU PRAKASH 9551234604 [email protected] 87

 cache->table[index] = newEntry;
}
else
{
// If there is already an entry at the slot, append the new entry to the end of the linked list
struct CacheEntry *temp = cache->table[index];
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newEntry;
}
}
// Function to search for a key in the cache
char *search(struct Cache *cache, int key)
{
int index = hash(key);
struct CacheEntry *temp = cache->table[index];
// Traverse the linked list at the index to find the key
while (temp != NULL)
{
if (temp->key == key)
{
return temp->value;
}
temp = temp->next;
}
return NULL; // Key not found
}
int main()
{
struct Cache cache;
initCache(&cache);
int n;
printf("Enter the number of key-value pairs to insert into the cache: ");
scanf("%d", &n);
printf("Enter %d key-value pairs (key value):\n", n);
for (int i = 0; i < n; ++i)
{
int key;
char value[100];
printf("Pair %d: ", i + 1);
scanf("%d %s", &key, value);
insert(&cache, key, value);
}
// Search for a key in the cache

P BHANU PRAKASH 9551234604 [email protected] 88

 int searchKey;
printf("\nEnter the key to search in the cache: ");
scanf("%d", &searchKey);
char *result = search(&cache, searchKey);
if (result != NULL)
{
printf("Value for key %d in the cache: %s\n", searchKey, result);
}
else
{
printf("Key %d not found in the cache.\n", searchKey);
}
// Free allocated memory for string values
for (int i = 0; i < CACHE_SIZE; i++)
{
struct CacheEntry *temp = cache.table[i];
while (temp != NULL)
{
struct CacheEntry *toFree = temp;
temp = temp->next;
free(toFree->value); // Free dynamically allocated string
free(toFree);
}
}

return 0;
}

OUTPUT
Enter the number of key-value pairs to insert into the cache: 2
Enter 2 key-value pairs (key value):
Pair 1: 57
Pair 2: 89
Enter the key to search in the cache: 8
Value for key 8 in the cache: 9

P BHANU PRAKASH 9551234604 [email protected] 89