Priority Queue โดยใช้ Doubly Linked List ใน C++

โจทย์

เราได้รับข้อมูลและลำดับความสำคัญเป็นค่าจำนวนเต็ม งานคือสร้าง doubly linked list ตามลำดับความสำคัญที่กำหนดและแสดงผลลัพธ์

Queue เป็นโครงสร้างข้อมูล FIFO ซึ่งองค์ประกอบที่แทรกเข้ามาก่อนจะถูกลบออกก่อน Priority Queue เป็นประเภทของ queue ที่องค์ประกอบสามารถแทรกหรือลบได้ขึ้นอยู่กับลำดับความสำคัญ สามารถนำไปใช้โดยใช้ queue, stack หรือ linked list Priority queue ถูกนำไปใช้โดยปฏิบัติตามกฎเหล่านี้ -

• ข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญสูงสุดจะถูกดำเนินการก่อนข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญต่ำสุด
• ถ้าสององค์ประกอบมีลำดับความสำคัญเท่ากัน พวกเขาจะถูกดำเนินการตามลำดับที่ถูกเพิ่มในรายการ

โหนดของ doubly linked list สำหรับนำ priority queue ไปใช้จะมี 3 ส่วน -

• Data - จะเก็บค่าจำนวนเต็ม
• Next Address - จะเก็บที่อยู่ของโหนดถัดไป
• Previous Address - จะเก็บที่อยู่ของโหนดก่อนหน้า
• Priority - จะเก็บลำดับความสำคัญซึ่งเป็นค่าจำนวนเต็ม สามารถอยู่ระหว่าง 0-10 โดย 0 แสดงลำดับความสำคัญสูงสุด และ 10 แสดงลำดับความสำคัญต่ำสุด

ตัวอย่าง

อินพุต -

เอาต์พุต -

อัลกอริทึม

เริ่ม
ขั้นตอน 1 → ประกาศโครงสร้าง Node
  ประกาศ info, priority
  ประกาศ struct Node *prev, *next
ขั้นตอน 2 → ในฟังก์ชัน push(Node** fr, Node** rr, int n, int p)
  ตั้งค่า Node* news = (Node*)malloc(sizeof(Node))
  ตั้งค่า news->info = n
  ตั้งค่า news->priority = p
  ถ้า *fr == NULL แล้ว
    ตั้งค่า *fr = news
    ตั้งค่า *rr = news
    ตั้งค่า news->next = NULL
  มิฉะนั้น ถ้า p <= (*fr)->priority แล้ว
    ตั้งค่า news->next = *fr
    ตั้งค่า (*fr)->prev = news->next
    ตั้งค่า *fr = news
  มิฉะนั้น ถ้า p > (*rr)->priority แล้ว
    ตั้งค่า news->next = NULL
    ตั้งค่า (*rr)->next = news
    ตั้งค่า news->prev = (*rr)->next
    ตั้งค่า *rr = news
  มิฉะนั้น
    ตั้งค่า 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
ขั้นตอน 3 → ในฟังก์ชัน int peek(Node *fr)
  คืนค่า fr->info
ขั้นตอน 4 → ในฟังก์ชัน bool isEmpty(Node *fr)
  คืนค่า (fr == NULL)
ขั้นตอน 5 → ในฟังก์ชัน int pop(Node** fr, Node** rr)
  ตั้งค่า Node* temp = *fr
  ตั้งค่า res = temp->info
  ตั้งค่า (*fr) = (*fr)->next
  free(temp)
  ถ้า *fr == NULL แล้ว
    *rr = NULL
  จบถ้า
  คืนค่า res
ขั้นตอน 6 → ในฟังก์ชัน 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)
  พิมพ์ผลลัพธ์จากการเรียก pop(&front, &rear)
  พิมพ์ผลลัพธ์จากการเรียก peek(front)
หยุด

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

#include <bits/stdc++.h>
using namespace std;
// โหนด doubly linked list
struct Node {
  int info;
  int priority;
  struct Node *prev, *next;
};
// แทรกโหนดใหม่
void push(Node** fr, Node** rr, int n, int p) {
  Node* news = (Node*)malloc(sizeof(Node));
  news->info = n;
  news->priority = p;
  // ถ้า linked list ว่าง
  if (*fr == NULL) {
    *fr = news;
    *rr = news;
    news->next = NULL;
  } else {
    // ถ้า p น้อยกว่าหรือเท่ากับ priority ของโหนดหน้า ให้แทรกที่หน้า
    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 {
      // หาตำแหน่งที่ต้องแทรกโหนดใหม่
      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;
    }
  }
}
// ค่าสุดท้าย
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;
}
// ฟังก์ชันหลัก
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