Implement a Priority Queue for strings. A priority queue is similar to a regular

Question

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:

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.

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node
{
   int priority;
   string name;
   struct node *link;
};
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
void insert(string name, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->name = name;
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;
}
}
void del()
{
node *tmp;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->name<<endl;
front = front->link;
free(tmp);
}
}
};
int main()
{
int choice, priority;
string name;
Priority_Queue pq;
do
{
cout<<"1.Insert ";
cout<<"2.Delete ";
cout<<"3.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>name;
cout<<"Enter its priority : ";
cin>>priority;
pq.insert(name, priority);
break;
case 2:
pq.del();
break;
case 3:
break;
default :
cout<<"Wrong choice ";
}
}
while(choice != 3);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.