队列详解：从概念到 C 语言实战

顺序队列特点：

• 优点：实现简单，访问速度快，内存连续。
• 缺点：容量固定，存在'假溢出'问题（需通过循环队列优化）。

3.2 链式队列（链表实现）

链式队列使用链表存储元素，队头指针指向头节点，队尾指针指向尾节点。这种方式不需要预先分配固定大小的内存。

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

// 节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 链式队列结构体
typedef struct {
    Node *front; // 队头指针（指向头节点）
    Node *rear;  // 队尾指针（指向尾节点）
} LinkQueue;

// 初始化队列
void InitQueue(LinkQueue *q) {
    // 创建头节点（不存储数据）
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    q->front = head;
    q->rear = head;
}

// 判空
int IsEmpty(LinkQueue *q) {
    return q->front == q->rear;
}

// 入队
void EnQueue(LinkQueue *q, int value) {
    // 创建新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    // 插入到队尾
    q->rear->next = newNode;
    q->rear = newNode;
}

// 出队
int DeQueue(LinkQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无法出队\n");
        return 0;
    }
    Node *temp = q->front->next; // 待删除节点
    *value = temp->data;
    q->front->next = temp->next;

    // 如果删除的是最后一个节点，需更新队尾指针
    if (q->rear == temp) {
        q->rear = q->front;
    }
    free(temp); // 释放节点内存
    return 1;
}

// 获取队头元素
int GetFront(LinkQueue *q, int *value) {
    if (IsEmpty(q)) {
        printf("队列为空，无队头元素\n");
        return 0;
    }
    *value = q->front->next->data;
    return 1;
}

// 销毁队列
void DestroyQueue(LinkQueue *q) {
    while (q->front != NULL) {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

// 测试链式队列
int main() {
    LinkQueue q;
    InitQueue(&q);

    // 入队
    EnQueue(&q, 100);
    EnQueue(&q, 200);
    EnQueue(&q, 300);

    // 获取队头
    int frontVal;
    GetFront(&q, &frontVal);
    printf("队头元素：%d\n", frontVal); // 输出：100

    // 出队
    int deVal;
    DeQueue(&q, &deVal);
    printf("出队元素：%d\n", deVal); // 输出：100

    // 销毁队列
    DestroyQueue(&q);
    return 0;
}

链式队列特点：

• 优点：容量动态扩展，不存在溢出问题。
• 缺点：需要额外空间存储指针，操作稍复杂，内存碎片风险。

四、队列的应用场景

1. 广度优先搜索（BFS）：在二叉树层次遍历、图的遍历中常用队列来管理待访问节点。
2. 缓冲处理：如键盘输入缓冲、网络数据接收缓冲，用于平滑数据流。
3. 任务调度：操作系统中的进程调度、线程池任务调度，保证公平性。
4. 消息传递：分布式系统中的消息队列（如 RabbitMQ），解耦生产者与消费者。

五、两种实现的对比选择