DATA STRUCTURES PRACTICAL

FILE (INITC201)

SEMESTER -2
ITNS
Group-1
 BY -
AVANI AGNIHOTRI
2023UIN2527
PROBLEM-1 :
Write a program to implement two stacks in an array.

CODE –
/ Program to implement two stacks in an
array #include <iostream>

#include <stdlib.h>

using namespace std;

class twoStacks {

int* ar;

int size;

int top1, top2;

public:

twoStacks(int n)

size = n;

ar = new int[n];

top1 = -1;

top2 = size;

void push1(int x)

if (top1 < top2 - 1) {

top1++;

ar[top1] = x;
 }

else {

cout << "Stack Overflow";

exit(1);

void push2(int x)

if (top1 < top2 - 1) {

top2--;

ar[top2] = x;

else {

cout << "Stack Overflow";

exit(1);

int pop1()

if (top1 >= 0) {

int x = ar[top1];

top1--;

return x;

else {

cout << "Stack UnderFlow";

 exit(1);

}
 }

int pop2()

if (top2 < size) {

int x = ar[top2];

top2++;

return x;

else {

cout << "Stack UnderFlow";

exit(1);

};

int main()

twoStacks ts(5);

ts.push1(5);

ts.push2(10);

ts.push2(16);

ts.push1(13);

ts.push2(6);

cout << "Popped element from stack1 is "

< ts.pop1();

ts.push2(12);

cout << "\nPopped element from stack2 is "

 < ts.pop2();

return 0;

}
OUTPUT –

PROBLEM-2:
Write a program to implement stack using Linked List.

CODE -
#include <iostream>

#include <stdlib.h>

using namespace std;

struct node

int data;

node* next;

};

struct node* head = NULL;

void push(int x)

node* temp;

temp = new node();

temp->data = x;

temp->next = head;
 head = temp;

}
bool isEmpty()

if (head == NULL)

return true;

else

return false;

int top_element()

if (head == NULL)

cout << "stack is empty" << endl;

else

return head->data;

void pop()

node* temp;

if (isEmpty())

cout << "stack is empty" << endl;

}
else

{
 temp = head;

head = head->next;

delete(temp);

void print_stack()

struct node* curr;

if (isEmpty())

cout << "stack is empty" << endl;

else

curr = head;

cout << "Elements are: ";

while (curr != NULL)

cout << curr->data << " ";

curr = curr->next;

cout << endl;

}
int main()
{

push(5);

push(3);

push(6);

print_stack();

isEmpty();

cout << "Top: "

<< top_element() << endl;

pop();

print_stack();

cout << "Top: "

< top_element() <<

endl; return 0;

OUTPUT –
PROBLEM-3 :
Write a program to convert an infix expression to post fix and evaluate the post
fix expression using stack.
CODE –
#include <iostream>

#include <stdlib.h>

using namespace std;

/ Function to return precedence of operators

int prec(char c) {

if (c == '^')
return 3;

else if (c == '/' || c ==
'*') return 2;

else if (c == '+' || c == '-')

return 1;

else return
-1;

/ Function to return associativity of operators

char associativity(char c) {

if (c == '^')
return 'R';
return 'L'; // Default to left-associative
}

/ The main function to convert infix expression

/ to postfix expression
void infixToPostfix(string s) {

stack<char> st;
string result;

for (int i = 0; i < s.length(); i++) {

char c = s[i];

/ If the scanned character is

/ an operand, add it to the output string.
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;

/ If the scanned character is an

/ ‘(‘, push it to the stack.

else if (c == '(')

st.push('(');
 / If the scanned character is an ‘)’,

/ pop and add to the output string from the stack

/ until an ‘(‘ is encountered.

else if (c == ')') {
while (st.top() != '(') {

result += st.top();
st.pop();

}
st.pop(); // Pop '('

/ If an operator is
scanned else {

while (!st.empty() && prec(s[i]) < prec(st.top()) || !

st.empty() && prec(s[i]) == prec(st.top()) &&
associativity(s[i]) == 'L') {

result += st.top();
st.pop();

st.push(c);
}

/ Pop all the remaining elements from the stack

while (!st.empty()) {

result += st.top();
st.pop();

cout << result << endl;

}

/ Driver code
int main() {
string exp = "a+b*(c^d-e)^(f+g*h)-i";

/ Function call
infixToPostfix(exp);

return 0;
}

OUTPUT –
PROBLEM-4:
Write a program to implement queue using array.

CODE –
#include <iostream>

#include <stdlib.h>

using namespace std;

struct Queue {

int front, rear, capacity;

int* queue;

Queue(int c)

front = rear = 0;

capacity = c;

queue = new int;

~Queue() { delete[] queue; }

/ function to insert an element

/ at the rear of the queue

void queueEnqueue(int data)

/ check queue is full or

not if (capacity == rear) {

printf("\nQueue is full\
n"); return;
}

// insert element at the rear

 else {

queue[rear] = data;

rear++;

return;

/ function to delete an element

/ from the front of the

queue void queueDequeue()

/ if queue is empty

if (front == rear) {

printf("\nQueue is empty\n");

return;

/ shift all the elements from index 2 till rear

/ to the left by one

else {

for (int i = 0; i < rear - 1; i++) {

queue[i] = queue[i + 1];

/ decrement
rear rear--;

}
 return;

}
 / print queue elements
void queueDisplay()

int i;

if (front == rear) { printf("\

nQueue is Empty\n"); return;

/ traverse front to rear and print

elements for (i = front; i < rear; i++) {

printf(" %d <-- ", queue[i]);

return;

/ print front of queue

void queueFront()

if (front == rear) { printf("\

nQueue is Empty\n"); return;

printf("\nFront Element is: %d",

queue[front]); return;

};
/ Driver code
int main(void)
{

/ Create a queue of capacity 4

Queue q(4);

/ print Queue elements

q.queueDisplay();

/ inserting elements in the queue

q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);

/ print Queue elements

q.queueDisplay();

/ insert element in the queue

q.queueEnqueue(60);

/ print Queue elements

q.queueDisplay();

q.queueDequeue();

q.queueDequeue();

printf("\n\nafter two node deletion\n\n");

/ print Queue elements

q.queueDisplay();
 / print front of the queue
q.queueFront();

return 0;

OUTPUT –

PROBLEM-5:
Write a program to implement priority queue using linked list.

CODE –
#include <iostream>

#include <stdlib.h>

using namespace std;

// Node

typedef struct node

int data;
/ Lower values indicate

/ higher priority

int priority;
 struct node* next;

} Node;

/ Function to create a new node

Node* newNode(int d, int p)

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = d;

temp->priority = p;
temp->next = NULL;

return temp;

/ Return the value at head

int peek(Node** head)

return (*head)->data;

/ Removes the element with the

/ highest priority from the

list void pop(Node** head)

{
 Node* temp = *head;
(*head) = (*head)->next;
free(temp);

}
/ Function to push according to priority
void push(Node** head, int d, int p)

Node* start = (*head);

// Create new Node

Node* temp = newNode(d, p);

/ Special Case: The head of list has

/ lesser priority than new node. So

/ insert newnode before head node

/ and change head node.

if ((*head)->priority > p)

/ Insert New Node before

head temp->next = *head;
(*head) = temp;

else

/ Traverse the list and find a

/ position to insert new node

while (start->next != NULL &&

start->next->priority < p)

{
 start = start->next;

}
 / Either at the ends of the list

/ or at required position
temp->next = start->next;
start->next = temp;

/ Function to check is list is

empty int isEmpty(Node** head)

return (*head) == NULL;

/ Driver code

int main()

/ Create a Priority Queue

/ 7->4->5->6

Node* pq = newNode(4, 1);

push(&pq, 5, 2);

push(&pq, 6, 3);

push(&pq, 7, 0);

while (!isEmpty(&pq))

cout << " " << peek(&pq);

pop(&pq);
 }

return 0;

}
OUTPUT –

PROBLEM-6:
Write a program to display a singly linked list in reverse order.

CODE –
#include <iostream>

#include <stdlib.h>

using namespace std;

struct Node {

int data;

struct Node* next;

Node(int data) {

this->data = data;

next = NULL;

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/ Function to print linked

list void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous
pointer while(curr) {

auto temp = curr -> next;

 curr -> next = prev;

prev = curr;

head = prev;

curr = temp;

void print() {

struct Node* temp = head;

while (temp != NULL) {

cout << temp->data << " ";

temp = temp->next;

void push(int data) {

Node* temp = new Node(data);

temp->next = head;

head = temp;

};

int main() {

LinkedList list;

list.push(20);

list.push(4);

list.push(15);

list.push(85);

list.print();

list.reverse();

cout << "\n";

 list.print();

}
OUTPUT –

PROBLEM-7:
Write a program to remove duplicates in a singly linked list.

CODE –
#include <bits/stdc++.h>

using namespace std;

struct Node {

int data;

struct Node* next;

};

/ Utility function to create a new

Node struct Node* newNode(int data)

Node* temp = new Node;

temp->data = data; temp-
>next = NULL; return
temp;

void removeDuplicates(struct Node* start)

{
struct Node *ptr1, *ptr2, *dup;
ptr1 = start;

while (ptr1 != NULL && ptr1->next != NULL) {

 ptr2 = ptr1;

while (ptr2->next != NULL) {

/* If duplicate then delete it */

if (ptr1->data == ptr2->next->data) {

/* sequence of steps is important here */

dup = ptr2->next;

ptr2->next = ptr2->next->next;

delete (dup);

ptr2 = ptr2->next;

ptr1 = ptr1->next;

void printList(struct Node* node)

while (node != NULL) {

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

node = node->next;

/ Driver code
int main()

struct Node* start = newNode(10); start-

>next = newNode(12); start->next->next
= newNode(11); start->next->next->next
= newNode(11);
 start->next->next->next->next = newNode(12); start->next-
>next->next->next->next = newNode(11); start->next-
>next->next->next->next->next = newNode(10);

printf("Linked list before removing duplicates ");

printList(start);

removeDuplicates(start);

printf("\nLinked list after removing duplicates ");

printList(start);

return 0;

OUTPUT –
Q10

#include <stdio.h>
#include <limits.h>
#include <iostream>

using namespace std;

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;

return min_index;
}

// A utility function to print the constructed MST stored in parent[]

int printMST(int parent[], int n, int graph[V][V])
{
cout<<"Edge Weight\n";
for (int i = 1; i < V; i++)
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
}

// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
bool mstSet[V]; // To represent set of vertices not yet included in MST

// Initialize all keys as INFINITE

for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.

key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < V - 1; count++)
{
// Pick thd minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of the adjacent vertices of

// the picked vertex. Consider only those vertices which are not yet
// included in MST
for (int v = 0; v < V; v++)

// graph[u][v] is non zero only for adjacent vertices of m

// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
 parent[v] = u, key[v] = graph[u][v];
}

// print the constructed MST

printMST(parent, V, graph);
}

// driver program to test above function

int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| /\ |
6| 8/ \5 |7
|/ \|
(3)-------(4)
9 */
int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 }, };

// Print the solution

primMST(graph);

return 0;
}

Q11
// C++ Implementation of the Quick Sort Algorithm.
#include <iostream>
using namespace std;

int partition(int arr[], int start, int end)

{

int pivot = arr[start];

int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
 }

// Giving pivot element its correct position

int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);

// Sorting left and right parts of the pivot element

int i = start, j = end;

while (i < pivotIndex && j > pivotIndex) {

while (arr[i] <= pivot) {

i++;
}

while (arr[j] > pivot) {

j--;
}

if (i < pivotIndex && j > pivotIndex) {

swap(arr[i++], arr[j--]);
}
}

return pivotIndex;
}

void quickSort(int arr[], int start, int end)

{

// base case
if (start >= end)
return;

// partitioning the array

int p = partition(arr, start, end);

// Sorting the left part

quickSort(arr, start, p - 1);

// Sorting the right part

quickSort(arr, p + 1, end);
}

int main()
{
 int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}

return 0;
}

Q12
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root Since we are using 0 based indexing
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// main function to do heap sort

void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

/* A utility function to print array of size n */

void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver program
int main()
{
int arr[] = { 60 ,20 ,40 ,70, 30, 10};
int n = sizeof(arr) / sizeof(arr[0]);
//heapify algorithm
// the loop must go reverse you will get after analyzing manually
// (i=n/2 -1) because other nodes/ ele's are leaf nodes
// (i=n/2 -1) for 0 based indexing
// (i=n/2) for 1 based indexing
for(int i=n/2 -1;i>=0;i--){
heapify(arr,n,i);
}

cout << "After heapifying array is \n";

printArray(arr, n);

heapSort(arr, n);

cout << "Sorted array is \n";

 printArray(arr, n);

return 0;
}