数据结构：队列概念与 C 语言实现

顺序队列特点：

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

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）底层逻辑。

选型建议

实际开发中，若追求极致性能且能预估规模，首选顺序队列；若规模不可控，链式队列则更安全。