Cのリンクリストを使用した優先キュー

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

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

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

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

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

例

入力

出力

アルゴリズム

Start
Step 1-> Declare a struct node
   Declare data, priority
   Declare a struct node* next
Step 2-> In function Node* newNode(int d, int p)
   Set Node* temp = (Node*)malloc(sizeof(Node))
   Set temp->data = d
   Set temp->priority = p
   Set temp->next = NULL
   Return temp
Step 3-> In function int peek(Node** head)
   return (*head)->data
Step 4-> In function void pop(Node** head)
   Set Node* temp = *head
   Set (*head) = (*head)->next
   free(temp)
Step 5-> In function push(Node** head, int d, int p)
   Set Node* start = (*head)
   Set Node* temp = newNode(d, p)
   If (*head)->priority > p then,
      Set temp->next = *head
      Set (*head) = temp
   Else
   Loop While start->next != NULL && start->next->priority < p
      Set start = start->next
      Set temp->next = start->next
      Set start->next = temp
Step 6-> In function int isEmpty(Node** head)
   Return (*head) == NULL
Step 7-> In function int main()
   Set Node* pq = newNode(7, 1)
   Call function push(&pq, 1, 2)
   Call function push(&pq, 3, 3)
   Call function push(&pq, 2, 0)
   Loop While (!isEmpty(&pq))
   Print the results obtained from peek(&pq)
   Call function pop(&pq)
Stop

例

#include <stdio.h>
#include <stdlib.h>
// priority Node
typedef struct node {
   int data;
   int priority;
   struct node* next;
} Node;
Node* newNode(int d, int p) {
   Node* temp = (Node*)malloc(sizeof(Node));
   temp->data = d;
   temp->priority = p;
   temp->next = NULL;
   return temp;
}
int peek(Node** head) {
   return (*head)->data;
}
void pop(Node** head) {
   Node* temp = *head;
   (*head) = (*head)->next;
   free(temp);
}
void push(Node** head, int d, int p) {
   Node* start = (*head);
   Node* temp = newNode(d, p);
   if ((*head)->priority > p) {
      temp->next = *head;
      (*head) = temp;
   } else {
      while (start->next != NULL &&
      start->next->priority < p) {
         start = start->next;
      }
      // Either at the ends of the list
      // or at required position
      temp->next = start->next;
      start->next = temp;
   }
}
// Function to check the queue is empty
int isEmpty(Node** head) {
   return (*head) == NULL;
}
// main function
int main() {
   Node* pq = newNode(7, 1);
   push(&pq, 1, 2);
   push(&pq, 3, 3);
   push(&pq, 2, 0);
   while (!isEmpty(&pq)) {
      printf("%d ", peek(&pq));
      pop(&pq);
   }
   return 0;
}

出力

2 7 1 3