//stacks using Arrays

#include "iostream.h"
#include "conio.h"
const int SIZE = 10;

template
class stack
{
StackType stck[SIZE];
int tos;

public:
stack() {
tos = 0;
}
void push(StackType ob)
{
if(tos==SIZE) {
cout << "Stack is full.\n";
return;
}
stck[tos] = ob;
tos++;
}

StackType pop()
{
if(tos==0) {
cout << "Stack is empty.\n";
return 0; // return null on empty stack
}
tos--;
return stck[tos];
}
};

int main()
{
int i,j;
stack s1, s2;
clrscr();

s1.push('a');
s2.push('x');
s1.push('b');
s2.push('y');
s1.push('c');
s2.push('z');

for(i=0; i<3; i++)
cout << "Pop s1: " << s1.pop() << "\n";
for(j=0; j<3; j++)
cout << "Pop s2: " << s2.pop() << "\n";

stack ds1, ds2;

ds1.push(1.1);
ds2.push(2.2);
ds1.push(3.3);
ds2.push(4.4);
ds1.push(5.5);
ds2.push(6.6);

for(i=0; i<3; i++)
cout << "Pop ds1: " << ds1.pop() << "\n";
for(j=0; j<3; j++)
cout << "Pop ds2: " << ds2.pop() << "\n";
getch();
return 0;
}

// Insertion & Deletion of element in Queue (using Array)

#include "iostream.h"
#include "conio.h"
#include "process.h"


int ins(int[], int);
int del(int[]);

void display(int[], int, int);

const int size=20;

int q[size], f=-1, r=-1;

int main()
{
int item, res;
char ch='y';
clrscr();
while(ch=='y' ||ch=='Y')
{
cout<<"\nEnter Item for insertion: ";
cin>>item;
res=ins(q,item);
if (res==-1)
{
cout<<"\nOver flow\n ";
exit(1);
}
cout<<"\nQueue: ";
display(q, f, r);
cout <<"\nInsert more Y/N :- ";
ch=getch();
}

cout << "\n\nDeletion of element begins... \n";
ch='y';

while (ch=='y'||ch=='Y')
{
res=del(q);
if(res==-1)
{
cout<< "\nUnder flow";
exit(1);
}
else
{
cout<<"\nElement deleted is : "< cout<<"\nQueue: ";
display(q, f, r);
}
cout<<"\nWant to delete more element Y/N -";
cin >> ch;
if(ch=='n'||ch=='N')
cout<<"\nQueue: ";
display(q,f,r);
}
getch();
return 0;
}


int ins(int q[], int ele)
{
if (r==size-1)
return -1;
else if (r==-1)
{
f=r=0;
q[r]=ele;
}
else
{
r++;
q[r]=ele;
}
return 0;
}


int del (int q[])
{
int ret;
if(f==-1)
return -1;
else
{
ret = q[f];
if (f==r)
f=r=-1;
else
f++;
}
return ret;
}


void display(int q[], int f, int r)
{
if (f== -1) return;
cout<< "F-";
for(int i = f;i<=r;i++)
cout< cout<<"R";
}



/* Output::::::::::::::::::::

Enter Item for insertion: 10
Queue: F-10-R
Insert more Y/N :-

Enter Item for insertion: 20
Queue: F-10-20-R
Insert more Y/N :-

Enter Item for insertion: 30
Queue: F-10-20-30-R
Insert more Y/N :-

Deletion of element begins...
Element deleted is : 10
Queue: F-20-30-R
Want to delete more element Y/N -

*/

priority queue

#include "iostream.h"
#include "conio.h"
#include "iomanip.h"
#define MAX 10
class pqueue
{
int pq[MAX];
int mh;
public:
pqueue();

int size(void){ return mh;}
int isempty(void) {
if(mh == 0)
return 1;
return 0;}
int pop(void);
void push(int);
void display(void);
int top(void){
if(!isempty()) return pq[1];
else cout<<"\n PQ empty"; return 0;}
};
pqueue::pqueue()
{
for(int i = 0; i < MAX; i++,pq[i] = 0);
mh = 0;
}
void pqueue::push(int ele) {
int cpos = ++mh;
while(cpos != 1 && pq[cpos/2] < ele) {
pq[cpos] = pq[cpos/2];
cpos /= 2; }
pq[cpos] = ele;

}
int pqueue::pop(void) {
if(!isempty()) {
int le = pq[mh--];
pq[0] = pq[1];
int cnode = 1;
int child = 2;
while(child<= mh) {
if(child < mh && pq[child] child++;
if(le >= pq[child])
break;
pq[cnode] = pq[child];
cnode = child;
child *= 2;
}
pq[cnode] = le;
return pq[0];
}
else {
cout<<"\n Queue is Empty ";
return 0;
}

}

void pqueue::display(void) {
if(!isempty()) {
cout<<"\n The elements in the queue :"< for(int i = 1; i <= mh; i++)
cout< else cout<<"\n Queue is empty";
}
int menu(void) {
cout<<"\n\tMENU"< cout<<"\n 1 -> push \n 2 -> pop \n ";
cout<<"3 ->isempty \n 4 -> Display";
cout<<"\n 5 ->topelement \n 6 -> size \n ";
cout<<"\n 7 -> Heap Sort \n 8 -> exit ";
cout<<"\n Enter your choice :";
int ch;
cin>>ch;
return ch;
}
void heapsort(void) {
int n,ele;
pqueue q;
cout<<"\n Enter the no.of elements :";
cin>>n;
cout<<"\n Enter the elements : \n";
for(int i = 0; i < n; i++) {
cin>>ele;
q.push(ele);
}
cout<<"\n The elements in the sorted order is :\n";
for(i = 0 ; i < n; i ++)
cout<}
void main() {
int ch,ele;
pqueue p;
do {
clrscr();
ch = menu();
switch(ch){
case 1: cout<<"\n Enter the element to push : ";
cin>>ele;
p.push(ele); break;
case 2: ele = p.pop();
if(ele)
cout<<"\n The popped element is :"< break;
case 3: if(p.isempty())
cout<<"\n queue is empty" ;
else
cout<<"\n queue is not empty ";
break;
case 4: p.display(); break;
case 5: ele = p.top();
cout<<"\n The top element is :"< break;
case 6: cout<<"\n No.of elements is :"< break;
case 7: heapsort(); break;
case 8: break;
Default:cout<<"\n Invalid Choice. Try again ";
} getch();

}while (ch != 8);
}

// Binary Search Tree Program

#include "iostream.h"
#include "conio.h"
#include "iomanip.h"
class bnode
{
public:
bnode *left;
bnode *right;
int data;
bnode(){}
bnode(int e)
{
left = NULL;
right = NULL;
data = e;
}

};
class bst
{
bnode *root;
public:
bst(){ root = NULL;}
int find(int);
int insert(int);
int remove(int);
void display(void);
void inorder(bnode*);

};

int bst::find(int ele)
{
bnode *p=root;
while(p)
{
if(p->data == ele) return 1;
else if(p->data < p =" p"> right;
else p = p -> left;
} return 0;
}
int bst::insert(int ele)
{
bnode *p = root;
bnode *q = new bnode(ele);
bnode *pp;
if(root)
{
while(p)
{
pp = p;
if(p -> data < p =" p"> right;
else if(p -> data > ele) p = p -> left;
else return 1;
}
if(pp -> data < ele)
pp -> right = q;
else pp -> left = q;
}
else root = q;

return 0;
}

int bst::remove(int ele){
bnode *p = root; bnode *pp = NULL;
while(p && p ->data != ele){
pp = p;
if(p -> data > ele) p = p -> left;
else p = p -> right;
}if(!p) return 1;
if(p -> left && p -> right) {
bnode *s = p -> left;
bnode *ps = p;
while(s -> right) {
ps = s; s = s -> right;
}bnode *q = new bnode(s->data);
q -> left = p -> left;
q -> right = p ->right;
if(pp == NULL) root = q;
else if(pp -> left == p)
pp -> left = q;
else pp -> right = q;
if(ps == p) pp = q;
else pp = ps;
p = s;
}bnode *c;
if(p -> left) c = p -> left;
else c = p ->right;
if( p == root) root = c;
else {
if(p == pp -> left)
pp -> left = c;
else
pp -> right = c;
} delete p; return 0; }


void bst::display(void)
{
inorder(root);
}
void bst::inorder(bnode* p)
{
if(p)
{
inorder(p -> left);
cout< data;
inorder(p -> right);
}

}

int menu(void)
{
cout<<"\n Binary Search Tree Menu \n";
cout<<"\n 1 -> insert\n 2 -> Delete \n 3 -> find ";
cout<<"\n 4 -> display \n 5 -> exit ";
cout<<"\n Enter your choice :";
int ch;
cin>>ch;
return ch;

}

void main()
{
bst b; int ch,ele;
do{
clrscr();
ch = menu();
switch(ch) {
case 1: cout<<"\n Enter the element to insert :";
cin>>ele;
if(b.insert(ele))
cout<<"\n Duplicate element ";
break;
case 2: cout<<"\n Enter the element to remove :";
cin>>ele;
if(b.remove(ele))
cout<<"\n Element not in the list:";
break;
case 3: cout<<"\n Enter the element to find:";
cin>>ele;
if(b.find(ele))
cout<<"\n Element found";
else
cout<<"\n Element not found :";
break;
case 4: cout<<"\n The elements in the list :";
b.display();
break;
case 5: break;
default:
cout<<"\n Invalid choice . Try again"; } getch(); }while(ch != 5);
}