Priority Queue dùng Linked List trong C

Cho dữ liệu và ưu tiên (số nguyên), tạo linked list theo ưu tiên và hiển thị.

Queue = FIFO (vào trước ra trước). Priority Queue: chèn/xóa theo ưu tiên. Triển khai bằng queue, stack, linked list. Quy tắc:

• Ưu tiên cao (số nhỏ) thực thi trước.
• Ưu tiên bằng nhau → theo thứ tự chèn (FIFO).

Node linked list cho Priority Queue có 3 phần:

• Data: giá trị nguyên.
• Address (next): địa chỉ node tiếp theo.
• Priority: độ ưu tiên (0-10, 0 = cao nhất).

Ví dụ

Đầu vào: (7,1), (1,2), (3,3), (2,0) → Đầu ra: 2 7 1 3 (theo ưu tiên 0,1,2,3)

Thuật toán

B1: Struct node { data, priority, next }
B2: newNode(d,p): cấp phát node, gán data, priority, next=NULL
B3: peek(head): trả về head->data
B4: pop(head): xóa head, head = head->next, free(old)
B5: push(head, d, p):
      start = head
      temp = newNode(d,p)
      if head->priority > p:  // ưu tiên cao hơn (số nhỏ hơn)
        temp->next = head; head = temp
      else:
        while start->next != NULL && start->next->priority < p:
          start = start->next
        temp->next = start->next
        start->next = temp
B6: isEmpty(head): return head == NULL
B7: main: tạo pq = newNode(7,1), push(1,2), push(3,3), push(2,0)
      while !isEmpty: print peek, pop

Ví dụ mã nguồn

#include <stdio.h>
#include <stdlib.h>

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;
        temp->next = start->next;
        start->next = temp;
    }
}

int isEmpty(Node** head) { return *head == NULL; }

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;
}

Kết quả đầu ra

2 7 1 3