Sunday, 3 June 2012

C++ program to implements dequeues using circular arrays

C++ program to implements dequeues using circular arrays. Dequeues are queues in which elements can be inserted/deleted from either end
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <alloc.h>

#define MAXSIZE 30
#define TRUE 1
#define FALSE 0

/*---------------------STRUCTURE DECLARATION-----------------------------*/
struct queue
{
int front,rear;
int data[MAXSIZE];
};
struct queue *q;
/*-----------------------------------------------------------------------*/

/*--------------------FUNCTION DECLARATION-------------------------------*/
void insert(int);
int remove(int);
int empty();
void display();
/*-----------------------------------------------------------------------*/

/*--------------------GLOBAL VARIABLES-----------------------------------*/
int flag,x, count=0;
/*-----------------------------------------------------------------------*/

/*------------------------MAIN-------------------------------------------*/
main()
{
q=(struct queue *)malloc(sizeof (struct queue));
int ch,z,i;
clrscr();
q->front=0;
q->rear=0;
for (i=0; i<MAXSIZE; i++)
q->data[i]=-1;
do
{
cout<<"\n";
cout<<"\n 1. Insert an element to the left.";
cout<<"\n 2. Insert an element to the right.";
cout<<"\n 3. Delete an element from the left.";
cout<<"\n 4. Delete an element from the right.";
cout<<"\n 5. Display current status of the dequeue.";
cout<<"\n 6. Exit.";
cout<<"\n Enter choice:";
cin>>ch;

switch(ch)
{
case 1 : insert(1);
display();
break;
case 2 : insert(2);
display();
break;
case 3 : z=remove(1);
cout<<"\n The element deleted is: "<< z;
display();
break;
case 4 : z=remove(2);
cout<<"\n The element deleted is:"<< z;
display();
break;
case 5 : display();
break;
case 6 : exit(1);
}
}while (ch!=7);
getch();
}
/*-----------------------------------------------------------------------*/

/*----------------------INSERT ELEMENT-----------------------------------*/
void insert(int flag)
{
int value;
clrscr();
printf("\n Enter the element to be inserted into the queue:");
scanf("%d", &value);
count++;
if (flag==1)
{
if (count==1)
{
q->front==0;
q->rear=0;
}
else if (q->front==0 && count>1 && q->data[MAXSIZE-1]==-1)
q->front=MAXSIZE-1;
else if (q->front==0 && q->data[MAXSIZE-1]!=-1)
{
printf("\n Queue full.");
getch();
return;
}
else
q->front--;
q->data[q->front]=value;
return;
}
else if (flag==2)
{
if (count==1)
{
q->rear=0;
q->front=0;
}
else if (q->rear==MAXSIZE-1 && q->data[0]==-1)
q->rear=0;
else if (q->rear==MAXSIZE-1 && q->data[0]!=-1)
{
printf("\n Queue full.");
getch();
return;
}
else
q->rear++;
q->data[q->rear]=value;
return;
}
}
/*-----------------------------------------------------------------------*/

/*------------------------DELETE ELEMENT---------------------------------*/
int remove (int flag)
{
if (empty())
{
printf("\n Sorry, queue is empty.");
getch();
return(0);
}
if (flag==1)
{
if (count==1)
{
x=q->data[q->front];
q->data[q->front]=-1;
q->front=q->rear;
count--;
return(x);
}
if (q->front==MAXSIZE-1)
{
x=q->data[q->front];
q->data[q->front]=-1;
q->front=0;
count--;
return(x);
}
x=q->data[q->front];
q->data[q->front]=-1;
q->front++;
count--;
return(x);
}
else if (flag==2)
{
if (count==1)
{
x=q->data[q->rear];
q->data[q->rear]=-1;
q->front=q->rear;
count--;
return(x);
}
if (q->rear==0)
{
x=q->data[q->rear];
q->data[q->rear]=-1;
q->rear=MAXSIZE-1;
count--;
return(x);
}
x=q->data[(q->rear)];
q->data[q->rear]=-1;
q->rear--;
count--;
return(x);
}
}
/*-----------------------------------------------------------------------*/

/*------------------------EMPTY QUEUE------------------------------------*/
int empty()
{
if (q->front==q->rear && q->data[q->front]==-1)
return(TRUE);
else
return(FALSE);
}
/*-----------------------------------------------------------------------*/

/*-------------------------DISPLAY QUEUE---------------------------------*/
void display()
{
int i,fl=0;
printf("\n Total number of elements in queue = %d",count);
if (count==0)
return;
else
{
printf("\n The queue is:");
{
if (count==1)
{
printf(" %d ",q->data[q->front]);
return;
}
i=q->front;
while ( i<=MAXSIZE-1)
{
fl=0;
if (i==q->rear)
{
printf (" %d ", q->data[q->rear]);
fl=1;
break;
}
if (q->data[i]!=-1)
{
printf(" %d ",q->data[i]);
}
i++;
}
if (fl==0)
{
i=0;
while (i<=q->rear)
{
if (q->data[i]!=-1)
{
printf(" %d ",q->data[i]);
}
i++;
}
cout<<endl;
cout<<"Press any key to continue"<<endl;
getch();
}
}
}
} 

0 comments:

Post a Comment

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites More