Practical No: -12
Experiment No. 12: A double-ended queue(deque) is a linear list in which additions and deletions
may be made at either end. Obtain a data representation mapping a deque into a one-dimensional
array. Write C++ program to simulate deque with functions to add and delete elements from either
end of the deque.
Code:
using namespace std;
#include<iostream>
#include<stdio.h>
#include<process.h>
#define MAX 30
typedef struct dequeue
{
int data[MAX];
int rear,front;
}dequeue;
void initialize(dequeue *p);
int isEmpty(dequeue *p);
int isFull(dequeue *p);
void enqueueRear(dequeue *p,int x);
void enqueueFront(dequeue *p,int x);
int dequeueFront(dequeue *p);
int dequeueRear(dequeue *p);
void display(dequeue *p);
main()
{
int i,x,choice,n;
dequeue q;
initialize(&q);
do
{
cout<<"\n 1.Create \n 2.Insert(rear) \n 3.Insert(front) \n 4.Delete(rear) \n 5.Delete(front)";
cout<<"\n 6.Display \n 7.Exit \n\n Enter your choice:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\n Enter number of elements:";
cin>>n;
initialize(&q);
cout<<"\n Enter the elements:";
for(i=0;i<n;i++)
{
cin>>x;
if(isFull(&q))
{
cout<<"\n Queue is full!!\n";
exit(0);
}
enqueueRear(&q,x);
}
break;
case 2:
cout<<"\n Enter element to be inserted:\n";
cin>>x;
if(isFull(&q))
{
cout<<"\n Queue is full!!\n";
exit(0);
}
enqueueRear(&q,x);
break;
case 3:
cout<<"\n Enter the element to be inserted:\n";
cin>>x;
if(isFull(&q))
{
cout<<"\n Queue is full!!\n";
exit(0);
}
enqueueFront(&q,x);
break;
case 4:
if(isEmpty(&q))
{
cout<<"\n Queue is empty!!\n";
exit(0);
}
x=dequeueRear(&q);
cout<<"\n Element deleted is:\n"<<x;
break;
case 5:
if(isEmpty(&q))
{
cout<<"\n Queue is empty!!\n";
exit(0);
}
x=dequeueFront(&q);
cout<<"\n Element deleted is:\n"<<x;
break;
case 6:
display(&q);
break;
default:
break;
}
}
while(choice!=7);
}
void initialize(dequeue *P)
{
P->rear=-1;
P->front=-1;
}
int isEmpty(dequeue *P)
{
if(P->rear==-1)
return(1);
return(0);
}
int isFull(dequeue *P)
{
if((P->rear+1)%MAX==P->front)
return(1);
return(0);
}
void enqueueRear(dequeue *P,int x)
{
if(isEmpty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->rear=(P->rear+1)%MAX;
P->data[P->rear]=x;
}
}
void enqueueFront(dequeue *P,int x)
{
if(isEmpty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->front=(P->front-1+MAX)%MAX;
P->data[P->front]=x;
}
}
int dequeueFront(dequeue *P)
{
int x;
x=P->data[P->front];
if(P->rear==P->front)
initialize(P);
else
P->front=(P->front+1)%MAX;
return(x);
}
int dequeueRear(dequeue *P)
{
int x;
x=P->data[P->rear];
if(P->rear==P->front)
initialize(P);
else
P->rear=(P->rear-1+MAX)%MAX;
return(x);
}
void display(dequeue *P)
{
if(isEmpty(P))
{
cout<<"\n Queue is empty!!";
exit(0);
}
int i;
i=P->front;
while(i!=P->rear)
{
cout<<" "<<P->data[i];
i=(i+1)%MAX;
}
cout<<" "<<P->data[P->rear];
}
