数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++双向链表实现优先队列
给定数据和整数优先级值，任务是根据给定的优先级创建一个双向链表并显示结果。
队列是一种FIFO(先进先出)数据结构，其中最先插入的元素是最先被移除的。优先队列是一种队列，其中元素可以根据优先级插入或删除。它可以使用队列、堆栈或链表数据结构实现。优先队列通过遵循以下规则来实现：
- 具有最高优先级的数据或元素将优先于具有最低优先级的数据或元素执行。
- 如果两个元素具有相同的优先级，则它们将按照添加到列表中的顺序执行。
用于实现优先队列的双向链表节点将包含三个部分：
- 数据 - 它将存储整数值。
- 下一个地址 - 它将存储下一个节点的地址。
- 上一个地址 - 它将存储上一个节点的地址。
- 优先级 - 它将存储优先级，这是一个整数值。它的范围可以是0-10，其中0表示最高优先级，10表示最低优先级。
示例
输入：
输出：
算法
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
示例
#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;
}输出
5 3
更新于：2019年12月23日
607 次浏览
广告