16.13 Homework9 (due Apr 8) Students This content is controlled by your instruct
ID: 3811901 • Letter: 1
Question
16.13 Homework9 (due Apr 8) Students This content is controlled by your instructor, and is not zyBooks content. Direct questions or concerns about this content to your instructor lf you have any technical issues with the zyLab submission system use the "Trouble with lab?" button at the bottom of the lab Implement a Priority Queue for strings. A priority queue is similar to a regular queue except each item added to the queue also has an associated priority. For this problem, make the priority an integer where 0 is the highest priority and larger values are increasingly lower in priority The remove function should return and remove the item that has the highest priority For example: q add ("X", 10); q add("Y", 1); q add ("Z", 3); cout q. remove Returns Y cout q.remove Returns Z Returns X cout q remove You can implement the priority queue by performing a linear search in the remove function. Hint: Take a look at the Linked List code example from 03/30, which can downloaded from D2L. Reusing the code example is acceptable and modifying it is acceptable. You are expected to use pointers You will get a 0 if you use STL:priorityqueue or any other already-implemented priority queue data structure. Important: Make sure to use the template provided since the test cases depend on it 16.13.1: Homework9 (due Apr 8) Lab Submission main Loppiefault template 1 #include kiostream 2 #includeExplanation / Answer
/*
* C++ Program to Implement Priority Queue
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
class node
{
public:
int priority;
string data;
node *link;
};
/*
* Class Priority Queue
*/
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
/*
* Insert into Priority Queue
*/
void add(string item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->data = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while (q->link != NULL && q->link->priority <= priority)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
}
/*
* Delete from Priority Queue
*/
string remove()
{
node *tmp;
string s;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->data<<endl;
s= tmp->data;
front = front->link;
free(tmp);
}
return s;
}
/*
* Print Priority Queue
*/
void display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty ";
else
{ cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->data<<endl;
ptr = ptr->link;
}
}
}
};
/*
* Main
*/
int main()
{
int choice, priority;
string item;
Priority_Queue pq;
do
{
cout<<"1.ADD ";
cout<<"2.Remove ";
cout<<"3.Display ";
cout<<"4.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.add(item, priority);
break;
case 2:
pq.remove();
break;
case 3:
pq.display();
break;
case 4:
break;
default :
cout<<"Wrong choice ";
}
}
while(choice != 4);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.