How to implement priority queue in C++?

Question

I am implementing a train boarding system using priority queue. I have the working code but I need to make the following changes..

The priority levels will be : High, Medium and Low. So the passenger should input his/her name and the priority level. The train can have up to 30 passengers. In the end I will sort the passengers accordingly... Here what I have so far my problem is taking strings as arguments instead of the integers I have now.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;
#define High 1
#define Medium 2
#define Low 3
/*
* Node Declaration
*/
struct node
{
    int priority;
    int info;
    struct node *link;
};
/*
* Class Priority Queue
*/
class Priority_Queue
{
private:
    node *front;
public:
    Priority_Queue()
    {
        front = NULL;
    }
    /*
    * Insert into Priority Queue
    */
    void insert(int item, int priority)
    {
        node *tmp, *q;
        tmp = new node;
        tmp->info = 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
    */
    void del()
    {
        node *tmp;
        if (front == NULL)
            cout << "Queue Underflow\n";
        else
        {
            tmp = front;
            cout << "Deleted item is: " << tmp->info << endl;
            front = front->link;
            free(tmp);
        }
    }
    /*
    * Print Priority Queue
    */
    void display()
    {
        node *ptr;
        ptr = front;
        if (front == NULL)
            cout << "Queue is empty\n";
        else
        {
            cout << "Queue is :\n";
            cout << "Priority       Item\n";
            while (ptr != NULL)
            {
                cout << ptr->priority << "                 " << ptr->info << endl;
                ptr = ptr->link;
            }
        }
    }
};
/*
* Main
*/
int main()
{
    int choice, item, priority;
    Priority_Queue pq;
    do
    {
        cout << "1.Insert\n";
        cout << "2.Delete\n";
        cout << "3.Display\n";
        cout << "4.Quit\n";
        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.insert(item, priority);
            break;
        case 2:
            pq.del();
            break;
        case 3:
            pq.display();
            break;
        case 4:
            break;
        default:
            cout << "Wrong choice\n";
        }
    } while (choice != 4);
    return 0;
}

Answer 1

Here you can use mapping.

  int main()
{
    int choice, item;
   string priority;
   map<string,int>m;
   m["High"]=1;
   m["Low"]=3;
   m["Medium"]=2;
    Priority_Queue pq;
    do
    {
        cout << "1.Insert\n";
        cout << "2.Delete\n";
        cout << "3.Display\n";
        cout << "4.Quit\n";
        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.insert(item, m[priority]);//look change
    //... rest of the code will same

and you need to include #include<map> also. Thank you.

Answer 2

I would avoid using string values for the queue and just translate plain-text priorities to the respective integer value, think

int ParsePriority(string plainTextPriority)
{
    switch(plainTextPriority) {
        case "High": return 1;
        case "Medium": return 2;
        case "Low": return 3;
    }
    throw "Unknown priority class";
}

You'll then be able to use the priority values like you did before.

case 1:
    cout << "Input the item value to be added in the queue : ";
    cin >> item;
    cout << "Enter its priority : ";
    do {
        string plainTextPriority;
        cin >> plainTextPriority;
        try {
            priority = ParsePriority(plainTextPriority)
        }
        catch {
            priority = 0;
            cout << "Could not parse the priority, please enter one of High, Medium, Low" << endl;
        }
    } while (priority == 0);
    pq.insert(item, priority);
    break;

I added the loop to take the case that a value that does not represent a valid priority has been entered into account.