Chúng tôi được cung cấp dữ liệu và mức độ ưu tiên dưới dạng giá trị số nguyên và nhiệm vụ là tạo một danh sách được liên kết kép theo mức độ ưu tiên đã cho và hiển thị kết quả.
Hàng đợi là một cấu trúc dữ liệu FIFO trong đó phần tử được chèn vào đầu tiên là phần tử đầu tiên bị xóa. Hàng đợi Ưu tiên là một loại hàng đợi trong đó các phần tử có thể được chèn hoặc xóa tùy thuộc vào mức độ ưu tiên. Nó có thể được thực hiện bằng cách sử dụng cấu trúc dữ liệu hàng đợi, ngăn xếp hoặc danh sách liên kết. Hàng đợi ưu tiên được triển khai bằng cách tuân theo các quy tắc sau -
- Dữ liệu hoặc phần tử có mức độ ưu tiên cao nhất sẽ được thực thi trước phần dữ liệu hoặc phần tử có mức độ ưu tiên thấp nhất.
- Nếu hai phần tử có cùng mức độ ưu tiên, chúng sẽ được thực thi theo trình tự mà chúng được thêm vào danh sách.
Một nút của danh sách được liên kết kép để triển khai hàng đợi ưu tiên sẽ chứa ba phần -
- Dữ liệu - Nó sẽ lưu trữ giá trị số nguyên.
- Địa chỉ Tiếp theo - Nó sẽ lưu trữ địa chỉ của một nút tiếp theo
- Địa chỉ trước - Nó sẽ lưu trữ địa chỉ của nút trước đó
- Mức độ ưu tiên - Nó sẽ lưu trữ mức độ ưu tiên là một giá trị số nguyên. Nó có thể nằm trong khoảng từ 0-10 trong đó 0 đại diện cho mức độ ưu tiên cao nhất và 10 đại diện cho mức độ ưu tiên thấp nhất.
Ví dụ
Đầu vào -
Đầu ra-
Thuật toán
Start Step 1-> Declare a struct Node Declare info, priority Declare struct Node *prev, *next Step 2-> In function push(Node** fr, Node** rr, int n, int p) Set Node* news = (Node*)malloc(sizeof(Node)) Set news->info = n Set news->priority = p If *fr == NULL then, Set *fr = news Set *rr = news Set news->next = NULL Else If p <= (*fr)->priority then, Set news->next = *fr Set (*fr)->prev = news->next Set *fr = news Else If p > (*rr)->priority then, Set news->next = NULL Set (*rr)->next = news Set news->prev = (*rr)->next Set *rr = news Else Set Node* start = (*fr)->next Loop While start->priority > p Set start = start->next Set (start->prev)->next = news Set news->next = start->prev Set news->prev = (start->prev)->next Set start->prev = news->next Step 3-> In function int peek(Node *fr) Return fr->info Step 4-> In function bool isEmpty(Node *fr) Return (fr == NULL) Step 5-> In function int pop(Node** fr, Node** rr) Set Node* temp = *fr Set res = temp->info Set (*fr) = (*fr)->next free(temp) If *fr == NULL then, *rr = NULL Return res Step 6-> In function int main() Declare and assign Node *front = NULL, *rear = NULL Call function push(&front, &rear, 4, 3) Call function push(&front, &rear, 3, 2) Call function push(&front, &rear, 5, 2) Call function push(&front, &rear, 5, 7) Call function push(&front, &rear, 2, 6) Call function push(&front, &rear, 1, 4) Print the results obtained from calling the function pop(&front, &rear) Print the results obtained from calling the function peek(front) Stop
Ví dụ
#include <bits/stdc++.h>
using namespace std;
//doubly linked list node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
//inserting a new Node
void push(Node** fr, Node** rr, int n, int p) {
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// if the linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
} else {
// If p is less than or equal front
// node's priority, then insert the node
// at front.
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 {
// Finding the position where we need to
// insert the new node.
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;
}
}
}
//the last value
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;
}
// main function
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