原文：
使用链表实现优先级队列。
优先级队列上的操作：
-
push()：此函数用于将新数据插入队列。 -
pop()：此函数从队列中删除优先级最高的元素。 -
peek()/top()：此函数用于获取队列中优先级最高的元素，而无需将其从队列中删除。
可以使用常见的数据结构（如数组，链表，堆和二叉树）来实现优先级队列。
先决条件：
，
这样创建列表，以使优先级最高的元素始终位于列表的开头。 该列表根据元素的优先级以降序排列。 这使我们可以删除o(1)时间中的最高优先级元素。 要插入元素，我们必须遍历列表并找到合适的位置插入节点，以便维护优先级队列的整体顺序。 这使push()操作花费o(n)时间。 pop()和peek()操作在固定时间内执行。
算法：
push(head, data, priority)
步骤 1：使用data和priority创建新节点
步骤 2：检查head是否具有较低的优先级。 如果是，请执行步骤 3-4，然后结束。 否则，转到步骤 5。
步骤 3：new->next = head
步骤 4：head = new
步骤 5：将temp设置为列表的头部
步骤 6：while temp->next != null和temp->next->priority > priority
步骤 7：temp = temp->next
【循环结束】
步骤 8 ：new->next = temp->next
步骤 9：temp->next = new
步骤 10：结束
pop(head)
步骤 2：将列表的开头设置为列表中的下一个节点。 head = head->next。
步骤 3：释放列表顶部的节点
步骤 4：结束
peek(head)
步骤 1：返回head->data
步骤 2：结束
下面是该算法的实现：
c
// c code to implement priority queue
// using linked list
#include
using namespace std;
// node
typedef struct node
{
int data;
// lower values indicate
// higher priority
int priority;
struct node* next;
} node;
// function to create a new node
node* newnode(int d, int p)
{
node* temp = (node*)malloc(sizeof(node));
temp->data = d;
temp->priority = p;
temp->next = null;
return temp;
}
// return the value at head
int peek(node** head)
{
return (*head)->data;
}
// removes the element with the
// highest priority form the list
void pop(node** head)
{
node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
// function to push according to priority
void push(node** head, int d, int p)
{
node* start = (*head);
// create new node
node* temp = newnode(d, p);
// special case: the head of list has
// lesser priority than new node. so
// insert newnode before head node
// and change head node.
if ((*head)->priority > p)
{
// insert new node before head
temp->next = *head;
(*head) = temp;
}
else
{
// traverse the list and find a
// position to insert new node
while (start->next != null &&
start->next->priority < p)
{
start = start->next;
}
// either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// function to check is list is empty
int isempty(node** head)
{
return (*head) == null;
}
// driver code
int main()
{
// create a priority queue
// 7->4->5->6
node* pq = newnode(4, 1);
push(&pq, 5, 2);
push(&pq, 6, 3);
push(&pq, 7, 0);
while (!isempty(&pq))
{
cout << " " << peek(&pq);
pop(&pq);
}
return 0;
}
// this code is contributed by shivanisinghss2110
c
// c code to implement priority queue
// using linked list
#include
#include
// node
typedef struct node {
int data;
// lower values indicate higher priority
int priority;
struct node* next;
} node;
// function to create a new node
node* newnode(int d, int p)
{
node* temp = (node*)malloc(sizeof(node));
temp->data = d;
temp->priority = p;
temp->next = null;
return temp;
}
// return the value at head
int peek(node** head)
{
return (*head)->data;
}
// removes the element with the
// highest priority form the list
void pop(node** head)
{
node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
// function to push according to priority
void push(node** head, int d, int p)
{
node* start = (*head);
// create new node
node* temp = newnode(d, p);
// special case: the head of list has lesser
// priority than new node. so insert new
// node before head node and change head node.
if ((*head)->priority > p) {
// insert new node before head
temp->next = *head;
(*head) = temp;
}
else {
// traverse the list and find a
// position to insert new node
while (start->next != null &&
start->next->priority < p) {
start = start->next;
}
// either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// function to check is list is empty
int isempty(node** head)
{
return (*head) == null;
}
// driver code
int main()
{
// create a priority queue
// 7->4->5->6
node* pq = newnode(4, 1);
push(&pq, 5, 2);
push(&pq, 6, 3);
push(&pq, 7, 0);
while (!isempty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
java
// java code to implement priority queue
// using linked list
import java.util.* ;
class solution
{
// node
static class node {
int data;
// lower values indicate higher priority
int priority;
node next;
}
static node node = new node();
// function to create a new node
static node newnode(int d, int p)
{
node temp = new node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
// return the value at head
static int peek(node head)
{
return (head).data;
}
// removes the element with the
// highest priority form the list
static node pop(node head)
{
node temp = head;
(head) = (head).next;
return head;
}
// function to push according to priority
static node push(node head, int d, int p)
{
node start = (head);
// create new node
node temp = newnode(d, p);
// special case: the head of list has lesser
// priority than new node. so insert new
// node before head node and change head node.
if ((head).priority > p) {
// insert new node before head
temp.next = head;
(head) = temp;
}
else {
// traverse the list and find a
// position to insert new node
while (start.next != null &&
start.next.priority < p) {
start = start.next;
}
// either at the ends of the list
// or at required position
temp.next = start.next;
start.next = temp;
}
return head;
}
// function to check is list is empty
static int isempty(node head)
{
return ((head) == null)?1:0;
}
// driver code
public static void main(string args[])
{
// create a priority queue
// 7.4.5.6
node pq = newnode(4, 1);
pq =push(pq, 5, 2);
pq =push(pq, 6, 3);
pq =push(pq, 7, 0);
while (isempty(pq)==0) {
system.out.printf("%d ", peek(pq));
pq=pop(pq);
}
}
}
// this code is contributed
// by arnab kundu
c
// c# code to implement priority queue
// using linked list
using system;
class gfg
{
// node
public class node
{
public int data;
// lower values indicate
// higher priority
public int priority;
public node next;
}
public static node node = new node();
// function to create a new node
public static node newnode(int d, int p)
{
node temp = new node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
// return the value at head
public static int peek(node head)
{
return (head).data;
}
// removes the element with the
// highest priority form the list
public static node pop(node head)
{
node temp = head;
(head) = (head).next;
return head;
}
// function to push according to priority
public static node push(node head,
int d, int p)
{
node start = (head);
// create new node
node temp = newnode(d, p);
// special case: the head of list
// has lesser priority than new node.
// so insert new node before head node
// and change head node.
if ((head).priority > p)
{
// insert new node before head
temp.next = head;
(head) = temp;
}
else
{
// traverse the list and find a
// position to insert new node
while (start.next != null &&
start.next.priority < p)
{
start = start.next;
}
// either at the ends of the list
// or at required position
temp.next = start.next;
start.next = temp;
}
return head;
}
// function to check is list is empty
public static int isempty(node head)
{
return ((head) == null) ? 1 : 0;
}
// driver code
public static void main(string[] args)
{
// create a priority queue
// 7.4.5.6
node pq = newnode(4, 1);
pq = push(pq, 5, 2);
pq = push(pq, 6, 3);
pq = push(pq, 7, 0);
while (isempty(pq) == 0)
{
console.write("{0:d} ", peek(pq));
pq = pop(pq);
}
}
}
// this code is contributed by shrikant13
输出：
7 4 5 6
时间复杂度以及与的比较：
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，转载请注明出处
