Question

(Deque) A deque is a data structure consisting of a list of items on which the following operations are possible: a. push (x) : Insert item x on the front end of the deque. b. pop ): Remove the front item from the deque and return it. c. inject(x): Insert item x on the rear end of the deque. d. eject ): Remove the rear item from the deque and return it. Write routines to support the deque that take O(1) time per operation (the operations that take O(n) will be given 0 point). Write an application file a2q3.cpp containing mainO function to test if Deque class works correctly Three files should be submitted for this program question. 1) the file Deque.h which contains the definition and implementation of Deque class template, 2) the application file a2q3.cpp containing main () function, 3) a script file a2q3result containing result. Here are the sample runs: Push values in deque: 1 2 3 4 5 Inject values in deque: 1234 5 The front element popped out is 5 The rear element ejected out is 5 The front element popped out is 4 The rear element ejected out is 4

Answer 1

ANS.......................................................................................

DEQUEUE.CPP:
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;

struct node
{
int data;
node *next;
node *prev;
}*front = NULL,*rear = NULL,*temp1 = NULL,*temp2 = NULL;

void push(int x)
{
temp1 = new node;
temp1->data = x;
  
if(front == NULL)
{

front = rear = temp1;
rear->next = NULL;
rear->prev = NULL;
}
else
{
temp1->next = front;
front->prev = temp1;
temp1->prev = NULL;
front = temp1;
}
}

void inject(int x)
{
temp1 = new node;
temp1->data = x;
temp1->next = NULL;
if(front == NULL)
{
front = rear = temp1;
rear->next = NULL;
rear->prev = NULL;
}
else
{
temp1->prev = rear;
rear->next = temp1;
rear = temp1;
}
}

int pop()
{
int x;
if(front == NULL)
{
cout<<"Queue is empty!! ";
}
else
{
temp2 = front;
x = temp2->data;
front = front->next;
if(front==NULL){
rear = NULL;
}else{
front->prev = NULL;
}
delete(temp2);
return(x);
}
}

int eject()
{
int x;
if(front == NULL)
{
cout<<"Queue is empty!! ";
}
else
{
temp2 = rear;
x = temp2->data;
rear = rear->prev;
if(rear==NULL){
front = NULL;
}else{
rear->next = NULL;
}
delete(temp2);
return(x);
}
}

MAIN.CPP:

In the main function we would be calling each of these functions n number of times, n being the number of values the user needs to push. PFB the a2q3.cpp file:

#include<iostream>
#include<stdio.h>
#include<conio.h>

#include "Deque.h"
using namespace std;

int main()
{
int n1,c1 = 0,x1;
cout<<"Enter the number of values to be pushed into queue ";
cin>>n1;
while (c1 < n1)
{
cout<<"Push the values in the Deque ";
cin>>x1;
push(x1);
c1++;
}

while(c1>0)
{
cout<<" The front element popped out is "<<pop()<<endl;
c1--;
}

int n2,c2 = 0,x2;
cout<<"Enter the number of values to be pushed into queue ";
cin>>n2;
while (c2 < n2)
{
cout<<"Inject the values in the Deque ";
cin>>x2;
inject(x2);
c2++;
}
  
while(c2>0)
{
  
cout<<" The rear element ejected out is "<<eject()<<endl;
c2--;
}
getch();
}