Priority Queue ใช้ Linked List ในภาษา C

กำหนดข้อมูลและ priority (integer) สร้าง linked list ตาม priority แสดงผล

Queue เป็น FIFO แต่ Priority Queue เพิ่ม/ลบตาม priority กฎ:

• Priority สูงสุด (เลขน้อย) ทำงานก่อน
• Priority เท่ากัน ทำงานตามลำดับที่เพิ่ม

โหนด linked list สำหรับ priority queue มี 3 ส่วน:

• Data - ค่าจำนวนเต็ม
• Address - ที่อยู่โหนดถัดไป
• Priority - ค่า priority (0-10: 0=สูงสุด)

อัลกอริทึม

Node struct: data, priority, next
newNode(d, p): สร้างโหนดใหม่
peek(head): คืนค่า data ของ head
pop(head): ลบ head, เลื่อน head ไป next
push(head, d, p): แทรกโหนดตาม priority (น้อยกว่า = สูงกว่า)
isEmpty(head): ตรวจสอบ head == NULL

ตัวอย่างโค้ด

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

เอาต์พุต

2 7 1 3