C++中如何实现优先级队列？

Question

我正在使用优先队列实现火车登机系统。我有工作代码，但我需要进行以下更改..

优先级将是：高、中和低。所以乘客应该输入his/her姓名和优先级。火车最多可容纳30名乘客。最后我会相应地对乘客进行排序......到目前为止我的问题是将字符串作为参数而不是我现在拥有的整数。

#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

我会避免为队列使用字符串值，只是将纯文本优先级转换为相应的整数值，想想

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

然后您将能够像以前一样使用优先级值。

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;

我添加了循环以处理输入了不代表有效优先级的值的情况。

Answer 2

这里可以使用映射。

  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

您还需要包括 #include<map>。谢谢。

C++中如何实现优先级队列？

How to implement priority queue in C++?

c++

priority-queue