C에서 연결 목록을 사용하는 우선 순위 큐

정수값으로 데이터와 우선순위를 부여받고 주어진 우선순위에 따라 연결리스트를 생성하여 결과를 출력하는 작업입니다.

큐는 먼저 삽입된 요소가 가장 먼저 제거되는 FIFO 데이터 구조입니다. 우선 순위 큐는 우선 순위에 따라 요소를 삽입하거나 삭제할 수 있는 큐 유형입니다. 큐, 스택 또는 연결 목록 데이터 구조를 사용하여 구현할 수 있습니다. 우선 순위 대기열은 다음 규칙에 따라 구현됩니다 -

• 우선순위가 가장 높은 데이터 또는 요소가 우선순위가 가장 낮은 데이터 또는 요소보다 먼저 실행됩니다.
• 두 요소가 순서대로 실행되는 것보다 우선순위가 같으면 목록에 추가됩니다.

우선 순위 대기열을 구현하기 위한 연결 목록의 노드는 세 부분으로 구성됩니다. -

• 데이터 − 정수 값을 저장합니다.
• 주소 − 다음 노드의 주소를 저장합니다.
• 우선순위 −정수 값인 우선 순위를 저장합니다. 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