A difficulty occurs when the first element is removed from a deque but the first
ID: 3862941 • Letter: A
Question
A difficulty occurs when the first element is removed from a deque but the first vector in the internal representation is empty. The pop then causes the first element to be removed from teh second vector. This is potentially costly if a number of pops are performed in sequence. A better alternative is to first move half the elements fromt eh second vector into the first vector, so that subsequent pops are implemented as operations on the first vector. Write implementations for pop_front and pop_back that use this idea. This is for C++.
Explanation / Answer
#include <iostream.h>
#include<stdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
node *next;
node *prev;
}*head, *tail;
/*
*Class Declaration
*/
class dqueue
{
public:
int top1,top2;
void insert();
void del();
void display();
dqueue()
{
top1 = 0;
top2 = 0;
head = NULL;
tail = NULL;
}
};
/*
* main: contains menu
*/
int main()
{
int choice;
dequeue d1;
while(1)
{
count<<” __________________”<<endl;
cout<<”Operations on Dequeue”<<endl;
cout<<” __________________”<<endl;
cout<<”1.Insert Element into the Dequeue”<endl;
cout<<”2.Delete Element from the Dequeue”<<endl;
cout<<”3.Traverse the Dequeue”<<endl;
cout<<”4.Quit”<<endl;
cin>>choice;
cout<<endl;
switch(choice)
{
case 1:
d 1.insert();
break;
case 2:
d1.del();
break;
case 3:
d1.display();
break;
default:
cout<<”Wrong choice”<<endl;
}
}
return 0;
}
/*
* Insert Element in Doubly Ended Queue
*/
void dqueue::insert()
{
struct node *temp;
int ch, value;
if(top1 + top2 >=50)
{
cout<<”Dequeue Overflow”<<endl;
return;
}
if(top1 + top2 >=50)
{
cout<<”Enter the value to be inserted”;
cin>>value;
head = new(struct node);
head->info = value;
head->next = NULL;
head->prev = NULL;
tail = head;
top++;
cout<<”Element Inserted into empty dequeue”<<endl;
}
else
{
while(1)
{
cout<<endl;
cout<<”1.Insert Element at First”<<endl;
cout<<”2.Insert Element at Last”<<endl;
cout<<endl;
cout<<”Enter your choice:”;
cin>>endl;
switch(ch)
{
case 1:
cout<<”Enter the value to be inserted:”;
cin>>value;
temp = new(struct node);
temp->info = value;
temp->next = head;
temp->prev = NULL;
head->prev = temp;
head = temp;
top1++;
break;
case 2:
cout<<”Enter the value to be Inserted:”;
cin>>value;
temp = new(struct node);
temp->info = value;
temp->next = NULL;
temp->prev = tail;
tail->next = temp;
tail = temp;
top2++;
break;
case 3:
return;
break;
default:
cout<<”Wrong Choice”<<endl;
}
}
}
}
/*
*Delete Element in Doubly Ended Queue
*/
void dqueue::del()
{
if(top1 + top2 <=0)
{
cout<<”Dequeue Underflow”<<endl;
return;
}
int ch;
while(1)
{
cout<<endl;
cout<<”1.Delete Element at first:”<<endl;
cout<<”2.Delete Element at last:”<<end;
cout<<”3.Exit”<<endl;
cout<<”Enter your choice:”
cin>>ch;
switch(ch)
{
case 1:
head = head->next;
head->prev = NULL;
top1--;
break;
case 2:
tail = tail->prev;
tail->next = NULL;
top2--;
break;
case 3:
return;
break;
default:
cout<<”Wrong choice”<<endl;
}
}
}
/*
* Display Doubly Ended Queue
*/
void dqueue::display()
{
struct node *temp;
int ch;
if(top1 + top2 <= 0)
{
cout<<”Dequeue Underflow”<<endl;
return;
}
while(1)
{
cout<<endl;
cout<<”1.Display Dequeue from Beginning”<<endl;
cout<<”2.Display Dequeue from End”<<endl;
cout<<endl;
cout<<”Enter Your choice:”;
cin>>ch;
cout<<endl;
switch(ch)
{
case 1:
temp = head;
cout<<”Dequeue from beginning:”<<endl;
while(temp != NULL)
{
cout<<temp->info<<” “;
temp = temp->next;
}
cout<<endl;
break;
case 2:
cout<<”Dequeue from End:”<<endl;
temp = tail;
while(temp != NULL)
{
cout<<temp->info<<” “;
temp = temp->prev;
}
temp = tail;
cout<<endl;
break;
case 3:
return;
break;
default:
cout<<”Wrong choice”<<endl;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.