INDRAPRASTHA COLLEGE FOR WOMEN

DATA STRUCTURE

PRACTICAL FILE

SUBMITTED BY: SIMRAN VISHISHT

SUBMITTED TO: Dr. Archana Singhal
ROLL NO: 21/CS/48
SEMESTER: III
Course: B.Sc(Hons) Computer Science
1. Given a list of N elements, which follows no particular arrangement, you are required to search an
element x in the list. The list is stored using array data structure. If the search is successful, the
output should be the index at which the element occurs, otherwise returns -1 to indicate that the
element is not present in the list. Assume that the elements of the list are all distinct. Write a program
to perform the desired task.
Answer:
#include<iostream>
using namespace std;
int main()
{

int size,i,tosearch,found;
cout<<("Enter size of array:");
cin>>size;
int arr[size];

for(i=0;i<size;i++)
{
cout<<("Enter elements in array:");
int num;
cin>>num;
arr[i]=num;
}
cout<<("Enter element to search:");
cin>>tosearch;
found=0;
for(i=0;i<size;i++)
{
if(arr[i]==tosearch)
{
found=1;
break;
}
}
if(found==1)
{
cout<<tosearch<<" is found at "<<i+1;
}
else
{
cout<<"not found";
}
}

Output:
2. Given a list of N elements, which is sorted in ascending order, you are required to search an
element x in the list. The list is stored using array data structure. If the search is successful, the
output should be the index at which the element occurs, otherwise returns -1 to indicate that the
element is not present in the list. Assume that the elements of the list are all distinct. Write a program
to perform the desired task.
Answer:
#include<iostream>
using namespace std;
int binarysearch(int array[],int low,int high,int x)
{
if(low<high)
{
int mid=(low+high)/2;
if(array[mid]==x)
{
return mid;
}
if(array[mid]<x)
{
return binarysearch(array,mid+1,high,x);
}
else
{
return binarysearch(array,low,mid-1,x);
}
}
}

int main()
{
int size,i,tosearch,found;
cout<<("Enter size of array:");
cin>>size;
int arr[size];

for(i=0;i<size;i++)
{
cout<<("Enter elements in array:");
int num;
cin>>num;
arr[i]=num;
}
cout<<("Enter element to search:");
cin>>tosearch;
int result=binarysearch(arr,0,size-1,tosearch);
cout<<"Element found at index "<<result;
}

Output:

3. Write a program to implement singly linked list which supports the following operations:
(i) Insert an element x at the beginning of the singly linked list
(ii) Insert an element x at position in the singly linked list
(iii)Remove an element from the beginning of the singly linked list
(iv) Remove an element from position in the singly linked list.
(v) Search for an element x in the singly linked list and return its pointer
(vi) Concatenate two singly linked lists
Answer:
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node(int d)
{
this->data=d;
this->next=NULL;
}
~Node()
{
if(this->next!=NULL)
{
delete next;
this->next=NULL;
}
}
};
void insertathead(Node* &tail,Node* &head,int d)
{
Node* temp=new Node(d);
if(head==NULL)
{
head=temp;
tail=temp;
}
else{
temp->next=head;
head=temp;
}

}
void insertatTail(Node* &tail,int d)
{
Node* temp=new Node(d);
tail->next=temp;
tail=temp;
}

void insertatpos(Node* &tail,Node* &head,int d,int pos)

{
if(pos==1)
{
insertathead(tail,head,d);
return;

}
int cnt=1;
Node* temp=head;
while(cnt<pos-1)
{
temp=temp->next;
cnt++;

}
if(temp->next==NULL)
{
insertatTail(tail,d);
return;
}
Node* nodetoinsert=new Node(d);
nodetoinsert->next=temp->next;
temp->next=nodetoinsert;
}
void print(Node* &head)
{
Node* temp=head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
void deletestart(Node* &head)
{
Node* temp=head;
head=head->next;
temp->next=NULL;
delete temp;
}
void deletepos(Node* &head,int pos)
{
if(pos==1)
{
deletestart(head);
}
else
{
Node* curr=head;
Node* prev=NULL;
int cnt=1;
while(cnt<pos)
{
prev=curr;
curr=curr->next;
cnt++;
}
prev->next=curr->next;
curr->next=NULL;
delete curr;
}
}
void merge(Node* &tail1,Node* &head1,Node* &tail2,Node* &head2)
{
Node* temp=head1;

while(temp->next!=0)
{
temp=temp->next;
}
temp->next=head2;
head2=head1;
tail1=tail2;

}
Node* search(Node* head, int x)
{
Node* current = head; // Initialize current
int pos=1;
while (current != NULL)
{
if(current->data==x)
{
cout<<"Element found at position: "<<pos<<endl;
return current;
}
current = current->next;
pos++;
}
return 0;
}
int main()
{
Node* head=NULL;
Node* tail=NULL;
int i=0;
int choice=0;
do{

cout<<"MENU"<<endl;
cout<<"1.Insert at head"<<endl;
cout<<"2.Insert at position"<<endl;
cout<<"3.Print"<<endl;
cout<<"4.Enter to delete starting element of the list"<<endl;

cout<<"5.Enter to delete element at the position"<<endl;

cout<<"6.Enter to search element"<<endl;
cout<<"7.Enter to concatenate"<<endl;
cout<<"8.Exit"<<endl;
cout<<"Enter your choice"<<endl;
cin>>choice;
if(choice==1)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
insertathead(tail,head,data);
}
else if(choice==2)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
int pos;
cout<<"Enter the position";
cin>>pos;
insertatpos(tail,head,data,pos);
}
else if(choice==3)
{
print(head);
}
else if(choice==4)
{
cout<<"List after deletion"<<endl;
deletestart(head);
print(head);
}
else if(choice==5)
{
int pos;
cout<<"Enter position:";
cin>>pos;
cout<<"List after deletion from position "<<endl;
deletepos(head,pos);
print(head);
}
else if(choice==6)
{
cout<<"Enter the element you want to search :";
int a;
cin>>a;
Node* result=search(head,a);
cout<<result<<endl;
}
else if(choice==7)
{
Node* head1=NULL;
Node* tail1=NULL;
cout<<"Creation of first linked list: ";
insertathead(tail1,head1,24);
insertathead(tail1,head1,27);
insertathead(tail1,head1,30);
insertathead(tail1,head1,32);
cout<<"The first linked list is: ";
print(head1);
Node* head2=NULL;
Node* tail2=NULL;
cout<<"Creation of second linked list: ";
insertathead(tail2,head2,56);
insertathead(tail2,head2,57);
insertathead(tail2,head2,40);
insertathead(tail2,head2,59);
print(head2);
cout<<"The second linked list is: ";
print(head2);
cout<<"Merging the two lists"<<endl;
merge(tail1,head1,tail2,head2);
print(head1);
}
else if(choice==8)
{
break;
}
else{
cout<<"Incorrect choice"<<endl;
}
}while(choice!=10);

Output:

4. Write a program to implement doubly linked list which supports the following operations:
(i) Insert an element x at the beginning of the doubly linked list
(ii) Insert an element x at position in the doubly linked list
(iii)Insert an element x at the end of the doubly linked list
(iv) Remove an element from the beginning of the doubly linked list
(v) Remove an element from position in the doubly linked list.
(vi) Remove an element from the end of the doubly linked list
(vii) Search for an element x in the doubly linked list and return its pointer
(viii) Concatenate two doubly linked lists
Answer:
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node* prev;
Node(int data)
{
this->data=data;
this->next=NULL;
this->prev=NULL;
}
~Node()
{
if(this->next!=NULL)
{
delete next;
this->next=NULL;
this->prev=NULL;
}
}
};
void insertathead(Node* &tail,Node* &head,int d)
{
Node* temp=new Node(d);
if(head==NULL)
{
head=temp;
tail=temp;
}
else{
temp->next=head;
head->prev=temp;
head=temp;
}
}
void insertattail(Node* &tail,Node* &head,int d)
{
Node* temp=new Node(d);
if(tail==NULL)
{
head=temp;
tail=temp;
}
else{

tail->next=temp;
temp->prev=tail;
tail=temp;
}
}
void print(Node* &head)
{
Node* temp=head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
void insertatpos(Node* &tail,Node* &head,int d,int pos)
{
if(pos==1)
{
insertathead(tail,head,d);
return;

}
int cnt=1;
Node* temp=head;
while(cnt<pos-1)
{
temp=temp->next;
cnt++;

}
if(temp->next==NULL)
{
insertattail(tail,head,d);
return;
}
Node* nodetoinsert=new Node(d);
nodetoinsert->next=temp->next;
temp->next->prev=nodetoinsert;
temp->next=nodetoinsert;
nodetoinsert->prev=temp;
}
void deletestart(Node* &head)
{
Node* temp=head;
temp->next->prev=NULL;
head=temp->next;
temp->next=NULL;
delete temp;
}
void deletepos(Node* &head,int pos)
{
if(pos==1)
{
deletestart(head);

}
else{
Node* curr=head;
Node* prev=NULL;
int count=1;
while(count<pos)
{
prev=curr;
curr=curr->next;
count++;
}
curr->prev=NULL;
prev->next=curr->next;

curr->next->prev=prev;
curr->next=NULL;
delete curr;
}
}
void deleteend(Node* &tail)
{
Node *temp=tail;
tail->prev->next=NULL;
tail=tail->prev;
temp->prev=NULL;
delete temp;

}
void merge(Node* &tail1,Node* &head1,Node* &tail2,Node* &head2)
{
Node* temp=head1;

while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=head2;
head2->prev=temp;
head2=head1;
tail1=tail2;
}
Node* search(Node* head, int x)
{
Node* current = head; // Initialize current
int pos=1;
while (current != NULL)
{
if(current->data==x)
{
cout<<"Element found at position: "<<pos<<endl;
return current;
}
current = current->next;
pos++;
}
return 0;
}

int main()
{
Node* head=NULL;
Node* tail=NULL;
int i=0;
int choice=0;
do{

cout<<"MENU"<<endl;
cout<<"1.Insert at head"<<endl;
cout<<"2.Insert at position"<<endl;
cout<<"3.Print"<<endl;
cout<<"4.Insert at tail"<<endl;
cout<<"5.Enter to delete starting element of the list"<<endl;

cout<<"6.Enter to delete element at the position"<<endl;

cout<<"7.Enter to delete element from last"<<endl;
cout<<"8.Enter to search"<<endl;
cout<<"9.Enter to concatenate"<<endl;
cout<<"10.Exit"<<endl;
cout<<"Enter your choice"<<endl;
cin>>choice;
if(choice==1)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
insertathead(tail,head,data);
}
else if(choice==2)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
int pos;
cout<<"Enter the position";
cin>>pos;
insertatpos(tail,head,data,pos);
}
else if(choice==3)
{
print(head);
}
else if(choice==4)
{
int data;
cout<<"Enter the data which you want to insert in tail"<<endl;
cin>>data;
insertattail(tail,head,data);
}
else if(choice==5)
{
cout<<"List after deletion"<<endl;
deletestart(head);
print(head);
}
else if(choice==6)
{
int pos;
cout<<"Enter position:";
cin>>pos;
cout<<"List after deletion from position "<<endl;
deletepos(head,pos);
print(head);
}
else if(choice==7)
{
cout<<"List after deletion"<<endl;
deleteend(tail);
print(head);
}
else if(choice==8)
{
cout<<"Enter the element you want to search :";
int a;
cin>>a;
Node* result=search(head,a);
cout<<result<<endl;
}
else if(choice==9)
{
Node* head1=NULL;
Node* tail1=NULL;
cout<<"Creation of first linked list: ";
insertathead(tail1,head1,24);
insertathead(tail1,head1,27);
insertathead(tail1,head1,30);
insertathead(tail1,head1,32);
cout<<"The first linked list is: ";
print(head1);
Node* head2=NULL;
Node* tail2=NULL;
cout<<"Creation of second linked list: ";
insertathead(tail2,head2,56);
insertathead(tail2,head2,57);
insertathead(tail2,head2,40);
insertathead(tail2,head2,59);
print(head2);
cout<<"The second linked list is: ";
print(head2);
cout<<"Merging the two lists"<<endl;
merge(tail1,head1,tail2,head2);
print(head1);
}
else if(choice==10)
{
break;
}
else
{
cout<<"Wrong choice"<<endl;
}
}while(choice!=10);
}
Output:

5. Write a program to implement circularly linked list which supports the following operations:
(i) Insert an element x at the front of the circularly linked list
(ii) Insert an element x after an element y in the circularly linked list
(iii)Insert an element x at the back of the circularly linked list
(iv) Remove an element from the back of the circularly linked list
(v) Remove an element from the front of the circularly linked list
(vi) remove the element x from the circularly linked list
(vii)Search for an element x in the circularly linked list and return its pointer
(viii) Concatenate two circularly linked lists
Answer:
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int data)
{
this->data=data;
this->next=NULL;
}
~Node()
{
if(this->next!=NULL)
{
delete next;
this->next=NULL;

}
}
};
void insertathead(Node* &tail,Node* &head,int d)
{
Node* newNode=new Node(d);
if(head==NULL)
{
head=newNode;
tail=newNode;
}
else
{
tail->next=newNode;
newNode->next=head;
head=newNode;
}

}
void insertatposele(Node* &tail,Node* &head,int ele,int d)
{

if(head==NULL)
{
Node* newNode=new Node(d);
head=newNode;
tail=newNode;
tail->next=tail;
}
else{
Node* curr=head;
while(curr->data!=ele)
{
curr=curr->next;
}
Node* temp=new Node(d);
temp->next=curr->next;
curr->next=temp;
}
}
void insertattail(Node* &tail,Node* &head,int d)
{
Node* newNode=new Node(d);
if(tail==NULL)
{
head=newNode;
tail=newNode;
}
else{
tail->next=newNode;
newNode->next=head;
tail=newNode;
}
}
void print(Node* &head)
{

Node* temp=head;
do
{
cout<<temp->data<<" ";
temp=temp->next;
}while(temp!=head);
cout<<endl;
}
void deleteend(Node* &tail,Node* &head)
{
Node *temp=head;

while(temp->next->next!=head)
{
temp=temp->next;
}
temp->next=head;
tail=temp;
}

void deletestart(Node* &tail,Node* &head)

{
Node* temp=head;
tail->next=head->next;
head=head->next;
temp->next=NULL;
delete temp;
}

void deleteele(Node* &tail,Node* &head,int ele)

{
if(head->data==ele)
{
deletestart(tail,head);
}
else{
Node* curr=head;
Node* prev=NULL;

while(curr->data!=ele)
{
prev=curr;
curr=curr->next;
}
if(curr->next==head)
{
deleteend(tail,head);
}
else{
prev->next=curr->next;
curr->next=NULL;
delete curr;
}
}
}

void merge(Node* &tail1,Node* &head1,Node* &tail2,Node* &head2)

{
Node* temp=head1;

while(temp->next!=head1)
{
temp=temp->next;
}
temp->next=head2;
tail2->next=head1;
}
Node* search(Node* head, int x)
{
Node* current = head; // Initialize current
int pos=1;
while (current->next!=head)
{
if(current->data==x)
{
cout<<"Element found at position: "<<pos<<endl;
return current;
}
current = current->next;
pos++;
}
return 0;
}

int main()
{
Node* head=NULL;
Node* tail=NULL;
int i=0;
int choice=0;
do{

cout<<"MENU"<<endl;
cout<<"1.Insert at head"<<endl;
cout<<"2.Insert at specified position after element"<<endl;
cout<<"3.Print"<<endl;
cout<<"4.Insert at tail"<<endl;
cout<<"5.Enter to delete starting element of the list"<<endl;

cout<<"6.Enter to delete the element "<<endl;

cout<<"7.Enter to delete element from last"<<endl;
cout<<"8.Enter to search"<<endl;
cout<<"9.Enter to concatenate"<<endl;
cout<<"10.Exit"<<endl;
cout<<"Enter your choice"<<endl;
cin>>choice;
if(choice==1)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
insertathead(tail,head,data);
}
else if(choice==2)
{
int data;
cout<<"Enter the data which you want to insert"<<endl;
cin>>data;
int ele;
cout<<"Enter the element after which you want to enter";
cin>>ele;
insertatposele(tail,head,ele,data);
}
else if(choice==3)
{
print(head);
}
else if(choice==4)
{
int data;
cout<<"Enter the data which you want to insert in tail"<<endl;
cin>>data;
insertattail(tail,head,data);
}
else if(choice==5)
{
cout<<"List after deletion"<<endl;
deletestart(tail,head);
print(head);
}

else if(choice==6)
{
int ele;
cout<<"Enter element:";
cin>>ele;
cout<<"List after deletion from position "<<endl;
deleteele(tail,head,ele);
print(head);
}
else if(choice==7)
{
cout<<"List after deletion"<<endl;
deleteend(tail,head);
print(head);
}
else if(choice==8)
{
cout<<"Enter the element you want to search :";
int a;
cin>>a;
Node* result=search(head,a);
cout<<result<<endl;
}
else if(choice==9)
{
Node* head1=NULL;
Node* tail1=NULL;
cout<<"Creation of first linked list: ";
insertathead(tail1,head1,24);
insertathead(tail1,head1,27);
insertathead(tail1,head1,30);
insertathead(tail1,head1,32);
cout<<"The first linked list is: ";
print(head1);
Node* head2=NULL;
Node* tail2=NULL;
cout<<"Creation of second linked list: ";
insertathead(tail2,head2,56);
insertathead(tail2,head2,57);
insertathead(tail2,head2,40);
insertathead(tail2,head2,59);
cout<<"The second linked list is: ";
print(head2);
cout<<"Merging the two lists"<<endl;
merge(tail1,head1,tail2,head2);
print(head1);
}
else if(choice==10)
{
break;
}
else
{
cout<<"Wrong choice"<<endl;
}
}while(choice!=10);
}

Output:
6. Implement a stack using Array representation
Answer:
#include<iostream>
using namespace std;

class stackk
{
int arr[50];
int size;
int count;
public:
stackk()
{
count=-1;
}
int push(int n);
int print();
int pop();

};
int stackk::print()
{
int i;
cout<<"Stack is: ";
for(i=count;i>=0;i--)
{
cout<<arr[i]<<" ";

}
cout<<endl;
}
int stackk::push(int n)
{
if(count==(size-1))
{
cout<<"Array is full"<<endl;
}
else
{
++count;
arr[count]=n;
return n;
}
}
int stackk::pop()
{
int n;
if(count==-1)
{
cout<<"Array is empty"<<endl;
}
else
{
n=arr[count--];
cout<<"Deleted element is: "<<n;
}
}
int main()
{
stackk s;
int i=0;
int choice=0;
do{

cout<<"MENU"<<endl;
cout<<"1.Insetion"<<endl;
cout<<"2.Print"<<endl;
cout<<"3.Delete"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice"<<endl;
cin>>choice;
if(choice==1)
{
int data;
cout<<"Enter data: ";
cin>>data;
s.push(data);
}
if(choice==2)
{

s.print();
}
if(choice==3)
{

s.pop();
}
}while(choice!=4);

Output:
7. Implement a stack using Linked representation
Answer:
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node* next;
Node(int data)
{
this->data=data;
this->next=NULL;
}
};
class Stack {
Node* top;

public:

Stack()
{
top = NULL;
}

void push(int data)

{
Node* temp = new Node(data);
if (!temp) {
cout << "\nStack Overflow";
}
else{
temp->data=data;
temp->next= top;
top= temp;
}
}

void pop()
{
Node* temp;
if (top== NULL) {
cout << "\nStack Underflow" << endl;
}
else {
temp = top;

top=top->next;
delete(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;

// Check for stack underflow

if (top == NULL) {
cout << "\nStack Underflow";

}
else {
temp = top;
while (temp != NULL) {

// Print node data

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

// Assign temp link to temp

temp = temp->next;
if (temp != NULL)
cout << " -> ";
}
}
}

};

// Driven Program
int main()
{
// Creating a stack
Stack s;

// Push the elements of stack

s.push(11);
s.push(22);
s.push(33);
s.push(44);

s.display();
cout<<endl;
s.pop();
s.pop();
cout<<"After Popping:"<<endl;
s.display();
return 0;
}

Output:
8. Implement Queue using Circular Array representation
Answer:
#include <iostream>
using namespace std;
#define SIZE 5
int A[SIZE];
int front = -1;
int rear = -1;
//Function to check if queue is empty or not
bool isempty()
{
if(front == -1 && rear == -1)
return true;
else
return false;
}

//function to enter elements in queue

void enqueue ( int value )
{
//queue is full
if ((rear + 1)%SIZE == front)
cout<<"Queue is full \n";
else
{
//first element inserted
if( front == -1)
front = 0;
//insert element at rear
rear = (rear+1)%SIZE;
A[rear] = value;
}
}

//function to delete/remove element from queue

void dequeue ( )
{
if( isempty() )
cout<<"Queue is empty\n";
else
//only one element
if( front == rear )
front = rear = -1;
else
front = (front + 1)%SIZE;
}

//function to show the element at front

void showfront( )
{
if( isempty())
cout<<"Queue is empty\n";
else
cout<<"element at front is:"<<A[front];
}

//function to display queue

void displayQueue()
{
if(isempty())
cout<<"Queue is empty\n";
else
{
int i;
if( front <= rear )
{
for( i=front ; i<= rear ; i++)
cout<<A[i]<<" ";
}
else
{
i=front;
while( i < SIZE)
{
cout<<A[i]<<" ";
i++;
}
i=0;
while( i <= rear)
{
cout<<A[i]<<" ";
i++;
}
}
}
}

//Main Function
int main()
{
int choice, flag=1, value;
while( flag == 1)
{
cout<<"\n1.enqueue 2.dequeue 3.showfront 4.displayQueue 5.exit\n";
cin>>choice;
switch (choice)
{
case 1: cout<<"Enter Value:\n";
cin>>value;
enqueue(value);
break;
case 2: dequeue();
break;
case 3: showfront();
break;
case 4: displayQueue();
break;
case 5: flag = 0;
break;
}
}

return 0;
}

Output:

9. Implement Queue using Circular linked list representation

Answer:
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

class Node
{
public:
int value;
Node *next;
Node(int a)
{
this->value=a;
this->next==NULL;}
};

class Queue
{
public:
Node *front,*back;
int size;
Queue()
{
front=NULL;
back=NULL;size=0;
}
void enqueue(int a)
{
cout<<"Pushing "<<a<<" to the Circular Queue"<<endl;
size++;
Node *temp= new Node(a);
if(front==NULL)
{
front =temp;
}
else back->next=temp;
back=temp; // back=back->next
back->next=front;
}
int dequeue()
{
if(front==NULL){
cout<<"The Circular queue is empty"<<endl;
return -1;
}
size--;
int a;
if(front==back)
{
a=front->value;
delete front;
front=back=NULL;
cout<<"Popping the top value "<<a<<" from the Circular Queue"<<endl;
return a;
}
Node *temp=front;
a=temp->value;
front=front->next;
back->next=front;
delete temp;
cout<<"Popping the top value "<<a<<"from the Circular Queue"<<endl;
return a;
}
void Show()
{
if(size==0) {cout<<"The Circular Queue is empty."<<endl;return;}
cout<<"The Queue is:";
Node *temp=front;
while(temp->next!=front)
{cout<<" "<<temp->value;temp=temp->next;}
cout<<" "<<temp->value;
cout<<endl;
cout<<back->next->value;
}

};

int main()
{
Queue q;
q.enqueue(3);
q.enqueue(5);
q.enqueue(2);
q.enqueue(5);
q.enqueue(6);
q.Show();
q.enqueue(7);q.dequeue();q.dequeue();
q.Show();
}

Output:

10. Implement Double-ended Queues using Linked list representation

Answer:
#include<iostream>
using namespace std;
struct Node
{
int value;
Node *prev, *next;
// prev and next pointers to point to the previous and next element in the deque.
};
// Function to create a new node in the deque or doubly-linked list.
Node* createnode(int value)
{
Node* newNode = new Node();
newNode->value = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

class Deque
{
Node* front;
Node* rear;
int Size;

public:
Deque()
{
front = rear = NULL;
Size = 0;
}

// Operations/Functionalities on Deque.
void insertFront(int value);
void insertRear(int value);
void deleteFront();
void deleteRear();
int getFront();
int getRear();
int size();
bool isEmpty();
};

// This function checks if the deque is empty.

bool Deque::isEmpty()
{
if(Size == 0){
return true;
}
return false;
}

// Function to return the size of the deque.

int Deque::size()
{
return Size;
}

// Function to insert an element at the beginning of the deque.

void Deque::insertFront(int value)
{
Node* newNode = createnode(value);
// If deque is empty then update the front and rear pointers.
if (front == NULL){
rear = front = newNode;
}
// Otherwise insert at the beginning of the deque according to the algorithm described
above.
else
{
newNode->next = front;
front->prev = newNode;
front = newNode;
}

// Increase the size of the queue by one.

Size++;
}

// Function to insert an element at the end of the deque.

void Deque::insertRear(int value)
{
Node* newNode = createnode(value);
// If deque is empty then update the front and rear pointers.
if (rear == NULL)
front = rear = newNode;
// Otherwise insert at the end of the deque according to the algorithm described
above.
else
{
newNode->prev = rear;
rear->next = newNode;
rear = newNode;
}

// Increase the size of the queue by one.

Size++;
}

// Function to delete the element from the front end of the deque.
void Deque::deleteFront()
{
// Check if the deque is empty.
if (isEmpty())
cout << "UnderFlow\n";

// Otherwise, delete the element at the beginning of the deque according to the
algorithm described above.
else
{
Node* temp = front;
front = front->next;
// If only one element was present in the deque.
if (front == NULL)
rear = NULL;
else
front->prev = NULL;
delete(temp);
// Decrease the size of the deque by one.
Size--;
}
}

// Function to delete the element from the rear end of the deque.
void Deque::deleteRear()
{
// Check if the deque is empty.
if (isEmpty())
cout << "UnderFlow\n";
// Otherwise delete the element at the end of the deque according to the algorithm
described above.
else
{
Node* temp = rear;
rear = rear->prev;
// If only one element was present in the deque.
if (rear == NULL)
front = NULL;
else
rear->next = NULL;
delete(temp);

// Decrease the size of the deque by one.

Size--;
}
}

// Function to return the element at the front of the deque.

int Deque::getFront()
{
// If deque is empty, then return garbage value.
if (isEmpty())
return -1; // garbage value
return front->value;
}

// Function to return the element at the back of the deque.

int Deque::getRear()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return rear->value;
}

int main(){

Deque deq;
// keep taking input till the user ends the program.
cout<<("To exit, Enter 9.\n");
cout<<"1.Insert at front"<<endl;
cout<<"1.Insert at end"<<endl;
cout<<"3.Delete Front"<<endl;
cout<<"4.Delete Rear"<<endl;
cout<<"5.Front element"<<endl;

cout<<"6.Rear Element "<<endl;

cout<<"7.Is empty?"<<endl;
cout<<"8.Length"<<endl;

while(true){
int operation;
cin>>operation;
if(operation <= 2){
int val; cin>>val;
if(operation == 1){
deq.insertFront(val);
}
else deq.insertRear(val);
}
else{
if(operation == 3){
deq.deleteFront();
}
else if(operation == 4){
deq.deleteRear();
}
else if(operation == 5){
if(deq.getFront() != -1)
cout<<"Front element: "<<deq.getFront()<<endl;
else cout<<"The deque is empty"<<endl;
}
else if(operation == 6){
if(deq.getRear() != -1)
cout<<"Rear element: "<<deq.getRear()<<endl;
else cout<<"The deque is empty"<<endl;
}
else if(operation == 7){
if(deq.isEmpty()) cout<<"The deque is empty"<<endl;
else cout<<"The deque is not empty"<<endl;
}
else if(operation == 8){
cout<<"The size of the deque is "<<deq.size()<<endl;
}
else break;
}
}
return 0;
}

Output:
11. Write a program to implement Binary Search Tree which supports the following operations:
(i) Insert an element x
(ii) Delete an element x
(iii) Search for an element x in the BST and change its value to y and then place the node with value
y at its appropriate position in the BST
(iv) Display the elements of the BST in preorder, inorder, and postorder traversal
(v) Display the elements of the BST in level-by-level traversal
(vi) Display the height of the BST
Answer:
#include<iostream>
using namespace std;
class node
{
public:
node()
{
left=right=NULL;
data=0;
visited=0;
}
int data,visited;
node *left,*Aright;
};
template<class t>
//stack
class stack
{
public:
t data;
stack *prev;
};
template<class t>
class stacks
{
stack<t> *top;
public:
stacks()
{
top=NULL;
}

void push(t n)
{
stack<t> *temp;
temp=new stack<t>;
temp->data=n;
temp->prev=top;
top=temp;
}

t pop()
{
t a;
if(top==NULL)
{

return NULL;
}
else
{
a=top->data;
top=top->prev;
return a;
}
}

int empty()
{
if(top==NULL)
return 0;
else
return 1;
}
};
class tlist
{
stacks<node*> st1,st2;
int visited;
public:
node *root;
tlist()
{
root=NULL;

visited=0;
}

void create(int n,node *current)

{
if(root==NULL)
{
cout<<"Entered in roote mking:\n";
root=new node;
root->data=n;
root->left=root->right=NULL;
}
else
{
if((n<current->data)&&(current->left==NULL))
{
node *temp;
temp=new node;
temp->data=n;
temp->left=temp->right=NULL;
current->left=temp;
}
else if((n>current->data)&&(current->right==NULL))
{
node *temp;
temp=new node;
temp->data=n;
temp->left=temp->right=NULL;
current->right=temp;
}
else
{
if(n<current->data)
create(n,current->left);
else
create(n,current->right);
}

}
}

void post_order(const node *roote)

{
if(roote!=NULL)
{
post_order(roote->left);
post_order(roote->right);
cout<<roote->data<<endl;
}
}

void pre_order(const node *roote)

{
if(roote!=NULL)
{
cout<<roote->data<<endl;
pre_order(roote->left);
pre_order(roote->right);
}
}

void in_order(const node *roote)

{
if(roote!=NULL)
{
in_order(roote->left);
cout<<roote->data<<endl;
in_order(roote->right);
}
}

void pre_order_nr()
{
node *current=root;
while(current!=NULL)
{
while((current!=NULL)&&(!visited))
{
st1.push(current);
//if(current!=NULL)
cout<<current->data<<endl;
current=current->left;
}
current=st1.pop();
if(current==NULL)
break;
visited=1;
if(current->right!=NULL)
{
visited=0;
current=current->right;
}
}
}

void post_order_nr()
{
node *tmp;
node *current=root;
while(current!=NULL)
{
while((current!=NULL)&&(!current->visited))
{ st1.push(current);

current=current->left;
}
current=st1.pop();
if(current==NULL)
break;
tmp=current->right;

if((current->right!=NULL) &&(!tmp->visited))
{
st1.push(current);
current=current->right;
continue;
}

if(!current->visited)
{
cout<<current->data<<endl;
current->visited =1;
}
}
}

void in_order_nr()
{
int ctr=0;
node *current=root;
while(current!=NULL)
{
while((current!=NULL)&&(!visited))
{
st1.push(current);
current=current->left;
}
current=st1.pop();
if(current!=NULL)
{
cout<<current->data<<endl;
ctr++;
}
else
break;
visited=1;
if(current->right!=NULL)
{
visited=0;
current=current->right;
}
}

cout<<"The number of nodes:\n"<<ctr<<endl;

}

void delete_node(int n)
{
node *current=root;
node *succ,*prev,*tmp=NULL;
prev=NULL;
while((current!=NULL)&&(current->data!=n))
{
if(current->data>n)
{
prev=current;
current=current->left;
}
else if(current->data<n)
{
prev=current;
current=current->right;
}
}
if(current==NULL)
cout<<"data not found\n";
else
{
if(current->right!=NULL)
{
succ=current->right;
if(succ->left!=NULL)
{
while(succ->left!=NULL)
{
prev=succ;
succ=succ->left;
}
prev->left=succ->right;
}
else
current->right=succ->right;
current->data=succ->data;

}
else
{

if(prev->left!=NULL)
if(current->data==prev->left->data)
prev->left=current->left;
else
prev->right=current->left;
else
prev->right=current->left;

}
}
}

void delete_node_merge(int n)
{
node *current=root;
node *succ,*prev,*tmp=NULL,*prev1=NULL;
prev=NULL;
while((current->data!=n)&&(current!=NULL))
{
if(n<current->data)
{
prev=current;
current=current->left;
}
else
{
prev=current;
current=current->right;
}
}
if(current==NULL)
cout<<"data not found\n";
else
{

if(current->right!=NULL)
{
succ=current->right;
if(succ->left!=NULL)
{
while(succ->left!=NULL)
{
prev1=succ;
succ=succ->left;
}
prev1->left=succ->right;
if(prev->left==current)
prev->left=succ;
else
prev->right=succ;
succ->left=current->left;
succ->right=current->right;
delete(current);
}
else
{
if(prev->left==current)
{
prev->left=succ;
succ->left=current->left;
delete(current);
}
else if(prev->right==current)
{
prev->right=succ;
succ->left=current->left;
delete(current);
}
}

}
else
{

if(prev->left!=NULL)
if(current->data==prev->left->data)
{
tmp=current;
prev->left=current->left;
}
else if(current->data==prev->right->data)
{
tmp=current;
prev->right=current->left;
}
else
{
tmp=current;
prev->right=current->left;
}

else
{
tmp=current;
prev->right=current->left;
}
delete(tmp);

}
}
}

int display_level()
{
int c=0;
node *current=root;
st1.push(current);
while((st1.empty())||(st2.empty()))
{
if(st1.empty()!=0)
{
while(st1.empty())
{
current=st1.pop();
cout<<current->data<<" -> ";
if(current->right!=NULL)
st2.push(current->right);
if(current->left!=NULL)
st2.push(current->left);
}
c++;
}
else
break;
cout<<endl;

if(st2.empty()!=0)
{
while(st2.empty())
{
current=st2.pop();
cout<<current->data<<" -> ";
if(current->right!=NULL)
st1.push(current->right);
if(current->left!=NULL)
st1.push(current->left);
}
c++;
}
else
break;
cout<<endl;
}
return c;

}
};
int main()
{
char ch;
int n=1;
tlist t1;
cout<<"Enter the numbers(enter 0 to terminate:\n";
for(int i=0;n!=0;i++)
{
cout<<"\nEnter the value:\n";
cin>>n;
cout<<endl;
if(n!=0)
t1.create(n,t1.root);
}
cout<<"Answer with post_order recursion:\n";
//t1.post_order(t1.root);
cout<<"The post_order without recursion:\n";
t1.in_order_nr();
do
{
cout<<"Wanna delete any data:\n";
cin>>ch;
if(ch=='y')
{
cout<<"Enter the number u want to delete:\n";
cin>>n;
t1.delete_node_merge(n);
}
}while(ch=='y');

cout<<"The resulting numbers in tree:\n";

t1.in_order(t1.root);

cout<<"The current tree:\n";

t1.pre_order(t1.root);

cout<<"The current tree:\n";

t1.in_order(t1.root);

int height;

cout<<"Want to see level wise tree:\n";

cin>>ch;
if(ch=='y')
{
height=t1.display_level();
cout<<"The height of tree is:\t"<<height<<endl;
}
cout<<"The current tree:\n";
t1.in_order_nr();
return 0;
}

Output:
12. Write a program, using templates, to sort a list of n elements. Give user the option to perform
sorting using Insertion sort, Bubble sort or Selection sort.
13. Write a program to implement:
(i) Diagonal Matrix using one-dimensional array.
(ii) Lower Triangular Matrix using one-dimensional array
(iii) Upper Triangular Matrix using one-dimensional array
(iv) Symmetric Matrix using one-dimensional array.
Answer:
#include<iostream>

using namespace std;

template <class T>

class sorting
{
T a[10];
public:
void get_item()
{
for(int i=0;i<10;i++)
{
cout<<"\n a["<<i<<"] = ";
cin>>a[i];
}
}

void sel_sort()
{
T temp;

for(int i=0;i<10;i++)
{
for(int j=i+1;j<10;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}

void bub_sort()
{
T temp;

for(int i=0;i<10;i++)
{
for(int j=0;j<10-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
void inst_sort()
{
T tmp;
int j;

for(int i=1;i<10;i++)
{
tmp=a[i];
j=i-1;
while(tmp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=tmp;
}
}

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

};// End of Class

int main()
{
// Creating Integer Array using Template
sorting<int> iarr;

cout<<"\n\n Enter Elements of Integer Array\n";

iarr.get_item();
cout<<"\n\n Elements of Integer Array\n";
iarr.display();
int choice=0;
do{

cout<<"MENU"<<endl;
cout<<"1.Selection sort"<<endl;
cout<<"2.Insertion sort"<<endl;
cout<<"3.Bubble sort"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice"<<endl;
cin>>choice;
if(choice==1)
{
iarr.sel_sort();
cout<<"\n\n After Selection Sorting\n Elememts of Integer Array\n";
iarr.display();
}
else if(choice==2)
{
iarr.inst_sort();
cout<<"\n\n After Insertion Sorting\n Elememts of Integer Array\n";
iarr.display();
}
else if(choice==3)
{
iarr.bub_sort();
cout<<"\n\n After Bubble Sorting\n Elememts of Integer Array\n";
iarr.display();
}
else if(choice==4)
{
break;
}
else
{
cout<<"Wrong Choice";
}
}while(choice!=4);
}

Output:
13.Write a program to implement: (
i) Diagonal Matrix using one-dimensional array. (
ii) Lower Triangular Matrix using one-dimensional array
(iii) Upper Triangular Matrix using one-dimensional array
(iv) Symmetric Matrix using one-dimensional array.
Answer:
#include<iostream>
#include<math.h>
using namespace std;
class sparse
{
int sp[4][4],temp[20];
int n;
public:
sparse()
{
n=0;
}
void insert()
{
cout<<"Enter the sparse matrix:\n";
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
cin>>sp[i][j];
}
void create_diagonal()
{ int ctr=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(i==j)
{
temp[ctr]=sp[i][j];
ctr++;
}
}
}
cout<<"The resulting matrix is:\n";
for(int i=0;i<=ctr;i++)
{
cout<<temp[i]<<" ";
}
cout<<endl;
}
void create_ltm(int m)
{
int ctr=0;
sp[20][20]={ };
cout<<"Enter the "<<n<<" enteryies for making lower triangular sparse matrix:\n";

for(int i=0;i<n;i++)
cin>>temp[i];
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
if((i>=j)&&(ctr<n))

sp[i][j]=temp[ctr++];
else
sp[i][j]=0;
}
}
}
void create_utm(int m)
{
int ctr=0;
sp[20][20]={0};

cout<<"Enter the "<<n<<" enteries for making upper triangular sparse matrix:\n";
for(int i=0;i<n;i++)
cin>>temp[i];
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
if((i<=j)&&(ctr<n))
sp[i][j]=temp[ctr++];
else
sp[i][j]=0;
}
}
}
void sym(int m)
{
int ctr=0;
sp[20][20]={0};

int sp1[20][20];
cout<<"Enter the "<<n<<" enteries for making symmetric sparse matrix:\n";
for(int i=0;i<n;i++)
cin>>temp[i];
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
if(ctr<n)
sp[i][j]=temp[ctr++];
else
sp[i][j]=0;
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
sp1[j][i]=sp[i][j];
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
sp[i][j]=(sp[i][j]+sp1[i][j])/2;
}
}
}
void display(int m)
{
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
cout<<sp[i][j]<<" ";
}
cout<<endl;
}
}
};
int main()
{ int n,cho,m,ctr=0,temp;
char ch;
do
{
sparse s1;
cout<<"What u want to make:\n1.diagonal\n2.lower triangular\n3.upper
triangular\n4.symmetric\n5.restart\n";
cin>>cho;
switch(cho)
{
case 1: s1.insert();
s1.create_diagonal();
s1.display(n);
break;
case 2:cout<<"Enter the order of matrix:\n";
cin>>m;
temp=m;
ctr=0;
while(temp>0)
{
ctr+=temp;
temp--;
}
cout<<"ctr= "<<ctr<<endl;
if(n<=ctr)
{
s1.create_ltm(m);
s1.display(m);
}
else
cout<<"more than required entries:\n";
break;
case 3:cout<<"Enter the order of matrix:\n";
cin>>m;
temp=m;
ctr=0;
while(temp>0)
{
ctr+=temp;
temp--;
}
cout<<"ctr= "<<ctr<<endl;
if(n<=ctr)
{
s1.create_utm(m);
s1.display(m);
}
else
cout<<"more than required entries:\n";
break;
case 4:cout<<"Enter the order of matrix:\n";
cin>>m;
if(((m*m)-n)>=(m*m)/2)
{
s1.sym(m);
s1.display(m);
}
else
cout<<"more than required entries for such a sparse matrix\n";
break;
case 5:continue;
break;
default: cout<<"Enter choice from 1 to 5 only:\n";
}
cout<<"Want to enter more:\n";
cin>>ch;
}while(ch=='y');
}

Output

14. Write a program to implement AVL Tree.

Answer:
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
int d;
struct avl *l;
struct avl *r;
}*r;
class avl_tree {
public:
int height(avl *);
int difference(avl *);
avl *rr_rotat(avl *);
avl *ll_rotat(avl *);
avl *lr_rotat(avl*);
avl *rl_rotat(avl *);
avl * balance(avl *);
avl * insert(avl*, int);
void show(avl*, int);
void inorder(avl *);
void preorder(avl *);
void postorder(avl*);
avl_tree() {
r = NULL;
}
};
int avl_tree::height(avl *t) {
int h = 0;
if (t != NULL) {
int l_height = height(t->l);
int r_height = height(t->r);
int max_height = max(l_height, r_height);
h = max_height + 1;
}
return h;
}
int avl_tree::difference(avl *t) {
int l_height = height(t->l);
int r_height = height(t->r);
int b_factor = l_height - r_height;
return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = t->l;
t->l = parent;
cout<<"Right-Right Rotation";
return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = t->r;
t->r = parent;
cout<<"Left-Left Rotation";
return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = rr_rotat(t);
cout<<"Left-Right Rotation";
return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = ll_rotat(t);
cout<<"Right-Left Rotation";
return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
int bal_factor = difference(t);
if (bal_factor > 1) {
if (difference(t->l) > 0)
t = ll_rotat(t);
else
t = lr_rotat(t);
} else if (bal_factor < -1) {
if (difference(t->r) > 0)
t = rl_rotat(t);
else
t = rr_rotat(t);
}
return t;
}
avl *avl_tree::insert(avl *r, int v) {
if (r == NULL) {
r = new avl;
r->d = v;
r->l = NULL;
r->r = NULL;
return r;
} else if (v< r->d) {
r->l = insert(r->l, v);
r = balance(r);
} else if (v >= r->d) {
r->r = insert(r->r, v);
r = balance(r);
} return r;
}
void avl_tree::show(avl *p, int l) {
int i;
if (p != NULL) {
show(p->r, l+ 1);
cout<<" ";
if (p == r)
cout << "Root -> ";
for (i = 0; i < l&& p != r; i++)
cout << " ";
cout << p->d;
show(p->l, l + 1);
}
}
void avl_tree::inorder(avl *t) {
if (t == NULL)
return;
inorder(t->l);
cout << t->d << " ";
inorder(t->r);
}
void avl_tree::preorder(avl *t) {
if (t == NULL)
return;
cout << t->d << " ";
preorder(t->l);
preorder(t->r);
}
void avl_tree::postorder(avl *t) {
if (t == NULL)
return;
postorder(t ->l);
postorder(t ->r);
cout << t->d << " ";
}
int main() {
int c, i;
avl_tree avl;
while (1) {
cout << "1.Insert Element into the tree" << endl;
cout << "2.show Balanced AVL Tree" << endl;
cout << "3.InOrder traversal" << endl;
cout << "4.PreOrder traversal" << endl;
cout << "5.PostOrder traversal" << endl;
cout << "6.Exit" << endl;
cout << "Enter your Choice: ";
cin >> c;
switch (c) {
case 1:
cout << "Enter value to be inserted: ";
cin >> i;
r = avl.insert(r, i);
break;
case 2:
if (r == NULL) {
cout << "Tree is Empty" << endl;
continue;
}
cout << "Balanced AVL Tree:" << endl;
avl.show(r, 1);
cout<<endl;
break;
case 3:
cout << "Inorder Traversal:" << endl;
avl.inorder(r);
cout << endl;
break;
case 4:
cout << "Preorder Traversal:" << endl;
avl.preorder(r);
cout << endl;
break;
case 5:
cout << "Postorder Traversal:" << endl;
avl.postorder(r);
cout << endl;
break;
case 6:
exit(1);
break;
default:
cout << "Wrong Choice" << endl;
}
}
return 0;
}
Output:
15. Write a Program to implement a priority queue using heap data structure.
Answer:
#include <bits/stdc++.h>
using namespace std;

int H[50];
int size = -1;

// Function to return the index of the

// parent node of a given node
int parent(int i)
{

return (i - 1) / 2;
}

// Function to return the index of the

// left child of the given node
int leftChild(int i)
{

return ((2 * i) + 1);

}

// Function to return the index of the

// right child of the given node
int rightChild(int i)
{

return ((2 * i) + 2);

}

// Function to shift up the node in order

// to maintain the heap property
void shiftUp(int i)
{
while (i > 0 && H[parent(i)] < H[i]) {

// Swap parent and current node

swap(H[parent(i)], H[i]);

// Update i to parent of i
i = parent(i);
}
}

// Function to shift down the node in

// order to maintain the heap property
void shiftDown(int i)
{
int maxIndex = i;

// Left Child
int l = leftChild(i);

if (l <= size && H[l] > H[maxIndex]) {

maxIndex = l;
}

// Right Child
int r = rightChild(i);

if (r <= size && H[r] > H[maxIndex]) {

maxIndex = r;
}

// If i not same as maxIndex

if (i != maxIndex) {
swap(H[i], H[maxIndex]);
shiftDown(maxIndex);
}
}

// Function to insert a new element

// in the Binary Heap
void insert(int p)
{
size = size + 1;
H[size] = p;

// Shift Up to maintain heap property

shiftUp(size);
}

// Function to extract the element with

// maximum priority
int extractMax()
{
int result = H[0];

// Replace the value at the root

// with the last leaf
H[0] = H[size];
size = size - 1;

// Shift down the replaced element

// to maintain the heap property
shiftDown(0);
return result;
}

// Function to change the priority

// of an element
void changePriority(int i, int p)
{
int oldp = H[i];
H[i] = p;

if (p > oldp) {
shiftUp(i);
}
else {
shiftDown(i);
}
}

// Function to get value of the current

// maximum element
int getMax()
{

return H[0];
}

// Function to remove the element

// located at given index
void remove(int i)
{
H[i] = getMax() + 1;

// Shift the node to the root

// of the heap
shiftUp(i);

// Extract the node

extractMax();
}

// Driver Code
int main()
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
Create a priority queue shown in
example in a binary max heap form.
Queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */

// Insert the element to the

// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);

int i = 0;

// Priority queue before extracting max

cout << "Priority Queue : ";
while (i <= size) {
cout << H[i] << " ";
i++;
}

cout << "\n";

// Node with maximum priority

cout << "Node with maximum priority : "
<< extractMax() << "\n";

// Priority queue after extracting max

cout << "Priority queue after "
<< "extracting maximum : ";
int j = 0;
while (j <= size) {
cout << H[j] << " ";
j++;
}

cout << "\n";

// Change the priority of element

// present at index 2 to 49
changePriority(2, 49);
cout << "Priority queue after "
<< "priority change : ";
int k = 0;
while (k <= size) {
cout << H[k] << " ";
k++;
}

cout << "\n";

// Remove element at index 3

remove(3);
cout << "Priority queue after "
<< "removing the element : ";
int l = 0;
while (l <= size) {
cout << H[l] << " ";
l++;
}
return 0;
}

Output:

16. Write a program to evaluate a prefix/postfix expression using stacks

Answer:
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100
using namespace std;
struct postfix
{
int stack[MAX];
int top,n;
char *s;
}p;
void init_post()
{
p.top=-1;
}
void init_exp(char *str)
{
p.s=str;
}
void push(int number)
{
p.top++;
p.stack[p.top]=number;
}
int pop()
{
int number=p.stack[p.top];
p.top--;
return number;
}
void calculate()
{
int n1, n2, x;
while(*(p.s))
{
if(*(p.s)==' ' || *(p.s)==' ')
{
p.s++;
continue;
}
if(isdigit(*(p.s)))
{
p.n=*(p.s)-'0';
push(p.n);
}
else
{
n1=pop();
n2=pop();
switch(*(p.s))
{
case '+':
x=n2+n1 ;
break;
case '-':
x=n2-n1 ;
break;
case '*':
x=n2*n1 ;
break;
case '/':
x=n2/n1 ;
break;
case '%':
x=n2%n1 ;
break;
case '^':
x=(int)pow(n2,n1) ;
break;
default:
cout<<"Invalid operator !!\n" ;
exit(1);
}
push(x);
}
p.s++;
}
}
void disp_result()
{
p.n=pop();
cout<<"\nResult = "<<p.n;
}
int main()
{
char exp[MAX];
init_post();
cout<<"Enter the postfix formed expression : ";
gets(exp);
init_exp(exp);

calculate();

disp_result();
return 0;
}

Output: