3. 事件队列与优先级

任务定义

在事件驱动系统中，不同事件的重要程度不同。本案例实现一个支持优先级的事件队列，核心目标：高优先级事件始终先于低优先级事件被取出处理。队列支持动态插入事件，每次出队返回当前队列中优先级最高的事件；同优先级事件按先入先出（FIFO）顺序处理。

数据结构设计

采用数组实现的二叉最小堆（优先级数值越小，优先级越高）。堆节点存储事件ID、优先级数值和到达序号。到达序号用于保证同优先级事件的FIFO顺序——当两个事件优先级相同时，序号小者先出队。堆操作包括上浮（插入时）和下沉（删除堆顶时），时间复杂度均为O(log n)。

代码实现

以下代码为完整可编译的C语言实现，包含事件队列的初始化、入队、出队和销毁操作，以及一个演示主函数。

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

#define MAX_QUEUE_SIZE 64

/* 事件结构体 */
typedef struct {
    int id;          /* 事件ID */
    int priority;    /* 优先级，数值越小优先级越高 */
    unsigned int seq; /* 到达序号，用于同优先级FIFO */
} Event;

/* 优先级事件队列 */
typedef struct {
    Event *data;
    int size;        /* 当前元素个数 */
    int capacity;    /* 容量 */
    unsigned int next_seq; /* 下一个到达序号 */
} PriorityQueue;

/* 比较两个事件：返回1表示a优先级高于b */
static int isHigher(const Event *a, const Event *b) {
    if (a->priority != b->priority)
        return a->priority < b->priority;
    return a->seq < b->seq;
}

/* 交换两个事件 */
static void swap(Event *a, Event *b) {
    Event tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 初始化队列 */
void pq_init(PriorityQueue *pq, int capacity) {
    pq->data = (Event*)malloc(sizeof(Event) * capacity);
    pq->size = 0;
    pq->capacity = capacity;
    pq->next_seq = 0;
}

/* 销毁队列 */
void pq_destroy(PriorityQueue *pq) {
    free(pq->data);
    pq->data = NULL;
    pq->size = 0;
    pq->capacity = 0;
}

/* 上浮调整 */
static void siftUp(PriorityQueue *pq, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (isHigher(&pq->data[index], &pq->data[parent])) {
            swap(&pq->data[index], &pq->data[parent]);
            index = parent;
        } else {
            break;
        }
    }
}

/* 下沉调整 */
static void siftDown(PriorityQueue *pq, int index) {
    while (1) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;

        if (left < pq->size && isHigher(&pq->data[left], &pq->data[smallest]))
            smallest = left;
        if (right < pq->size && isHigher(&pq->data[right], &pq->data[smallest]))
            smallest = right;

        if (smallest != index) {
            swap(&pq->data[index], &pq->data[smallest]);
            index = smallest;
        } else {
            break;
        }
    }
}

/* 入队 */
int pq_push(PriorityQueue *pq, int id, int priority) {
    if (pq->size >= pq->capacity)
        return -1; /* 队列满 */

    Event ev;
    ev.id = id;
    ev.priority = priority;
    ev.seq = pq->next_seq++;

    pq->data[pq->size] = ev;
    siftUp(pq, pq->size);
    pq->size++;
    return 0;
}

/* 出队：返回最高优先级事件，成功返回0，队列空返回-1 */
int pq_pop(PriorityQueue *pq, Event *out) {
    if (pq->size == 0)
        return -1;

    *out = pq->data[0];
    pq->size--;
    if (pq->size > 0) {
        pq->data[0] = pq->data[pq->size];
        siftDown(pq, 0);
    }
    return 0;
}

/* 获取队列当前元素个数 */
int pq_size(const PriorityQueue *pq) {
    return pq->size;
}

/* 演示主函数 */
int main(void) {
    PriorityQueue pq;
    pq_init(&pq, MAX_QUEUE_SIZE);

    /* 插入测试事件: (事件ID, 优先级) */
    pq_push(&pq, 101, 3);
    pq_push(&pq, 102, 1);  /* 最高优先级 */
    pq_push(&pq, 103, 2);
    pq_push(&pq, 104, 1);  /* 与102同优先级，后到 */
    pq_push(&pq, 105, 5);

    printf("入队完成，当前队列大小: %d\n", pq_size(&pq));

    /* 依次出队并打印 */
    Event ev;
    printf("出队顺序 (事件ID, 优先级):\n");
    while (pq_pop(&pq, &ev) == 0) {
        printf("  ID=%d, P=%d\n", ev.id, ev.priority);
    }

    pq_destroy(&pq);
    return 0;
}

编译与运行

将上述代码保存为priority_queue.c，在终端执行以下命令编译并运行：

gcc -Wall -o priority_queue priority_queue.c
./priority_queue

验证方法与判定标准

程序输出应满足以下判定条件：

• 优先级顺序正确：出队顺序中，优先级数值小的事件必须先输出。即P=1的两个事件（ID=102和ID=104）必须先于P=2、P=3、P=5的事件输出。
• 同优先级FIFO：ID=102（先入队）必须先于ID=104（后入队）输出。
• 队列完整：所有5个事件均被取出，最终队列大小为0。

预期输出顺序为：ID=102, P=1 → ID=104, P=1 → ID=103, P=2 → ID=101, P=3 → ID=105, P=5。若输出与此一致，则说明优先级事件队列实现正确。