树数据结构教程9.国彩网级队列

在本章中，我们将了解国彩网级队列及其使用C语言的链接列表的实现。

国彩网级队列是元素的集合，其中为每个元素分配了国彩网级。基于国彩网级，可以从国彩网级队列数据结构中插入或删除元素。

实现PQ的最简单方法之一是使用链接列表。

我们在哪里使用PQ？

在许多现实世界中，我们使用PQ。

例如：
1.与国彩网级较低的进程相比，国彩网级较高的进程需要首先执行。
2.在100页的打印作业中，如果特定文档具有国彩网级，则打印机必须暂停正在进行的作业并开始打印高国彩网级的作业。

以下是在PQ上执行的操作：

1.排队：添加具有给定国彩网级的元素
2.出队：删除国彩网级最高的元素
3. Peek（）：返回国彩网级最高的元素。

使用C使用链接列表实现国彩网级队列：

#include "stdio.h"
#include "stdlib.h"

//strucure to hold priority queue data structure
struct Node
{
    int data;
    int priority;
    struct Node* next;
};

//head node
struct Node* head = NULL;

// traverse element by element
void traverse()
{
    //take temp node to traverse.
    struct Node* temp = head;
    while(temp != NULL)
    {
        printf("\n Data = %d  and it's priority is = %d ",temp->data,temp->priority);
        temp = temp->next;
    }
}

//check if the list is empty
int isempty()
{
    if(head == NULL)
        return 1;
    else
        return 0;
}

// insert element with priority in it's correct place
void enqueue(int priority, int data)
{
    //create a temp node and then copy the data and priority
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p = head;
    temp->data = data;
    temp->priority = priority;

    if(isempty() || priority < head->priority)
    {
        temp->next = head;
        head = temp;
    }

    else
    {
        while(p->next!=NULL && p->next->priority <= priority)
            p = p->next;

        temp->next = p->next;
        p->next = temp;
    }
}

int dequeue()
{
    struct Node *tmp;
    int item;
    if( isempty() )
    {
        printf("\nQueue Underflow\n");
        return -1;
    }
    else
    {
        tmp=head;
        item=tmp->data;
        head=head->next;
        free(tmp);
    }
    return item;
}


int main()
{
    //lower the priority value, higher the priority
    enqueue(4,34);
    enqueue(1,25);
    enqueue(6,98);
    enqueue(2,87);
    enqueue(3,67);
    enqueue(5,23);
    
    traverse();

    printf("\nhighest priority element is = %d\n",dequeue()); 
    return 0;
}

输出：

Data = 25 and it's priority is = 1
Data = 87 and it's priority is = 2
Data = 67 and it's priority is = 3
Data = 34 and it's priority is = 4
Data = 23 and it's priority is = 5
Data = 98 and it's priority is = 6
highest priority element is = 25

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：