#include <stdio.h>

#define MAX 100

/* 基于无序数组的优先队列（最大优先队列：值越大优先级越高） */
struct PriorityQueue {
    int items[MAX];
    int size;  /* 当前元素个数 */
};

void initPQ(struct PriorityQueue* pq) { pq->size = 0; }

/* 入队：直接添加到末尾，O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
    if (pq->size >= MAX) return;
    pq->items[pq->size++] = value;
}

/* 出队：遍历查找最大值，O(n)
   找到后将最后一个元素移到删除位置，size 减 1 */
int dequeue(struct PriorityQueue* pq) {
    if (pq->size == 0) return -1;

    /* 查找最大值的索引 */
    int maxIdx = 0;
    for (int i = 1; i < pq->size; i++) {
        if (pq->items[i] > pq->items[maxIdx]) {
            maxIdx = i;
        }
    }
    int maxVal = pq->items[maxIdx];
    /* 将最后一个元素移到被删除位置（避免大量移动） */
    pq->items[maxIdx] = pq->items[--pq->size];
    return maxVal;
}

int main() {
    struct PriorityQueue pq;
    initPQ(&pq);

    enqueue(&pq, 5);
    enqueue(&pq, 9);
    enqueue(&pq, 3);
    enqueue(&pq, 7);

    printf("出队（优先级最高）: %d\n", dequeue(&pq));  /* 输出: 9 */
    printf("出队（优先级最高）: %d\n", dequeue(&pq));  /* 输出: 7 */
    printf("出队（优先级最高）: %d\n", dequeue(&pq));  /* 输出: 5 */
    printf("出队: %d\n", dequeue(&pq));                /* 输出: 3 */
    return 0;
}

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

struct Node {
    int data;
    int priority;       /* 优先级（值越大优先级越高） */
    struct Node* next;
};

/* 入队：按优先级降序插入，O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->priority = priority;
    newNode->next = NULL;

    /* 空链表或新节点优先级最高 → 头部插入 */
    if (head == NULL || head->priority < priority) {
        newNode->next = head;
        return newNode;
    }

    /* 遍历找到合适位置（保持降序） */
    struct Node* cur = head;
    while (cur->next != NULL && cur->next->priority >= priority) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

/* 出队：移除头节点（优先级最高），O(1) */
struct Node* dequeue(struct Node* head) {
    if (head == NULL) return NULL;
    struct Node* temp = head;
    printf("出队: data=%d, priority=%d\n", temp->data, temp->priority);
    head = head->next;
    free(temp);
    return head;
}

int main() {
    struct Node* pq = NULL;

    pq = enqueue(pq, 10, 1);  /* 数据 10，优先级 1 */
    pq = enqueue(pq, 20, 5);  /* 数据 20，优先级 5 */
    pq = enqueue(pq, 30, 3);  /* 数据 30，优先级 3 */

    pq = dequeue(pq);  /* 出队: data=20, priority=5 (最高优先级) */
    pq = dequeue(pq);  /* 出队: data=30, priority=3 */
    pq = dequeue(pq);  /* 出队: data=10, priority=1 */
    return 0;
}