原文：
给定具有优先级的节点，请使用双链表实现优先级队列。
前提条件：
优先级队列上的操作：
-
push()：此函数用于将新数据插入队列。 -
pop()：此函数从队列中删除优先级最低的元素。 -
peek()/top()：此函数用于获取队列中优先级最低的元素，而不将其从队列中删除。
方法：
-
创建一个双链表，其中包含字段
info（保存节点的信息），优先级（保存节点的优先级），prev（指向上一个节点），next（指向下一个节点）。 -
在节点中插入元素和优先级。
-
按优先级的升序排列节点。
以下是上述步骤的实现：
c
// cpp code to implement priority
// queue using doubly linked list
#include
using namespace std;
// linked list node
struct node {
int info;
int priority;
struct node *prev, *next;
};
// function to insert 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 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 at
// the front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}
// if p is more rear node's priority,
// then insert after the rear.
else if (p > (*rr)->priority) {
news->next = null;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}
// handle other cases
else {
// find position where we need to
// insert.
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;
}
}
}
// return the value at rear
int peek(node *fr)
{
return fr->info;
}
bool isempty(node *fr)
{
return (fr == null);
}
// removes the element with the
// least priority value form the list
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;
}
// driver code
int main()
{
node *front = null, *rear = null;
push(&front, &rear, 2, 3);
push(&front, &rear, 3, 4);
push(&front, &rear, 4, 5);
push(&front, &rear, 5, 6);
push(&front, &rear, 6, 7);
push(&front, &rear, 1, 2);
cout << pop(&front, &rear) << endl;
cout << peek(front);
return 0;
}
java
// java code to implement priority
// queue using doubly linked list
import java.util.* ;
class solution
{
static node front , rear;
// linked list node
static class node {
int info;
int priority;
node prev, next;
}
// function to insert a new node
static void push(node fr, node rr, int n, int p)
{
node news = new node();
news.info = n;
news.priority = p;
// if 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 at
// the front.
if (p <= (fr).priority) {
news.next = fr;
(fr).prev = news.next;
fr = news;
}
// if p is more rear node's priority,
// then insert after the rear.
else if (p > (rr).priority) {
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
// handle other cases
else {
// find position where we need to
// insert.
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;
}
}
front =fr;
rear=rr;
}
// return the value at rear
static int peek(node fr)
{
return fr.info;
}
static boolean isempty(node fr)
{
return (fr == null);
}
// removes the element with the
// least priority value form the list
static int pop(node fr, node rr)
{
node temp = fr;
int res = temp.info;
(fr) = (fr).next;
if (fr == null)
rr = null;
front =fr;
rear=rr;
return res;
}
// driver code
public static void main(string args[])
{
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
system.out.println( pop(front, rear));
system.out.println( peek(front));
}
}
// this code is contributed
// by arnab kundu
c
// c# code to implement priority
// queue using doubly linked list
using system;
class gfg
{
public static node front, rear;
// linked list node
public class node
{
public int info;
public int priority;
public node prev, next;
}
// function to insert a new node
public static void push(node fr, node rr,
int n, int p)
{
node news = new node();
news.info = n;
news.priority = p;
// if 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 at
// the front.
if (p <= (fr).priority)
{
news.next = fr;
(fr).prev = news.next;
fr = news;
}
// if p is more rear node's priority,
// then insert after the rear.
else if (p > (rr).priority)
{
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
// handle other cases
else
{
// find position where we
// need to insert.
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;
}
}
front = fr;
rear = rr;
}
// return the value at rear
public static int peek(node fr)
{
return fr.info;
}
public static bool isempty(node fr)
{
return (fr == null);
}
// removes the element with the
// least priority value form the list
public static int pop(node fr, node rr)
{
node temp = fr;
int res = temp.info;
(fr) = (fr).next;
if (fr == null)
{
rr = null;
}
front = fr;
rear = rr;
return res;
}
// driver code
public static void main(string[] args)
{
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
console.writeline(pop(front, rear));
console.writeline(peek(front));
}
}
// this code is contributed by shrikant13
输出：
1
2
相关文章：
时间复杂度以及与的比较：
peek() push() pop()
-----------------------------------------
linked list | o(1) o(n) o(1)
|
binary heap | o(1) o(log n) o(log n)
如果您喜欢 geeksforgeeks 并希望做出贡献，则还可以使用 tribution.geeksforgeeks.org 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 geeksforgeeks pg电子试玩链接主页上，并帮助其他 geeks。
如果您发现任何不正确的地方，请单击下面的“改进文章”按钮，以改进本文。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
