如何在C++中實現優先級隊列？

Question

我正在實施一個使用優先隊列的火車登機系統。我有工作代碼，但我需要做出以下更改。

優先級別爲：高，中和低。所以乘客應該輸入他/她的名字和優先級。火車可以有多達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>也。 謝謝。