Language is C++. Write a queue class to implement a queue using a 2 directional
ID: 3808307 • Letter: L
Question
Language is C++.
Write a queue class to implement a queue using a 2 directional linked list.
Test the program with the following sequence of code:
queue myQ; ( Use default constructor to initialize front and end to NULL. )
cout<< myQ.size() << endl; // number of elements in queue
myQ.dequeue(); // Try to deqeue when the queue is empty. Should catch UNDERFLOW
myQ.enqueue("Fred");
myQ.enqueue("Liv");
myQ.enqueue("Julie");
myQ.enqueue("Rich");
myQ.enqueue("William");
myQ.enqueue("Olo");
myQ.enqueue("Xi");
myQ.enqueue("Chu");
myQ.enqueue("Annie");
myQ.enqueue("Carlos");
myQ.enqueue("Tuyet");
myQ.enqueue("Sue");
cout<< myQ.front() << endl; // name at front, if not empty
cout<< myQ.end() << endl; // name at end, if not empty
cout<< myQ.size() << endl; // number of elements in queue
cout << myQ.dequeue() << endl;
cout << myQ.dequeue() << endl;
cout << myQ.dequeue() << endl;;
myQ.enqueue("Olive");
myQ.enqueue("Jim");
cout << myQ.dequeue() << endl;
cout << myQ.dequeue() << endl;
cout<< myQ.front() << endl; // name at front, if not empty
cout<< myQ.end() << endl; // name at end, if not empty
cout<< myQ.size() << endl; // number of elements in queue
Explanation / Answer
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
//Node Declaration
struct node
{
string info;
node *next;
node *prev;
}*head, *tail;
//Class Declaration
class dqueue
{
public:
int top1, top2;
void insert();
void del();
void display();
void displaySize();
//Default constructor
dqueue()
{
top1 = 0;
top2 = 0;
head = NULL;
tail = NULL;
}//End of constructor
};//End of class
//Main function
int main()
{
int choice;
//class object created
dqueue dl;
//Loops till user choice is 5
while (1)
{
cout<<" -------------"<<endl;
cout<<"Operations on Deque"<<endl;
cout<<" -------------"<<endl;
cout<<"1. Insert data into the Deque"<<endl;
cout<<"2. Delete data from the Deque"<<endl;
cout<<"3. Display Deque"<<endl;
cout<<"4. Size"<<endl;
cout<<"5. Quit"<<endl;
//Accepts user choice
cout<<"Enter your Choice: ";
cin>>choice;
cout<<endl;
switch(choice)
{
case 1:
dl.insert();
break;
case 2:
dl.del();
break;
case 3:
dl.display();
break;
case 4:
dl.displaySize();
break;
case 5:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}//End of switch case
}//End of while
return 0;
}//End of function
//Insert Element in Doubly Ended Queue
void dqueue::insert()
{
struct node *temp;
int ch;
string value;
//Validates dqueue overflow
if (top1 + top2 >= 50)
{
cout<<"Dequeue Overflow"<<endl;
return;
}//End of if
//if top1 + top2 is 0 then first element
if (top1 + top2 == 0)
{
cout<<"Enter the value to be inserted: ";
cin>>value;
head = new (struct node);
head->info = value;
head->next = NULL;
head->prev = NULL;
tail = head;
top1++;
cout<<"Element Inserted into empty deque"<<endl;
}//End of if
//Otherwise
else
{
//Loops till user choice is 3
while (1)
{
cout<<endl;
//Insert options
cout<<"1.Insert Element at first"<<endl;
cout<<"2.Insert Element at last"<<endl;
cout<<"3.Exit"<<endl;
cout<<endl;
//Accepts user choice for insert
cout<<"Enter Your Choice: ";
cin>>ch;
cout<<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;
}//End of switch
}//End of while
}//End of else
}//End of function
//Delete Element in Doubly Ended Queue
void dqueue::del()
{
//Checks for underflow condition
if (top1 + top2 <= 0)
{
cout<<"Deque Underflow"<<endl;
return;
}//End of if
int ch;
//Loops till user choice is 3
while (1)
{
cout<<endl;
//Delete options
cout<<"1.Delete Element at first"<<endl;
cout<<"2.Delete Element at last"<<endl;
cout<<"3.Exit"<<endl;
cout<<endl;
//Accept user choice for delete
cout<<"Enter Your Choice: ";
cin>>ch;
cout<<endl;
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;
}//End of switch
}//End of while
}//End of function
//Function to display size
void dqueue::displaySize()
{
//Creates a temporary node
struct node *temp;
//Initialize the counter to zero
int counter = 0;
//Validates the underflow condition
if (top1 + top2 <= 0)
{
cout<<"Deque Underflow"<<endl;
return;
}//End of if
//Assigns the head position to temporary node
temp = head;
//Loops till node is nut null
while (temp != NULL)
{
//Increase the counter
counter++;
//Move next
temp = temp->next;
}//End of while
cout<<" Number of elements = "<<counter;
}//End of function
//Display Doubly Ended Queue
void dqueue::display()
{
//Creates a temporary node
struct node *temp;
int ch;
//Checks the underflow condition
if (top1 + top2 <= 0)
{
cout<<"Deque Underflow"<<endl;
return;
}//End of if
//Loops till user choice is 3
while (1)
{
cout<<endl;
//Display menu
cout<<"1.Display Deque from Beginning"<<endl;
cout<<"2.Display Deque from End"<<endl;
cout<<"3.Exit"<<endl;
cout<<endl;
//Accepts user choice for display
cout<<"Enter Your Choice: ";
cin>>ch;
cout<<endl;
switch (ch)
{
case 1:
//Assigns head to the temporary node
temp = head;
cout<<"Deque from Beginning:"<<endl;
//Loops till node is nut null
while (temp != NULL)
{
//Displays the data
cout<<temp->info<<" ";
//Move next
temp = temp->next;
}//End of while
cout<<endl;
break;
case 2:
cout<<"Deque from End:"<<endl;
//Assigns tail to the node
temp = tail;
//Loops till node is nut null
while (temp != NULL)
{
//Displays information
cout<<temp->info<<" ";
//Moves previous
temp = temp->prev;
}//End of while
temp = tail;
cout<<endl;
break;
case 3:
return;
break;
default:
cout<<"Wrong Choice"<<endl;
}//End of switch
}//End of while
}//End of function
Output:
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 1
Enter the value to be inserted: This
Element Inserted into empty deque
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 1
1.Insert Element at first
2.Insert Element at last
3.Exit
Enter Your Choice: 1
Enter the value to be inserted: is
1.Insert Element at first
2.Insert Element at last
3.Exit
Enter Your Choice: 2
Enter the value to be inserted: test
1.Insert Element at first
2.Insert Element at last
3.Exit
Enter Your Choice: 3
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 3
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
Enter Your Choice: 1
Deque from Beginning:
is This test
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
Enter Your Choice: 2
Deque from End:
test This is
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
Enter Your Choice: 3
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 2
1.Delete Element at first
2.Delete Element at last
3.Exit
Enter Your Choice: 1
1.Delete Element at first
2.Delete Element at last
3.Exit
Enter Your Choice: 3
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 3
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
Enter Your Choice: 1
Deque from Beginning:
This test
1.Display Deque from Beginning
2.Display Deque from End
3.Exit
Enter Your Choice: 3
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 4
Number of elements = 2
-------------
Operations on Deque
-------------
1. Insert data into the Deque
2. Delete data from the Deque
3. Display Deque
4. Size
5. Quit
Enter your Choice: 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.