優先キューを実装するC++プログラム

挿入が一方の端（後部）で行われ、削除がもう一方の端（前部）から行われるFIFOとして実装されるキュー。入力した最初の要素が最初に削除されます。

キュー操作は

• EnQueue（intデータ） ：後端への挿入

• int DeQueue（） ：フロントエンドからの削除

ただし、優先度付きキューは先入れ先出し法ではなく、緊急性に基づいて各要素に優先度があります。

同じ優先度のアイテムは、先入れ先出しサービスベースで処理されます。

優先度の高いアイテムは、優先度の低い他のアイテムよりも先に処理されます。

クラスの説明

Begin
   class Priority_Queue has following functions:
   function insert() to insert items at priority queue with their priorities:
      1) If queue is empty insert data from the left end of the queue.
      2) If queue is having some nodes then insert the new node at the end of those nodes having priority
         same with the new node and also before all the nodes having priority lesser than the
         current priority of the new node.
      function del() to delete items from queue.
   If queue is completely empty, print underflow otherwise delete the front element and update front.
End

例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct n // node declaration {
   int p;
   int info;
   struct n *l;
};
class Priority_Queue {
   private:
      //Declare a front pointer f and initialize it to NULL.
      n *f;
   public:
      Priority_Queue() //constructor {
         f = NULL;
      }
      void insert(int i, int p) {
         n *t, *q;
         t = new n;
         t->info = i;
         t->p = p;
         if (f == NULL || p < f->p) {
            t->l= f;
            f = t;
         } else {
            q = f;
            while (q->l != NULL && q->l->p <= p)
               q = q->l;
               t->l = q->l;
               q->l = t;
         }
      }
      void del() {
         n *t;
         if(f == NULL) //if queue is null
            cout<<"Queue Underflow\n";
         else {
            t = f;
            cout<<"Deleted item is: "<<t->info<<endl;
            f = f->l;
            free(t);
         }
      }
      void show() //print queue {
         n *ptr;
         ptr = f;
         if (f == NULL)
            cout<<"Queue is empty\n";
         else {
            cout<<"Queue is :\n";
            cout<<"Priority Item\n";
            while(ptr != NULL) {
               cout<<ptr->p<<" "<<ptr->info<<endl;
               ptr = ptr->l;
            }
         }
      }
};
int main() {
   int c, i, p;
   Priority_Queue pq;
   Do//perform switch opeartion {
      cout<<"1.Insert\n";
      cout<<"2.Delete\n";
      cout<<"3.Display\n";
      cout<<"4.Exit\n";
      cout<<"Enter your choice : ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Input the item value to be added in the queue : ";
            cin>>i;
            cout<<"Enter its priority : ";
            cin>>p;
            pq.insert(i, p);
            break;
         case 2:
            pq.del();
            break;
         case 3:
            pq.show();
            break;
         case 4:
            break;
         default:
         cout<<"Wrong choice\n";
      }
   }
   while(c != 4);
   return 0;
}

出力

1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 7
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 6
Enter its priority : 1
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 3
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Queue is :
Priority Item
1 6
2 7
3 3
3 4
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4