优先队列(priority_queue)的C语言实现代码

优先队列是一种特殊的队列，每个元素都有一个权值。优先队列不同于一般的队列，它不是先进先出，而是按照元素的权值排序，权值最高的元素最先出队列。

C语言中，我们可以使用结构体和数组来实现优先队列。以下是实现优先队列的C语言代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct priority_queue Priority_Queue;

struct priority_queue{
    int *queue;    // 存储优先队列的数组
    int size;      // 优先队列当前的大小
    int capacity;  // 优先队列的最大容量
};

Priority_Queue* create(int capacity){
    Priority_Queue *q = (Priority_Queue*)malloc(sizeof(Priority_Queue));
    q->queue = (int*)malloc(sizeof(int)*capacity);
    q->size = 0;
    q->capacity = capacity;
    return q;
}

int is_empty(Priority_Queue *q){
    return q->size == 0;
}

int is_full(Priority_Queue *q){
    return q->size == q->capacity;
}

void enqueue(Priority_Queue *q, int data){
    if(is_full(q)){
        printf("Queue overflow\n");
        return;
    }
    int i = q->size - 1;
    while(i>=0 && q->queue[i]<data){
        q->queue[i+1] = q->queue[i];
        i--;
    }
    q->queue[i+1]=data;
    q->size++;
}

int dequeue(Priority_Queue *q){
    if(is_empty(q)){
        printf("Queue underflow\n");
        return -1;
    }
    int data = q->queue[q->size-1];
    q->size--;
    return data;
}

void display(Priority_Queue *q){
    if(is_empty(q)){
        printf("The queue is empty\n");
        return;
    }
    printf("Priority queue:\n");
    for(int i=q->size-1;i>=0;i--){
        printf("%d\n", q->queue[i]);
    }
}

int main(){
    Priority_Queue *q = create(5);
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    enqueue(q, 40);
    display(q);
    printf("The highest priority element dequeued: %d\n", dequeue(q));
    printf("The highest priority element dequeued: %d\n", dequeue(q));
    display(q);
    return 0;
}

以上代码中，我们定义了一个带有三个字段的结构体Priority_Queue，分别用来存储优先队列的数组，当前的大小，以及最大容量。我们用到了动态内存分配来创建队列，并定义了一些基本的操作，如创建队列，判断队列是否为空、满、入队和出队操作。具体实现如下：

• create(int capacity)：创建一个容量为capacity的优先队列。
• is_empty(Priority_Queue *q)：判断队列q是否为空，如果队列为空返回1，否则返回0。
• is_full(Priority_Queue *q)：判断队列q是否已满，如果队列已满返回1，否则返回0。
• enqueue(Priority_Queue *q, int data)：将元素data插入到队列q中。
• dequeue(Priority_Queue *q)：从队列q中删除并返回最高优先级的元素。
• display(Priority_Queue *q)：输出队列q。

以下是两个示例。

示例1：我们创建一个容量为5的优先队列，插入10、20、30、40、50。顺序为50->40->30->20->10，然后依次出队操作，输出结果为50->40、50->30、50->20、50->10、50、队列已为空。

Priority_Queue *q = create(5);
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
enqueue(q, 50);
display(q);
while(!is_empty(q)){
    printf("The highest priority element dequeued: %d\n", dequeue(q));
    display(q);
}

示例2：我们创建一个容量为3的优先队列，插入元素2、1和3，顺序为3->2->1。然后依次出队操作，输出结果为3->2、3->1、队列已为空。

Priority_Queue *q = create(3);
enqueue(q, 2);
enqueue(q, 1);
enqueue(q, 3);
display(q);
while(!is_empty(q)){
    printf("The highest priority element dequeued: %d\n", dequeue(q));
    display(q);
}

这些代码可以帮助理解优先队列在C语言中的实现，也可以作为您自己实现优先队列的参考。