INSERTION SORT

INSERTION SORT

Program

#include"stdio.h"
#include"conio.h"
int i,j,a[20],n;

void main()
{
clrscr();
printf("\n INSERTION SORT \n");
printf("Enter The Number Of Elements :");
scanf("%d",&n);
for(i=0;i < n;i++)
scanf("%d",&a[i]);
insert(a,n);
printf("The Sorted List Is :\n");
for(i=0;i < n;i++)
printf("%d\n",a[i]);
getch();
}

insert(a,n)
int a[],n;
{
int i,k,y;
for(k=1;k < n;k++)
{
y=a[k];
for(i=k-1;i > =0 &&y < a[i];i--)
a[i+1]=a[i];
a[i+1]=y;
}
return;
}

OUTPUT


INSERTION SORT
Enter The Number Of Elements :5
4
2
8
5
3
The Sorted List Is :
2
3
4
5
8

Index DS using C++

Data Structures Using C++

POLYNOMIAL DIFFERENTIATION

PRINTING NODE DETAILS IN LEVEL WISE

MATRIX USING BINARY SEARCH

KNAPSACK PROBLEM

BINARY TREE TRAVERSAL

TRAVELLING SALESMAN PROBLEM

KRUSKAL ALGORITHM

RED BLACK TREES

MINIMUM SPANNING TREE

POLYNOMIAL DIFFERENTIATION

POLYNOMIAL DIFFERENTIATION

#include”iostream.h”
#include”conio.h”
struct node
{
int coeff;
int pow;
struct node *next;
};

class polydiff
{
struct node *head;
struct node *i;
public:
void creation();
void display();
void differen();
polydiff();
};
polydiff::polydiff()
{
head=NULL;
}

void polydiff::creation()
{
char res;
struct node *temp;
head=new struct node();
cout<<"Enter the 1st term in the polynomial with coeff & Power";
cin>>head->coeff;
cin>>head->pow;
head->next=NULL;
cout<<"do u want to add another node\n";
cin>>res;
while(res=='y'res=='Y')
{
temp=new struct node();
cout<<"Enter coeff & power\n";
cin>>temp->coeff;
cin>>temp->pow;
temp->next=NULL;
for(i=head;i->next!=NULL;i=i->next);
i->next=temp;
cout<<"Interested in adding another node\n";
cin>>res;
}
}

void polydiff::display()
{
for(i=head;i!=NULL;i=i->next)
{
if(i->pow!=0)
{
cout<coeff<<"X^";
cout<pow<<"+";
}
else
cout<coeff;
}
}

void polydiff::differen()
{
for(i=head;i!=NULL;i=i->next)
{
if(i->pow!=0)
{
i->coeff=i->coeff*i->pow;
i->pow--;
}
else
{
i->coeff=0;
i->pow=0;
}
}
}

void main()
{
clrscr();
polydiff p;
printf(“POLYNOMIAL DIFFERENTIATION\n”);
p.creation();
p.display();
cout<<"\n\nDifferentiation is\n";
p.differen();
p.display();
getch();
}



OUTPUT:


POLYNOMIAL DIFFERENTIATION

Enter the 1st term in the polynomial with coeff & Power
25 4
do u want to add another node
y
Enter coeff & power
12 3
Interested in adding another node
y
Enter coeff & power
1 1
Interested in adding another node
y
Enter coeff & power
10
0
Interested in adding another node
n
25X^4+12X^3+1X^1+10

Differentiation is
100X^3+36X^2+10

PRINTING NODE DETAILS IN LEVEL WISE

PRINTING NODE DETAILS IN LEVEL WISE

#include”iostream.h”
#include”conio.h”
#include”malloc.h”
#include”math.h”
#include”process.h”
class binary
{
private:
struct node
{
int data;
node *left,*right;
}*root;
node *queue[30];
int rear,front,size;
public:
void insert(node *);
struct node *remove();
int qnotempty();
void create();
void traverse();
};

void binary::insert(node *temp)
{
queue[rear++]=temp;
}

struct binary::node *binary::remove()
{
node *temp=queue[front];
front++;
if(front==rear)
{
front=rear=0;
}
return temp;
}

int binary::qnotempty()
{
if(front==0 && rear==0)
{
return(0);
}
else
{
return(1);
}
}

void binary::create()
{
int i=1;
node *new1, *temp;
root=NULL;
rear=front=0;
cout<<"Enter the size of the tree\t";
cin>>size;
new1=new node();
new1->left=new1->right=NULL;
cout<<"Enter the"< cin>>new1->data;
root=new1;
insert(root);
//insert(root);
for(i=2;i<=size;i++)
{
temp=remove();
new1= new node();
new1->left=new1->right=NULL;
cout<<"Enter the "< cin>>new1->data;
if(temp->left==NULL)
{
temp->left=new1;
}
else
if(temp->right==NULL)
{
temp->right=new1;
}
insert(new1);
//insert(new1);
}
}
void binary::traverse()
{
int level=0;
int count=0;
rear=front=0;
node *temp=root;
insert(temp);
cout<<"\nLevel"< do
{
temp=remove();
if(temp!=NULL)
{
cout<<"\t"<data;
insert(temp->left);
//insert(temp->right);
}
count++;
if(pow(2,level)==count && pow(2,level+1) <= size)
{
level++;
cout< count=0;
}
}while(qnotempty()==1);
}

void main()
{
int ch;
binary b;
clrscr();
for(;;)
{
cout<<"\n\n1.Create\n2.LevelWise Traverse\n3.Exit\n";
cout<<"Enter choice\n";
cin>>ch;
switch(ch)
{
case 1:
b.create();
break;
case 2:
b.traverse();
break;
case 3:
exit(0);
}
}
}






OUTPUT:

PRINTING NODE DETAILS IN LEVEL WISE



1.Create
2.LevelWise Traverse
3.Exit
Enter choice
1
Enter the size of the tree 6
Enter the1Element 34
Enter the 2Element 54
Enter the 3Element 67
Enter the 4Element 23
Enter the 5Element 43
Enter the 6Element 99


1.Create
2.LevelWise Traverse
3.Exit
Enter choice
2

Level0 34

Level1 54 67

Level2 23 43 99


1.Create
2.LevelWise Traverse
3.Exit
Enter choice
3

MATRIX USING BINARY SEARCH

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH

#include”iostream.h”
#include”conio.h”
class matrix
{
int a[50][50],m,n,i,j,low,mid,high,h;
public:
void getdata();
void putdata();
void binsearch(int);
};

void matrix::getdata()
{
cout<<"\nEnter the row & Column"< cin>>m>>n;
cout<<"Enter the elements in increasing order\n";
if(m==n)
for(i=0;i for(j=0;j cin>>a[i][j];
}

void matrix::putdata()
{
cout<<"\nMatrix is\n\n";
for(i=0;i {
for(j=0;j {
cout< }
cout< }
}

void matrix::binsearch(int s)
{
for(i=0;i {
low=1;
high=m;
while(low<=high)
{
mid=(low+high)/2;
if(s==a[i][mid-1])
{
cout<<"\nElement is in the list\n"< cout<<"Position of the element\t"<<++i<<"\t"< h=1;
break;
}
else if(s high=mid-1;
else
low=mid+1;
}
}
if(h==0)
cout<<"\nElement not in the list";
}

void main()
{
clrscr();
int search;
matrix m;
m.getdata();
m.putdata();
cout<<"\nEnter the element to be searched\t";
cin>>search;
m.binsearch(search);
getch();
}
















OUTPUT:

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH

Enter the row & Column
3
3
Enter the elements in increasing order
10
20
30
40
50
60
70
80
90

Matrix is

10 20 30
40 50 60
70 80 90

Enter the element to be searched 50

Element is in the list

Position of the element 2 2

SEARCHING AN ELEMENT IN A MATRIX USING BINARY SEARCH

Enter the row & Column
2
2
Enter the elements in increasing order
90
80
70
60

Matrix is

90 80
70 60

Enter the element to be searched -10

Element not in the list

KNAPSACK PROBLEM

KNAPSACK PROBLEM

#include”iostream.h”
#include”conio.h”
#include”process.h”
int Capacity;
int profit[40],weight[40],n;
float ratio[40],temp[40],temp1[40],soln[40];
class knapsack
{
public:
void getdata();
void sort();
void display();
void calculatesoln();
float getmaxprofit();
};

void knapsack::getdata()
{
clrscr();
cout<<"\nEnter the Capacity of Bag\n";
cin>>Capacity;
//cout< cout<<"Enter the number of objects\n";
cin>>n;
//cout< cout<<"Enter the profit\n\n";
for(int i=0;i cin>>profit[i];
cout< cout<<"Enter the weight\n\n";
for(i=0;i cin>>weight[i];
cout< for(i=0;i {
ratio[i]=(float)profit[i]/(float)weight[i];
temp[i]=ratio[i];
temp1[i]=ratio[i];
}
}

void knapsack::sort()
{
float t;
for(int i=0;i {
for(int j=i+1;j {
if(ratio[i] {
t=ratio[i];
ratio[i]=ratio[j];
ratio[j]=t;
}
}
}
}

void knapsack::calculatesoln()
{
int maxcapac=0;
for(int i=0;i {
for(int p=0;p if(temp[p]==ratio[i])
{
if((maxcapac+weight[p])<=Capacity)
{
soln[p]=1.0;
maxcapac+=weight[p];
temp[p]=-1.0;
}
/* else
{
soln[p]=(float)(Capacity-maxcapac)/weight[p];
maxcapac+=Capacity-maxcapac;
temp[p]=-1.0;
}*/
break;
}
if(maxcapac==Capacity)
break;
}
}


float knapsack::getmaxprofit()
{
knapsack k;
float maxprofit=0.0;
k.calculatesoln();
k.display();
for(int i=0;i maxprofit+=(soln[i]*profit[i]);
return maxprofit;
}

void knapsack::display()
{
clrscr();
cout<<"\nKNAPSACK PROBLEM\n";
cout<<"----------------";
cout<<"\nWeight of each Node\n";
for(int i=0;i cout< cout<<"\n";
cout<<"\nProfit of each node\n";
for(i=0;i cout< cout<<"\n";
cout<<"\n\n Profit Ratio Pi/Wi is\n\n";
for(i=0;i cout< cout<<"\nValues \tProfit/Weight\n";
for(i=0;i {
cout<<"\nx"< }
}

void main()
{
clrscr();
knapsack kp;
kp.getdata();
kp.sort();
cout<<"\n\nMaximum Profit="< getch();
}














OUTPUT:

KNAPSACK PROBLEM

Enter the Capacity of Bag
10
Enter the number of objects
5
Enter the profit
80
60
75
20
10
0
Enter the weight
2
1
5
2
2

KNAPSACK PROBLEM

Weight of each Node
2 1 5 2 2

Profit of each node
80 60 75 20 10

Profit Ratio Pi/Wi is

60 40 15 10 5

Values Profit/Weight
x0 1 40
x1 1 60
x2 1 15
x3 1 10
x4 0 5

Maximum Profit=235

BINARY TREE TRAVERSAL

BINARY TREE TRAVERSAL

#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
struct node
{
int data;
struct node *left;
struct node *right;
}*root;

class btraverse
{
public:
btraverse()
{
root=NULL;
}
void create(int);
void preorder(struct node *);
void inorder(struct node *);
void postorder(struct node *);
};

void btraverse::create(int data)
{
struct node *newnode=new node;
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
struct node *prev,*temp;
prev=temp=root;
while(temp!=NULL)
{
if(data==temp->data)
{
cout<<"\nData already exists"; return; } else { if(datadata)
{
prev=temp;
temp=temp->left;
}
else
{
prev=temp;
temp=temp->right;
}
}
}
if(root==NULL)
root=newnode;
else if(datadata)
prev->left=newnode;
else
prev->right=newnode;
}

void btraverse::preorder(struct node *t)
{
if(t!=NULL)
{
cout<<" "<data;
preorder(t->left);
preorder(t->right);
}
}

void btraverse::inorder(struct node *t)
{
if(t!=NULL)
{
inorder(t->left);
cout<<" "<data;
inorder(t->right);
}
}

void btraverse::postorder(struct node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
cout<<" "<data;
}
}



void main()
{
btraverse bt;
int ch,item,n,i;
clrscr();
while(ch<=5) { cout<<"\n"; cout<<"\n1.Create"; cout<<"\n2.Preorder"; cout<<"\n3.Inorder"; cout<<"\n4.Postorder"; cout<<"\n5.Exit"; cout<<"\nEnter ur choice:\t"; cin>>ch;
cout<<"\n"; switch(ch) { case 1: cout<<"\nEnter the total items\n"; cin>>n;
cout<<"Enter the data\n\n"; for(i=0;i>item;
bt.create(item);
}
break;
case 2:
bt.preorder(root);
break;
case 3:
bt.inorder(root);
break;
case 4:
bt.postorder(root);
break;
case 5:
exit(0);
}
}
getch();
}





OUTPUT:
BINARY TREE TRAVERSAL
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 1
Enter the total items
8
Enter the data
30
12
40
10
20
35
50
60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 2
30 12 10 20 40 35 50 60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 3
10 12 20 30 35 40 50 60
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 4
10 20 12 35 60 50 40 30
1.Create
2.Preorder
3.Inorder
4.Postorder
5.Exit
Enter ur choice: 5

TRAVELLING SALESMAN PROBLEM

TRAVELLING SALESMAN PROBLEM

#include”iostream.h”
#include”conio.h”
int n,a[50][50],bpath[50],list[50],i,j,bcost,tbcost;
void calculate(int list[])
{
int t;
tbcost=0;
for(j=1;j {
t=a[list[j-1]][list[j]];
if(t!=0)
tbcost+=a[list[j-1]][list[j]];
else
tbcost=bcost+1;
}
}

void snap(int &x, int &y)
{
int temp;
temp=x;
x=y;
y=temp;
}

void permute(int k, int x)
{
int temp,i,j;
if(k==x)
{
calculate(list);
if(bcost==0)
bcost=tbcost+1;
if((tbcost {
bcost=tbcost;
for(j=0;j bpath[j]=list[j];
}
}
else
{
for(i=k;i<=x;i++)
{
snap(list[k],list[i]);
permute(k+1,x);
snap(list[k],list[i]);
}
}
}

void main()
{
clrscr();
cout<<"Enter the number of cities\n";
cin>>n;
for(i=0;i for(j=0;j {
if(i!=j)
{
cout<<"\nEnter the cost of travelling from"<<"("< cin>>a[i][j];
}
else
a[i][j]=0;
}
for(i=0;i list[i]=i;
permute(1,n-1);
cout<<"\nBest path is\n\n";
for(i=0;i cout< cout<<"\n\n Cost of best path is: "<< bcost+a[bpath[n-1]][0];
getch();
}





Enter the number of cities
4
Enter the cost of travelling from(1to2)6

Enter the cost of travelling from(1to3)0

Enter the cost of travelling from(1to4)8

Enter the cost of travelling from(2to1)4

Enter the cost of travelling from(2to3)3

Enter the cost of travelling from(2to4)0

Enter the cost of travelling from(3to1)0

Enter the cost of travelling from(3to2)5

Enter the cost of travelling from(3to4)10

Enter the cost of travelling from(4to1)2

Enter the cost of travelling from(4to2)0

Enter the cost of travelling from(4to3)6

Best path is

1 2 3 4

Cost of best path is: 21

KRUSKAL ALGORITHM

MINIMUM SPANNING TREE

KRUSKAL ALGORITHM

#include”iostream.h”
#include”conio.h”
class kruskal
{
struct node
{
int s;
int e;
int c;
};
node a[10],b[10];
int n,p[10],r[10];
public:
int getdata();
int findset(int);
void mintree(int);
void makeset(int);
void uni(int,int);
void link(int,int);
};

int kruskal::getdata()
{
int i,j,d,cn=0;
cout<<"Enter the number of vertices\n\n";
cin>>n;
for(i=0;i {
makeset(i);
for(j=i+1;j {
if(i!=j)
{
cout<<"Enter the cost of "<<"("< cin>>d;
if(d!=0)
{
a[cn].s=i+1;
a[cn].e=j+1;
a[cn].c=d;
cn++;
}
}
}
}
for(i=0;i {
for(j=i;j {
if(a[i].c>a[j].c)
{
int temp=a[i].s;
a[i].s=a[j].s;
a[j].s=temp;

temp=a[i].e;
a[i].e=a[j].e;
a[j].e=temp;

temp=a[i].c;
a[i].c=a[j].c;
a[j].c=temp;
}
}
}
cout<<"\nStart\tEnd\tCost\n";
for(i=0;i cout<<"\n"< return(cn);
}

void kruskal::makeset(int x)
{
p[x]=x;
r[x]=0;
}

void kruskal::uni(int x,int y)
{
int a=findset(x);
int b=findset(y);
link(a,b);
}

void kruskal::link(int x,int y)
{
if(r[x]>r[y])
p[y]=x;
else
p[x]=y;
if(r[x]==r[y])
r[y]=r[y]+1;
}

int kruskal::findset(int x)
{
if(x!=p[x])
p[x]=findset(p[x]);
return(p[x]);
}

void kruskal::mintree(int a1)
{
int i,j,u,v,ctr=0;
for(i=0;i {
u=a[i].s;
v=a[i].e;
if(findset(u)!=findset(v))
{
uni(u,v);
b[ctr].s=u;
b[ctr].e=v;
b[ctr].c=a[i].c;
ctr++;
}
}
cout<<"Edges in the minimum spanning tree\n";
for(i=0;i cout<<"\nEdge:"<<"("<}

void main()
{
kruskal k;
clrscr();
int a1=k.getdata();
k.mintree(a1);
getch();
}

INDEQUE

INDEQUE

/* Input-restricted deque program using array. */

#include “stdio.h”
#include
#include

#define MAX 10

struct dqueue
{
int arr[MAX] ;
int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatend ( struct dqueue *, int item ) ;
int delqatbeg ( struct dqueue * ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatend ( &dq, 12 ) ;
addqatend ( &dq, 13 ) ;
addqatend ( &dq, 14 ) ;
addqatend ( &dq, 15 ) ;
addqatend ( &dq, 16 ) ;
addqatend ( &dq, 17 ) ;
addqatend ( &dq, 18 ) ;
addqatend ( &dq, 19 ) ;
addqatend ( &dq, 20 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;
display ( dq ) ;

addqatend ( &dq, 19 ) ;
addqatend ( &dq, 20 ) ;
addqatend ( &dq, 21 ) ;
addqatend ( &dq, 22 ) ;
addqatend ( &dq, 23 ) ;
addqatend ( &dq, 24 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
int i ;

p -> front = p -> rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )
p -> arr[i] = 0 ;
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
int i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> rear == -1 && p -> front == -1 )
{
p -> rear = p -> front = 0 ;
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
return ;
}

if ( p -> rear == MAX )
{
for ( i = k = p -> front - 1 ; i <> rear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
p -> arr[k] = 0 ;
else
p -> arr[k] = p -> arr[i + 1] ;
}
( p -> rear )-- ;
( p -> front )-- ;
}
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
}

/* deletes item from begining of dqueue */
int delqatbeg ( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

item = p -> arr[p -> front] ;
p -> arr[p -> front] = 0 ;
( p -> front )++ ;

if ( p -> front == MAX )
p -> front = -1 ;

return item ;
}

/* deletes item from end of dqueue */
int delqatend ( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

( p -> rear )-- ;
item = p -> arr[p -> rear] ;
p -> arr[p -> rear] = 0 ;

if ( p -> rear == 0 )
p -> rear = -1 ;
return item ;
}

/* displays the queue */
void display ( struct dqueue dq )
{
int i ;

printf ( "\n front -> " ) ;

for ( i = 0 ; i < MAX ; i++ )
printf ( "%d\t", dq.arr[i] ) ;
printf ( " <- rear" ) ;
}

/* counts the number of items in dqueue */
int count ( struct dqueue dq )
{
int c, i ;

for ( i = c = 0 ; i < MAX ; i++ )
{
if ( dq.arr[i] != 0 )
c++ ;
}
return c ;
}

OUTDEQUE

OUTDEQUE

/* Output-restricted deque program using array. */

#include “stdio.h”
#include
#include

#define MAX 10

struct dqueue
{
int arr[MAX] ;
int front, rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatbeg ( struct dqueue *, int ) ;
void addqatend ( struct dqueue *, int ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatbeg ( &dq, 10 ) ;
addqatend ( &dq, 12 ) ;
addqatbeg ( &dq, 9 ) ;
addqatend ( &dq, 13 ) ;
addqatbeg ( &dq, 8 ) ;
addqatend ( &dq, 14 ) ;
addqatbeg ( &dq, 7 ) ;
addqatend ( &dq, 15 ) ;
addqatbeg ( &dq, 6 ) ;
addqatend ( &dq, 16 ) ;
addqatbeg ( &dq, 5 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;

display ( dq ) ;

addqatbeg ( &dq, 5 ) ;
addqatbeg ( &dq, 4 ) ;
addqatbeg ( &dq, 3 ) ;
addqatbeg ( &dq, 2 ) ;

display ( dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
int i ;

p -> front = p -> rear = -1 ;

for ( i = 0 ; i < MAX ; i++ )
p -> arr[i] = 0 ;
}

/* adds item at begining of dqueue */
void addqatbeg ( struct dqueue *p, int item )
{
int c, i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> front == -1 && p -> rear == -1 )
{
p -> front = p -> rear = 0 ;
p -> arr[p -> front] = item ;
return ;
}

if ( p -> rear != MAX )
{
c = count ( *p ) ;
k = p -> rear ;

for ( i = 1 ; i <= c ; i++ )
{
p -> arr[k] = p -> arr[k - 1] ;
k-- ;
}

p -> arr[k] = item ;
p -> front = k ;
( p -> rear )++ ;
}
else
{
( p -> front )-- ;
p -> arr[p -> front] = item ;
}
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
int i, k ;

if ( p -> front == 0 && p -> rear == MAX )
{
printf ( "\nQueue is full.\n" ) ;
return ;
}

if ( p -> rear == -1 && p -> front == -1 )
{
p -> rear = p -> front = 0 ;
p -> arr[p -> rear] = item ;
( p -> rear )++ ;
return ;
}

if ( p -> rear == MAX )
{
k = p -> front - 1 ;

for ( i = p -> front - 1 ; i <> rear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
p -> arr[k] = 0 ;
else
p -> arr[k] = p -> arr[i + 1] ;
}
( p -> rear )-- ;
( p -> front )-- ;
}

p -> arr[p -> rear] = item ;
( p -> rear )++ ;
}

/* deletes item from end of dqueue */
int delqatend( struct dqueue *p )
{
int item ;

if ( p -> front == -1 && p -> rear == -1 )
{
printf ( "\nQueue is empty.\n" ) ;
return 0 ;
}

( p -> rear )-- ;
item = p -> arr[p -> rear] ;
p -> arr[p -> rear] = 0 ;

if ( p -> rear == 0 )
p -> rear = -1 ;

return item ;
}

/* displays the queue */
void display( struct dqueue dq )
{
int i ;

printf ( "\n front -> " ) ;

for ( i = 0 ; i < MAX ; i++ )
printf ( "\t%d", dq.arr[i] ) ;

printf ( " <- rear " ) ;
}

/* counts the number of items in dqueue */
int count( struct dqueue dq )
{
int c, i ;
for ( i = c = 0 ; i < MAX ; i++ )
{
if ( dq.arr[i] != 0 )
c++ ;
}
return c ;
}