Hàng đợi ưu tiên dùng danh sách liên kết kép trong C++

Cho dữ liệu và ưu tiên là giá trị nguyên, nhiệm vụ là tạo danh sách liên kết kép theo ưu tiên cho trước và hiển thị kết quả.

Hàng đợi là cấu trúc dữ liệu FIFO, phần tử chèn đầu tiên sẽ được xóa đầu tiên. Hàng đợi ưu tiên là loại hàng đợi mà các phần tử có thể chèn hoặc xóa tùy thuộc vào ưu tiên. Có thể triển khai bằng queue, stack hoặc linked list. Hàng đợi ưu tiên tuân theo các quy tắc sau –

• Dữ liệu hoặc phần tử có ưu tiên cao nhất sẽ được thực thi trước dữ liệu hoặc phần tử có ưu tiên thấp hơn.
• Nếu hai phần tử có cùng ưu tiên thì chúng sẽ được thực thi theo thứ tự được thêm vào danh sách.

Một nút của danh sách liên kết kép để triển khai hàng đợi ưu tiên sẽ chứa ba phần –

• Dữ liệu – lưu giá trị nguyên.
• Địa chỉ Next – lưu địa chỉ nút tiếp theo.
• Địa chỉ Previous – lưu địa chỉ nút trước đó.
• Ưu tiên – lưu ưu tiên là giá trị nguyên. Có thể từ 0-10, trong đó 0 đại diện cho ưu tiên cao nhất và 10 đại diện cho ưu tiên thấp nhất.

Ví dụ

Đầu vào -

Đầu ra-

Thuật toán

Bắt đầu
Bước 1 -> Khai báo struct Node
    Khai báo info, priority
    Khai báo struct Node *prev, *next
Bước 2 -> Trong hàm push(Node** fr, Node** rr, int n, int p)
    Gán Node* news = (Node*)malloc(sizeof(Node))
    Gán news->info = n
    Gán news->priority = p
    NẾU *fr == NULL thì,
        Gán *fr = news
        Gán *rr = news
        Gán news->next = NULL
    NGƯỢC LẠI NẾU p <= (*fr)->priority thì,
        Gán news->next = *fr
        Gán (*fr)->prev = news->next
        Gán *fr = news
    NGƯỢC LẠI NẾU p > (*rr)->priority thì,
        Gán news->next = NULL
        Gán (*rr)->next = news
        Gán news->prev = (*rr)->next
        Gán *rr = news
    NGƯỢC LẠI
        Gán Node* start = (*fr)->next
        Vòng lặp Khi start->priority > p
            Gán start = start->next
            Gán (start->prev)->next = news
            Gán news->next = start->prev
            Gán news->prev = (start->prev)->next
            Gán start->prev = news->next
Bước 3 -> Trong hàm int peek(Node *fr)
    Trả về fr->info
Bước 4 -> Trong hàm bool isEmpty(Node *fr)
    Trả về (fr == NULL)
Bước 5 -> Trong hàm int pop(Node** fr, Node** rr)
    Gán Node* temp = *fr
    Gán res = temp->info
    Gán (*fr) = (*fr)->next
    free(temp)
    NẾU *fr == NULL thì,
        *rr = NULL
    Trả về res
Bước 6 -> Trong hàm int main()
    Khai báo và gán Node *front = NULL, *rear = NULL
    Gọi hàm push(&front, &rear, 4, 3)
    Gọi hàm push(&front, &rear, 3, 2)
    Gọi hàm push(&front, &rear, 5, 2)
    Gọi hàm push(&front, &rear, 5, 7)
    Gọi hàm push(&front, &rear, 2, 6)
    Gọi hàm push(&front, &rear, 1, 4)
    In kết quả từ gọi hàm pop(&front, &rear)
    In kết quả từ gọi hàm peek(front)
Kết thúc

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

// Nút danh sách liên kết kép
struct Node {
    int info;
    int priority;
    struct Node *prev, *next;
};

// Chèn nút mới
void push(Node** fr, Node** rr, int n, int p) {
    Node* news = (Node*)malloc(sizeof(Node));
    news->info = n;
    news->priority = p;
    // nếu danh sách liên kết rỗng
    if (*fr == NULL) {
        *fr = news;
        *rr = news;
        news->next = NULL;
    } else {
        // Nếu p nhỏ hơn hoặc bằng ưu tiên nút đầu
        // thì chèn nút ở đầu.
        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 {
            // Tìm vị trí cần chèn nút mới.
            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;
        }
    }
}

// Giá trị cuối
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;
}

// Hàm main
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;
}

Đầu ra

5 3