Data Structures Laboratory Name :- Anshu Kumari

Subject code: UGCA- 1918 iRoll.No: 3122/22

12. Program to concatenate and compare two strings using user defined
function.

#include <iostream>
using namespace std;
int main() {
string str1, str2, result;
int i;
cout << " Enter the first string: ";
cin >> str1;
cout << " Enter the second string: ";
cin >> str2;
for (i = 0; i < str1.size(); i++) {
result = result + str1[i];
}
for (i = 0; i < str2.size(); i++) {
result = result + str2[i];
}
cout << " The Concatenation of the string " << str1 << " and " << str2
<< " is " << result;
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

13. Program for using the concept of pointer to string.

#include <cstring>
#include <iostream>
using namespace std;
int main() {
const char* originalString = "Hello, Pointers to Strings!";
cout << "Original String: " << originalString << endl;
int length = strlen(originalString);
const char* stringPointer = originalString;
cout << "String using Pointer: ";
for (int i = 0; i < length; ++i) {
cout << *(stringPointer + i);
}
cout << endl;
cout << "Uppercase String: ";
for (int i = 0; i < length; ++i) {
cout << (char)toupper(*(stringPointer + i));
}
cout << endl;
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

14. Program to reverse a sentence by recursion.

#include <iostream>
using namespace std;
void reverse(char *str) {
if (*str == '\0')
return;
else {
reverse(str + 1);
cout << *str;
}
}
int main() {
char str[] = "C++ is fun";
cout << "Original String: " << str << endl;
cout << "Reversed String: ";
reverse(str);
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

15. Program to delete all repeated words in string.

#include <bits/stdc++.h>
using namespace std;
char *removeDuplicate(char str[], int n) {
int index = 0;
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < i; j++)
if (str[i] == str[j]) break;
if (j == i) str[index++] = str[i];
}
return str;
}
int main() {
char str[] =
"aaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbcccccccccccccccccdddddddddddddddeeeeee"
"eeee";
int n = sizeof(str) / sizeof(str[0]);
cout << removeDuplicate(str, n);
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

16. Program to find the number of vowels, consonants, digits and white space
in a string.

#include <iostream>
using namespace std;
int main() {
char str[] = {"My name is anshu chy 47"};
int vowels, consonants, digits, spaces;
vowels = consonants = digits = spaces = 0;
for (int i = 0; str[i] != '\0'; ++i) {
if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' ||
str[i] == 'u' || str[i] == 'A' || str[i] == 'E' || str[i] == 'I' ||
str[i] == 'O' || str[i] == 'U') {
++vowels;
} else if ((str[i] >= 'a' && str[i] <= 'z') ||
(str[i] >= 'A' && str[i] <= 'Z')) {
++consonants;
} else if (str[i] >= '0' && str[i] <= '9') {
++digits;
} else if (str[i] == ' ') {
++spaces;
}
}
cout << "The string is: " << str << endl;
cout << "Vowels: " << vowels << endl;
cout << "Consonants: " << consonants << endl;
cout << "Digits: " << digits << endl;
cout << "White spaces: " << spaces << endl;
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

17. Program to find the length of the longest repeating sequence in a string.

#include <cstring>
#include <iostream>
using namespace std;
int longestRepeatingSequenceLength(const char str[]) {
int n = strlen(str);
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++) dp[i][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (str[i - 1] == str[j - 1] && i != j)
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[n][n];
}
int main() {
char inputString[100];
cout << "Enter the string: ";
cin.getline(inputString, 100);
int length = longestRepeatingSequenceLength(inputString);
cout << "Length of the longest repeating sequence: " << length << endl;
return 0;
}

Output
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

18. Program to find highest and lowest frequency character in a string.

#include <cctype>
#include <climits>
#include <iostream>
using namespace std;
const int CHAR_COUNT = 256;
void findFrequency(const string& str) {
int frequencyMap[CHAR_COUNT] = {0};
for (char ch : str) {
if (isalpha(ch)) {
frequencyMap[ch]++;
}
}
char highestChar = '\0';
char lowestChar = '\0';
int highestFrequency = 0;
int lowestFrequency = INT_MAX;
for (int i = 0; i < CHAR_COUNT; ++i) {
if (frequencyMap[i] > highestFrequency) {
highestChar = static_cast<char>(i);
highestFrequency = frequencyMap[i];
}
if (frequencyMap[i] > 0 && frequencyMap[i] < lowestFrequency) {
lowestChar = static_cast<char>(i);
lowestFrequency = frequencyMap[i];
}
}
if (highestFrequency > 0) {
cout << "Highest Frequency Character: " << highestChar
<< " (Frequency: " << highestFrequency << ")" << endl;
} else {
cout << "No valid characters in the input string." << endl;
}
if (lowestFrequency != INT_MAX) {
cout << "Lowest Frequency Character: " << lowestChar
<< " (Frequency: " << lowestFrequency << ")" << endl;
} else {
cout << "No valid characters in the input string." << endl;
}
}
int main() {
string inputString;
cout << "Enter a string: ";
getline(cin, inputString);
findFrequency(inputString);
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

19. Program for implementing Stack using array.

#include <iostream>
#define MAX 5
using namespace std;
int STACK[MAX], TOP;
void initStack() { TOP = -1; }
int isEmpty() {
if (TOP == -1)
return 1;
else
return 0;
}
int isFull() {
if (TOP == MAX - 1)
return 1;
else
return 0;
}
void push(int num) {
if (isFull()) {
cout << "STACK is FULL." << endl;
return;
}
++TOP;
STACK[TOP] = num;
cout << num << " has been inserted." << endl;
}
void display() {
int i;
if (isEmpty()) {
cout << "STACK is EMPTY." << endl;
return;
}
for (i = TOP; i >= 0; i--) {
cout << STACK[i] << " ";
}
cout << endl;
}
void pop() {
int temp;
if (isEmpty()) {
cout << "STACK is EMPTY." << endl;
return;
}
temp = STACK[TOP];
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
TOP--;
cout << temp << " has been deleted." << endl;
}
int main() {
int num;
initStack();
char ch;
do {
int a;
cout << "Chosse \n1.push\n"
<< "2.pop\n"
<< "3.display\n";
cout << "Please enter your choice: ";
cin >> a;
switch (a) {
case 1:
cout << "Enter an Integer Number: ";
cin >> num;
push(num);
break;
case 2:
pop();
break;
case 3:
display();
break;
default:
cout << "An Invalid Choice!!!\n";
}
cout << "Do you want to continue ? ";
cin >> ch;
} while (ch == 'Y' || ch == 'y');
return 0;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

20. Program for implementing Stack using pointer.

#include <stdlib.h>
#include <iostream>
#define MAX_SIZE 3
using namespace std;
void push(int value);
void pop();
void display();
int choice, value;
int *tos, *p1, arr_stack[MAX_SIZE];
int exit_p = 1;
int main() {
tos = arr_stack;
p1 = arr_stack;
do {
cout << "\n\nStack Pointer: Main Menu";
cout << "\n1. Push \t2. Pop \t3. Display \t4. Exit";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value: ";
cin >> value;
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit_p = 0;
break;
default:
cout << "\nInvalid choice. Please enter a valid option.";
break;
}
} while (exit_p);
return 0;
}
void push(int value) {
if (p1 == (tos + MAX_SIZE)) {
cout << "\nStatus: Stack Overflow. Cannot push " << value << ".";
} else {
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
*p1 = value;
cout << "\nPushed value: " << *p1;
p1++;
}
}
void pop() {
if (p1 == tos) {
cout << "\nStatus: Stack Underflow. Cannot pop.";
} else {
p1--;
cout << "\nPopped value: " << *p1;
}
}
void display() {
if (p1 == tos) {
cout << "\nStatus: Stack is empty.";
} else {
cout << "\nStack elements: ";
for (int *ptr = tos; ptr < p1; ++ptr) {
cout << *ptr << " ";
}
}
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

21. Program for implementing multiple stack.

#include <climits>
#include <iostream>
using namespace std;
class TwoStacks {
private:
int* arr;
int size;
int top1;
int top2;
public:
TwoStacks(int n) {
size = n;
arr = new int[n];
top1 = -1;
top2 = size;
}
void push1(int value) {
if (top1 < top2 - 1) {
arr[++top1] = value;
cout << "Pushed into Stack 1: " << value << endl;
} else {
cout << "Stack Overflow: Cannot push into Stack 1." << endl;
}
}
void push2(int value) {
if (top1 < top2 - 1) {
arr[--top2] = value;
cout << "Pushed into Stack 2: " << value << endl;
} else {
cout << "Stack Overflow: Cannot push into Stack 2." << endl;
}
}
void pop1() {
if (top1 >= 0) {
cout << "Popped from Stack 1: " << arr[top1--] << endl;
} else {
cout << "Stack 1 Underflow: Cannot pop from an empty stack." << endl;
}
}
void pop2() {
if (top2 < size) {
cout << "Popped from Stack 2: " << arr[top2++] << endl;
} else {
cout << "Stack 2 Underflow: Cannot pop from an empty stack." << endl;
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
}
}
void displayStacks() {
cout << "Stack 1: ";
for (int i = 0; i <= top1; ++i) {
cout << arr[i] << " ";
}
cout << "\nStack 2: ";
for (int i = size - 1; i >= top2; --i) {
cout << arr[i] << " ";
}
cout << endl;
}
~TwoStacks() { delete[] arr; }
};
int main() {
TwoStacks twoStacks(6);
twoStacks.push1(1);
twoStacks.push1(2);
twoStacks.push2(3);
twoStacks.push2(4);
twoStacks.displayStacks();
twoStacks.pop1();
twoStacks.pop2();
twoStacks.displayStacks();
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

22. Program for converting infix to postfix form.

#include <iostream>
using namespace std;
char stack[20];
int top = -1;
class infix_to_postfix {
public:
void push(char x) { stack[++top] = x; }
char pop() {
if (top == -1) {
return -1;
} else {
return stack[top--];
}
}
int priority(char x) {
if (x == '(') return 0;
if (x == '+' || x == '-') return 1;
if (x == '*' || x == '/') return 2;
}
};
int main() {
infix_to_postfix obj;
char exp[20];
char *e, x;
cout << "enter the infix expression:";
cin >> exp;
e = exp;
cout << "postfix expression is:";
while (*e != '\0') {
if (isalnum(*e))
cout << *e;
else if (*e == '(')
obj.push(*e);
else if (*e == ')') {
while ((x = obj.pop()) != '(') cout << x;
} else {
while (obj.priority(stack[top]) >= obj.priority(*e)) cout << obj.pop();
obj.push(*e);
}
e++;
}
while (top != -1) {
cout << obj.pop();
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

23. Program for implementing Queue using array.

#include <iostream>
using namespace std;
int queue[100], n = 100, front = -1, rear = -1;
void Insert() {
int val;
if (rear == n - 1)
cout << "Queue Overflow" << endl;
else {
if (front == -1) front = 0;
cout << "Insert the element in queue : " << endl;
cin >> val;
rear++;
queue[rear] = val;
}
}
void Delete() {
if (front == -1 || front > rear) {
cout << "Queue Underflow ";
return;
} else {
cout << "Element deleted from queue is : " << queue[front] << endl;
front++;
;
}
}
void Display() {
if (front == -1)
cout << "Queue is empty" << endl;
else {
cout << "Queue elements are : ";
for (int i = front; i <= rear; i++) cout << queue[i] << " ";
cout << endl;
}
}
int main() {
int ch;
cout << "1) Insert element to queue" << endl;
cout << "2) Delete element from queue" << endl;
cout << "3) Display all the elements of queue" << endl;
cout << "4) Exit" << endl;
do {
cout << "Enter your choice : " << endl;
cin >> ch;
switch (ch) {
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
case 1:
Insert();
break;
case 2:
Delete();
break;
case 3:
Display();
break;
case 4:
cout << "Exit" << endl;
break;
default:
cout << "Invalid choice" << endl;
}
} while (ch != 4);
return 0;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

24. Program for dynamic implementation of queue.

#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
bool isEmpty() { return front == nullptr; }
void enqueue(int value) {
Node* newNode = new Node{value, nullptr};
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
cout << value << " enqueued to the queue." << endl;
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
} else {
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
cout << temp->data << " dequeued from the queue." << endl;
delete temp;
}
}
void display() {
if (isEmpty()) {
cout << "Queue is empty." << endl;
} else {
cout << "Queue elements: ";
Node* current = front;
while (current != nullptr) {
cout << current->data << " ";
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
current = current->next;
}
cout << endl;
}
}
~Queue() {
while (!isEmpty()) {
dequeue();
}
}
};
int main() {
Queue myQueue;
myQueue.enqueue(10);
myQueue.enqueue(20);
myQueue.enqueue(30);
myQueue.display();
myQueue.dequeue();
myQueue.dequeue();
myQueue.display();
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

25. Program for implementing circular queue.

#include <iostream>
using namespace std;
int cqueue[5];
int front = -1, rear = -1, n = 5;
void insertCQ(int val) {
if ((front == 0 && rear == n - 1) || (front == rear + 1)) {
cout << "Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val;
}
void deleteCQ() {
if (front == -1) {
cout << "Queue Underflow\n";
return;
}
cout << "Element deleted from queue is : " << cqueue[front] << endl;
if (front == rear) {
front = -1;
rear = -1;
} else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements are :\n";
if (f <= r) {
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
while (f <= r) {
cout << cqueue[f] << " ";
f++;
}
} else {
while (f <= n - 1) {
cout << cqueue[f] << " ";
f++;
}
f = 0;
while (f <= r) {
cout << cqueue[f] << " ";
f++;
}
}
cout << endl;
}
int main() {
int ch, val;
cout << "1)Insert\n";
cout << "2)Delete\n";
cout << "3)Display\n";
cout << "4)Exit\n";
do {
cout << "Enter choice : " << endl;
cin >> ch;
switch (ch) {
case 1:
cout << "Input for insertion: " << endl;
cin >> val;
insertCQ(val);
break;
case 2:
deleteCQ();
break;
case 3:
displayCQ();
break;
case 4:
cout << "Exit\n";
break;
default:
cout << "Incorrect!\n";
}
} while (ch != 4);
return 0;
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

26. Program for implementing dequeue

#include <iostream>
using namespace std;
#define SIZE 10
class Dequeue {
int a[SIZE];
int front, rear;
public:
Dequeue();
void insertAtBeginning(int);
void insertAtEnd(int);
void deleteFromFront();
void deleteFromRear();
void show();
};
Dequeue::Dequeue() {
front = -1;
rear = -1;
}
void Dequeue::insertAtEnd(int i) {
if (rear >= SIZE - 1) {
cout << "\nInsertion is not possible, overflow!!!!";
} else {
if (front == -1) {
front++;
rear++;
} else {
rear = rear + 1;
}
a[rear] = i;
cout << "\nInserted item is " << a[rear];
}
}
void Dequeue::insertAtBeginning(int i) {
if (front == -1) {
front = 0;
a[++rear] = i;
cout << "\nInserted element is: " << i;
} else if (front != 0) {
a[--front] = i;
cout << "\nInserted element is: " << i;
} else {
cout << "\nInsertion is not possible, overflow!!!";
}
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
void Dequeue::deleteFromFront() {
if (front == -1) {
cout << "Deletion is not possible: Dequeue is empty";
} else {
cout << "The deleted element is: " << a[front];
if (front == rear) {
front = rear = -1;
} else {
front = front + 1;
}
}
}
void Dequeue::deleteFromRear() {
if (front == -1) {
cout << "Deletion is not possible: Dequeue is empty";
} else {
cout << "The deleted element is: " << a[rear];
if (front == rear) {
front = rear = -1;
} else {
rear = rear - 1;
}
}
}
void Dequeue::show() {
if (front == -1) {
cout << "Dequeue is empty";
} else {
for (int i = front; i <= rear; i++) {
cout << a[i] << " ";
}
}
}
int main() {
int choice, item;
Dequeue d;
do {
cout << "\n1. Insert at Beginning";
cout << "\n2. Insert at End";
cout << "\n3. Show";
cout << "\n4. Delete from Front";
cout << "\n5. Delete from Rear";
cout << "\n6. Exit";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
case 1:
cout << "Enter the element to be inserted: ";
cin >> item;
d.insertAtBeginning(item);
break;
case 2:
cout << "Enter the element to be inserted: ";
cin >> item;
d.insertAtEnd(item);
break;
case 3:
d.show();
break;
case 4:
d.deleteFromFront();
break;
case 5:
d.deleteFromRear();
break;
case 6:
exit(1);
break;
default:
cout << "Invalid choice";
break;
}
} while (choice != 6);
return 0;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

27. Program for implementing dequeue

#include <iostream>
using namespace std;
struct Node {
int priority;
int data;
Node* next;
};
class PriorityQueue {
private:
Node* front;
public:
PriorityQueue() : front(nullptr) {}
void insert(int data, int priority) {
Node* newNode = new Node{priority, data, nullptr};
if (front == nullptr || priority < front->priority) {
newNode->next = front;
front = newNode;
} else {
Node* temp = front;
while (temp->next != nullptr && temp->next->priority <= priority) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
void remove() {
if (front == nullptr) {
cout << "Queue Underflow\n";
} else {
Node* temp = front;
cout << "Deleted item is: " << temp->data << endl;
front = front->next;
delete temp;
}
}
void display() {
if (front == nullptr) {
cout << "Queue is empty\n";
} else {
cout << "Queue is:\n";
cout << "Priority\tItem\n";
Node* temp = front;
while (temp != nullptr) {
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
cout << temp->priority << "\t\t" << temp->data << endl;
temp = temp->next;
}
}
}
};
int main() {
int choice, item, priority;
PriorityQueue pq;
do {
cout << "1. Insert\n";
cout << "2. Delete\n";
cout << "3. Display\n";
cout << "4. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter item value to be added in the queue: ";
cin >> item;
cout << "Enter its priority: ";
cin >> priority;
pq.insert(item, priority);
break;
case 2:
pq.remove();
break;
case 3:
pq.display();
break;
case 4:
break;
default:
cout << "Invalid choice\n";
}
} while (choice != 4);
return 0;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

28. Program for implementing Singly Linked list.

#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = nullptr;
void insert(int new_data) { head = new Node{new_data, head}; }
void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
}
int main() {
int value, n;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; ++i) {
cin >> value;
insert(value);
}
cout << "The linked list is: ";
display();
return 0;
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

29. Program for implementing Doubly Linked list.

#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head = nullptr;
void insert(int new_data) {
Node* new_node = new Node{new_data, nullptr, head};
if (head != nullptr) {
head->prev = new_node;
}
head = new_node;
}
void display() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
}
int main() {
int n, value;
cout << "Enter the number of elements: ";
cin >> n;
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; ++i) {
cin >> value;
insert(value);
}
cout << "The doubly linked list is: ";
display();
return 0;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

30. Program for implementing Binary Search Tree

#include <cstdlib>
#include <iostream>
using namespace std;
struct node {
int info;
struct node *left;
struct node *right;
} * root;
class BST {
public:
void find(int, node **, node **);
void insert(node *, node *);
void del(int);
void case_a(node *, node *);
void case_b(node *, node *);
void case_c(node *, node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST() { root = NULL; }
};
int main() {
int choice, num;
BST bst;
node *temp;
while (1) {
cout << " ---------------- " << endl;
cout << "Operations on BST" << endl;
cout << " ---------------- " << endl;
cout << "1.Insert Element " << endl;
cout << "2.Delete Element " << endl;
cout << "3.Inorder Traversal" << endl;
cout << "4.Preorder Traversal" << endl;
cout << "5.Postorder Traversal" << endl;
cout << "6.Display" << endl;
cout << "7.Quit" << endl;
cout << "Enter your choice : ";
cin >> choice;
switch (choice) {
case 1:
temp = new node;
cout << "Enter the number to be inserted : ";
cin >> temp->info;
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
bst.insert(root, temp);
case 2:
if (root == NULL) {
cout << "Tree is empty, nothing to delete" << endl;
continue;
}
cout << "Enter the number to be deleted : ";
cin >> num;
bst.del(num);
break;
case 3:
cout << "Inorder Traversal of BST:" << endl;
bst.inorder(root);
cout << endl;
break;
case 4:
cout << "Preorder Traversal of BST:" << endl;
bst.preorder(root);
cout << endl;
break;
case 5:
cout << "Postorder Traversal of BST:" << endl;
bst.postorder(root);
cout << endl;
break;
case 6:
cout << "Display BST:" << endl;
bst.display(root, 1);
cout << endl;
break;
case 7:
exit(1);
default:
cout << "Wrong choice" << endl;
}
}
}
void BST::find(int item, node **par, node **loc) {
node *ptr, *ptrsave;
if (root == NULL) {
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info) {
*loc = root;
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL) {
if (item == ptr->info) {
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
void BST::insert(node *tree, node *newnode) {
if (root == NULL) {
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (tree->info == newnode->info) {
cout << "Element already in the tree" << endl;
return;
}
if (tree->info > newnode->info) {
if (tree->left != NULL) {
insert(tree->left, newnode);
} else {
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout << "Node Added To Left" << endl;
return;
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
} else {
if (tree->right != NULL) {
insert(tree->right, newnode);
} else {
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
void BST::del(int item) {
node *parent, *location;
if (root == NULL) {
cout << "Tree empty" << endl;
return;
}
find(item, &parent, &location);
if (location == NULL) {
cout << "Item not present in tree" << endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
void BST::case_a(node *par, node *loc) {
if (par == NULL) {
root = NULL;
} else {
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
void BST::case_b(node *par, node *loc) {
node *child;
if (loc->left != NULL)
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
child = loc->left;
else
child = loc->right;
if (par == NULL) {
root = child;
} else {
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
void BST::case_c(node *par, node *loc) {
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL) {
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL) {
root = suc;
} else {
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
void BST::preorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
preorder(ptr->left);
preorder(ptr->right);
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
}
}
void BST::inorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
inorder(ptr->left);
cout << ptr->info << " ";
inorder(ptr->right);
}
}
void BST::postorder(node *ptr) {
if (root == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
postorder(ptr->left);
postorder(ptr->right);
cout << ptr->info << " ";
}
}
void BST::display(node *ptr, int level) {
int i;
if (ptr != NULL) {
display(ptr->right, level + 1);
cout << endl;
if (ptr == root)
cout << "Root->: ";
else {
for (i = 0; i < level; i++) cout << " ";
}
cout << ptr->info;
display(ptr->left, level + 1);
}
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

31. Program for Breadth First Search (BFS) for graph traversal.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
vector<bool> v;
vector<vector<int>> g;
void bfsTraversal(int b) {
queue<int> q;
q.push(b);
v[b] = true;
cout << "\n\nThe BFS Traversal is: ";
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto j = g[a].begin(); j != g[a].end(); j++) {
if (!v[*j]) {
v[*j] = true;
q.push(*j);
}
}
cout << a << " ";
}
}
void makeEdge(int a, int b) { g[a].push_back(b); }
int main() {
int n, e;
cout << "Enter the number of vertices: ";
cin >> n;
cout << "\n\nEnter the number of edges: ";
cin >> e;
v.assign(n, false);
g.assign(n, vector<int>());
int a, b, i;
cout << "Enter the edges with source and target vetex: \n ";
for (i = 0; i < e; i++) {
cin >> a >> b;
makeEdge(a, b);
}
for (i = 0; i < n; i++) {
if (!v[i]) {
bfsTraversal(i);
}
}
cout << "\n\n\n";
return 0;
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
}

Output:
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22

32. Program for Depth First Search (DFS) for graph traversal.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<bool> v;
vector<vector<int>> g;
void dfsTraversal(int startVertex) {
stack<int> dfsStack;
dfsStack.push(startVertex);
v[startVertex] = true;
cout << "\n\nThe DFS Traversal is: ";
while (!dfsStack.empty()) {
int currentVertex = dfsStack.top();
dfsStack.pop();
cout << currentVertex << " ";
for (int neighbor : g[currentVertex]) {
if (!v[neighbor]) {
v[neighbor] = true;
dfsStack.push(neighbor);
}
}
}
cout << endl;
}
void makeEdge(int a, int b) { g[a].push_back(b); }
int main() {
int n, e;
cout << "Enter the number of vertices: ";
cin >> n;
cout << "\n\nEnter the number of edges: ";
cin >> e;
v.assign(n, false);
g.assign(n, vector<int>());
int a, b, i;
cout << "Enter the edges with source and target vertex: \n ";
for (i = 0; i < e; i++) {
cin >> a >> b;
makeEdge(a, b);
}
for (i = 0; i < n; i++) {
if (!v[i]) {
dfsTraversal(i);
}
}
Data Structures Laboratory Name :- Anshu Kumari
Subject code: UGCA- 1918 iRoll.No: 3122/22
cout << "\n\n\n";
return 0;
}

Output: