数据结构篇（六）：线性表——队列

前言

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

一、什么是队列

队列（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; }

六、时间复杂度分析

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

七、队列的经典应用场景

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

八、队列 vs 栈 对比总结

九、总结

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

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