前言

上一篇讲了栈——后进先出的结构。这一篇讲队列，和栈刚好相反，队列是先进先出的结构。栈用数组实现是最优选择，而队列则正好相反：链表实现是更常用、更优的选择。本文将讲清楚队列的原理、为什么队列更适合用链表实现，以及完整的代码实现。

---

一、什么是队列

队列（Queue）是一种只允许在一端插入数据，在另一端删除数据的线性表。

• 插入数据的一端叫队尾（tail / rear），这个操作叫入队（push / enqueue）；
• 删除数据的一端叫队头（head / front），这个操作叫出队（pop / dequeue）。

队列的核心特性是先进先出（FIFO，First In First Out）：最先进队的元素，最先出队。

生活中的例子：排队买奶茶，先来的人先买到，后来的人排在后面；操作系统的任务调度队列；消息队列。

---

二、为什么队列更适合用链表实现

这是队列和栈很大的不同点，值得单独拎出来讲清楚。

• 栈只在一端操作（栈顶），用数组实现时，尾插尾删都是O(1)，非常合适；
• 队列需要在两端操作：队尾入队，队头出队。如果用数组实现，队头出队意味着所有元素都要往前搬移一位，效率是O(N)，非常低效（除非用循环数组或者额外维护两个下标，但实现相对复杂）；
• 而用链表实现队列，只要同时维护一个头指针和一个尾指针，头删（出队）和尾插（入队）都能做到O(1)，完美契合队列的操作特点。

所以结论是：栈优先用数组实现，队列优先用链表实现。

---

三、队列的结构定义

队列通常用单链表实现即可，因为只需要头删和尾插两种操作，不需要双向链表的能力。为了让尾插也能达到O(1)（否则每次尾插都要遍历找最后一个节点），需要额外维护一个尾指针。

typedef int QDataType;

// 链表节点
typedef struct QueueNode {
    QDataType data;
    struct QueueNode* next;
} QueueNode;

// 队列结构：维护头指针、尾指针和有效元素个数
typedef struct Queue {
    QueueNode* head; // 指向队头，出队在这里操作
    QueueNode* tail;  // 指向队尾，入队在这里操作
    int size;          // 有效元素个数
} Queue;

---

四、队列的基本操作

4.1 初始化

void QueueInit(Queue* pq) {
    assert(pq != NULL);

    pq->head = NULL;
    pq->tail = NULL;
    pq->size = 0;
}

4.2 入队（Push）

新节点始终插入到tail之后，再更新tail。需要单独处理队列为空的情况（此时head和tail都要指向新节点）。

void QueuePush(Queue* pq, QDataType x) {
    assert(pq != NULL);

    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = NULL;

    if (pq->tail == NULL) {
        // 队列为空，新节点既是队头也是队尾
        pq->head = newNode;
        pq->tail = newNode;
    } else {
        pq->tail->next = newNode;
        pq->tail = newNode;
    }
    pq->size++;
}

4.3 出队（Pop）

出队从head开始删除。同样需要处理"删除后队列变空"的情况，此时要把tail也置为NULL，否则会成为野指针。

void QueuePop(Queue* pq) {
    assert(pq != NULL);
    assert(pq->head != NULL); // 队列不能为空

    QueueNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;

    // 如果删除后队列为空，tail也要置空
    if (pq->head == NULL) {
        pq->tail = NULL;
    }
    pq->size--;
}

4.4 取队头 / 队尾元素

QDataType QueueFront(Queue* pq) {
    assert(pq != NULL);
    assert(pq->head != NULL);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq) {
    assert(pq != NULL);
    assert(pq->tail != NULL);

    return pq->tail->data;
}

4.5 判空

bool QueueEmpty(Queue* pq) {
    assert(pq != NULL);
    return pq->head == NULL;
}

4.6 获取有效元素个数

int QueueSize(Queue* pq) {
    assert(pq != NULL);
    return pq->size;
}

4.7 销毁

​void QueueDestroy(Queue* pq) {
    assert(pq != NULL);

    QueueNode* cur = pq->head;
    while (cur != NULL) {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

---

五、完整测试代码

int main() {
    Queue q;
    QueueInit(&q);

    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);

    printf("队头: %d, 队尾: %d\n", QueueFront(&q), QueueBack(&q)); // 队头: 1, 队尾: 4

    while (!QueueEmpty(&q)) {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    printf("\n"); // 1 2 3 4，和入队顺序一致

    QueueDestroy(&q);
    return 0;
}

---

六、时间复杂度分析

操作	时间复杂度	说明
入队 push	O(1)	有tail指针，无需遍历
出队 pop	O(1)	直接操作head
取队头/队尾	O(1)	直接访问指针
判空	O(1)	判断head是否为NULL

可以看到，只要正确维护了head和tail两个指针，队列的所有标准操作都能做到O(1)，这也印证了为什么链表是实现队列的最佳选择。

---

七、队列的经典应用场景

• 广度优先遍历（BFS）：无论是树的层序遍历，还是图的广度优先遍历，都需要用队列来保存"下一层待访问的节点"，这是队列最经典的应用；
• 任务调度 / 消息队列：操作系统的进程调度、生产者-消费者模型、消息中间件（如Kafka、RabbitMQ）的核心思想都基于队列的先进先出特性，保证任务按顺序被处理；
• 缓冲区：例如打印机的打印队列、网络数据包的接收缓冲区，都需要按到达顺序依次处理；
• 循环队列：在数据量有明确上限、且频繁出入队的场景（如环形缓冲区），会使用数组实现的循环队列，通过取模运算复用空间，避免链表频繁申请释放节点的开销。

---

八、队列 vs 栈 对比总结

特性	栈	队列
操作原则	后进先出（LIFO）	先进先出（FIFO）
操作端	一端（栈顶）	两端（队头出，队尾进）
常用实现方式	数组	链表
核心指针	一个top	head + tail 两个指针
典型应用	括号匹配、DFS、函数调用栈	BFS、任务调度、消息队列

---

九、总结

队列的核心也只有一句话：先进先出。相比栈用数组实现的简单直接，队列因为需要同时在两端高效操作，更适合用链表 + 头尾双指针的方式实现，这样入队出队都能稳定做到O(1)。理解队列，尤其是配合BFS的使用场景，是后续学习树的层序遍历、图论算法的重要基础，建议实现完之后，动手写一道BFS的题目加深理解。

如果这篇文章对你有帮助，欢迎点赞收藏，后续会继续更新树、二叉树等数据结构内容！