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

前言上一篇讲了栈——后进先出的结构。这一篇讲队列和栈刚好相反队列是先进先出的结构。栈用数组实现是最优选择而队列则正好相反链表实现是更常用、更优的选择。本文将讲清楚队列的原理、为什么队列更适合用链表实现以及完整的代码实现。一、什么是队列队列Queue是一种只允许在一端插入数据在另一端删除数据的线性表。插入数据的一端叫队尾tail / rear这个操作叫入队push / enqueue删除数据的一端叫队头head / front这个操作叫出队pop / dequeue。队列的核心特性是先进先出FIFOFirst 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; }六、时间复杂度分析操作时间复杂度说明入队 pushO(1)有tail指针无需遍历出队 popO(1)直接操作head取队头/队尾O(1)直接访问指针判空O(1)判断head是否为NULL可以看到只要正确维护了head和tail两个指针队列的所有标准操作都能做到O(1)这也印证了为什么链表是实现队列的最佳选择。七、队列的经典应用场景广度优先遍历BFS无论是树的层序遍历还是图的广度优先遍历都需要用队列来保存下一层待访问的节点这是队列最经典的应用任务调度 / 消息队列操作系统的进程调度、生产者-消费者模型、消息中间件如Kafka、RabbitMQ的核心思想都基于队列的先进先出特性保证任务按顺序被处理缓冲区例如打印机的打印队列、网络数据包的接收缓冲区都需要按到达顺序依次处理循环队列在数据量有明确上限、且频繁出入队的场景如环形缓冲区会使用数组实现的循环队列通过取模运算复用空间避免链表频繁申请释放节点的开销。八、队列 vs 栈 对比总结特性栈队列操作原则后进先出LIFO先进先出FIFO操作端一端栈顶两端队头出队尾进常用实现方式数组链表核心指针一个tophead tail 两个指针典型应用括号匹配、DFS、函数调用栈BFS、任务调度、消息队列九、总结队列的核心也只有一句话先进先出。相比栈用数组实现的简单直接队列因为需要同时在两端高效操作更适合用链表 头尾双指针的方式实现这样入队出队都能稳定做到O(1)。理解队列尤其是配合BFS的使用场景是后续学习树的层序遍历、图论算法的重要基础建议实现完之后动手写一道BFS的题目加深理解。如果这篇文章对你有帮助欢迎点赞收藏后续会继续更新树、二叉树等数据结构内容