C++で二重にリンクされたリストを使用した優先キュー

データと優先度は整数値として与えられ、タスクは与えられた優先度に従って二重にリンクされたリストを作成し、結果を表示することです。

キューはFIFOデータ構造であり、最初に挿入された要素が最初に削除されます。優先度付きキューは、優先度に応じて要素を挿入または削除できるキューの一種です。キュー、スタック、またはリンクリストのデータ構造を使用して実装できます。優先キューは、次のルールに従って実装されます-

• 優先度が最も高いデータまたは要素は、優先度が最も低いデータまたは要素の前に実行されます。
• 2つの要素の優先度が、順番に実行される要素と同じである場合、それらはリストに追加されます。

優先キューを実装するための二重リンクリストのノードには、3つの部分が含まれます-

• データ-整数値を格納します。
• 次のアドレス-次のノードのアドレスを保存します
• 前のアドレス-前のノードのアドレスを保存します
• 優先度-整数値である優先度を格納します。範囲は0〜10で、0は最高の優先度を表し、10は最低の優先度を表します。

例

入力-

出力-

アルゴリズム

Start
Step 1-> Declare a struct Node
   Declare info, priority
   Declare struct Node *prev, *next
Step 2-> In function push(Node** fr, Node** rr, int n, int p)
   Set Node* news = (Node*)malloc(sizeof(Node))
   Set news->info = n
   Set news->priority = p
   If *fr == NULL then,
      Set *fr = news
      Set *rr = news
      Set news->next = NULL
   Else If p <= (*fr)->priority then,
      Set news->next = *fr
      Set (*fr)->prev = news->next
      Set *fr = news
   Else If p > (*rr)->priority then,
      Set news->next = NULL
      Set (*rr)->next = news
      Set news->prev = (*rr)->next
      Set *rr = news
   Else
      Set Node* start = (*fr)->next
   Loop While start->priority > p
      Set start = start->next
      Set (start->prev)->next = news
      Set news->next = start->prev
      Set news->prev = (start->prev)->next
      Set start->prev = news->next
Step 3-> In function int peek(Node *fr)
   Return fr->info
Step 4-> In function bool isEmpty(Node *fr)
   Return (fr == NULL)
Step 5-> In function int pop(Node** fr, Node** rr)
   Set Node* temp = *fr
   Set res = temp->info
   Set (*fr) = (*fr)->next
   free(temp)
   If *fr == NULL then,
      *rr = NULL
   Return res
Step 6-> In function int main()
   Declare and assign Node *front = NULL, *rear = NULL
   Call function push(&front, &rear, 4, 3)
   Call function push(&front, &rear, 3, 2)
   Call function push(&front, &rear, 5, 2)
   Call function push(&front, &rear, 5, 7)
   Call function push(&front, &rear, 2, 6)
   Call function push(&front, &rear, 1, 4)
   Print the results obtained from calling the function pop(&front, &rear)
   Print the results obtained from calling the function peek(front)
Stop

例

#include <bits/stdc++.h>
using namespace std;
//doubly linked list node
struct Node {
   int info;
   int priority;
   struct Node *prev, *next;
};
//inserting a new Node
void push(Node** fr, Node** rr, int n, int p) {
   Node* news = (Node*)malloc(sizeof(Node));
   news->info = n;
   news->priority = p;
   // if the linked list is empty
   if (*fr == NULL) {
      *fr = news;
      *rr = news;
      news->next = NULL;
   } else {
      // If p is less than or equal front
      // node's priority, then insert the node
      // at front.
      if (p <= (*fr)->priority) {
         news->next = *fr;
         (*fr)->prev = news->next;
         *fr = news;
      } else if (p > (*rr)->priority) {
         news->next = NULL;
         (*rr)->next = news;
         news->prev = (*rr)->next;
         *rr = news;
      } else {
         // Finding the position where we need to
         // insert the new node.
         Node* start = (*fr)->next;
         while (start->priority > p)
         start = start->next;
         (start->prev)->next = news;
         news->next = start->prev;
         news->prev = (start->prev)->next;
         start->prev = news->next;
      }
   }
}
//the last value
int peek(Node *fr) {
   return fr->info;
}
bool isEmpty(Node *fr) {
   return (fr == NULL);
}
int pop(Node** fr, Node** rr) {
   Node* temp = *fr;
   int res = temp->info;
   (*fr) = (*fr)->next;
   free(temp);
   if (*fr == NULL)
   *rr = NULL;
   return res;
}
// main function
int main() {
   Node *front = NULL, *rear = NULL;
   push(&front, &rear, 4, 3);
   push(&front, &rear, 3, 2);
   push(&front, &rear, 5, 2);
   push(&front, &rear, 5, 7);
   push(&front, &rear, 2, 6);
   push(&front, &rear, 1, 4);
   printf("%d\n", pop(&front, &rear));
   printf("%d\n", peek(front));
   return 0;
}

出力

5
3