【深入理解链式队列：C语言实现详解与完整代码】

前言队列Queue是一种 ** 先进先出FIFO, First In First Out的线性数据结构。它只允许在队尾rear插入在队头front** 删除。队列的应用场景无处不在操作系统任务调度消息队列打印机队列广度优先搜索BFS生产者 - 消费者模型前面我们学过顺序队列数组实现它有固定大小、需要扩容、会出现 “假溢出” 等问题。链式队列完美解决了这些痛点一、链式队列是什么链式队列 用单链表实现的队列特点按需申请内存不存在容量限制无假溢出不需要扩容入队在队尾出队在队头时间复杂度O(1)结构简单、稳定、高效二、链式队列结构体设计核心链式队列采用“队头指针 队尾指针”管理模式#pragma once typedef int ELEM_TYPE; // 链式队列有效节点结构体 typedef struct LQ_Node { ELEM_TYPE data; // 数据域 struct LQ_Node* next; // 指针域 } LQ_Node; // 链式队列辅助节点结构体管理队头、队尾 typedef struct List_Queue { LQ_Node* front; // 队头指针出队端 LQ_Node* rear; // 队尾指针入队端 } List_Queue;结构说明LQ_Node真正存储数据的节点List_Queue辅助管理结构front指向队头节点rear指向队尾节点空队列front NULL rear NULL三、链式队列支持的操作全覆盖// 1. 初始化 void Init_List_Queue(struct List_Queue* plq); // 2. 入队尾插 bool Push(struct List_Queue* plq, ELEM_TYPE val); // 3. 出队头删 bool Pop(struct List_Queue* plq); // 4. 获取队头元素 ELEM_TYPE Front(struct List_Queue* plq); // 5. 查找元素 LQ_Node* Search(struct List_Queue* plq, ELEM_TYPE val); // 6. 判空 bool IsEmpty(struct List_Queue* plq); // 7. 获取有效元素个数 int Get_Size(struct List_Queue* plq); // 8. 清空队列 void Clear(struct List_Queue* plq); // 9. 销毁队列释放内存 void Destroy(struct List_Queue* plq); // 10. 打印队列 void Show(struct List_Queue* plq);四、核心函数精讲最关键#define _CRT_SECURE_NO_WARNINGS #includestdio.h #includeassert.h #includestdlib.h #includeList_Queue.h //1.初始化 void Init_List_Queue(struct List_Queue* plq) { assert(NULL ! plq); // 空队列队头、队尾都指向 NULL plq-front plq-rear NULL; } //2.入队 bool Push(struct List_Queue* plq, ELEM_TYPE val) { assert(NULL! plq); LQ_Node* pnewnode (LQ_Node*)malloc(sizeof(LQ_Node)); if (pnewnode NULL) return false; pnewnode-data val; //分情况看链式队列是否为空 if (IsEmpty(plq)) { pnewnode-next NULL; plq-front plq-rear pnewnode; return true; } //不空修改对应三个指针 else { /*plq-rear-next pnewnode; plq-rear pnewnode;*/ pnewnode-next plq-rear-next; plq-rear-next pnewnode; plq-rear pnewnode;// 更新队尾 return true; } } //3.出队 bool Pop(struct List_Queue* plq) { assert(NULL ! plq); if (IsEmpty(plq)) return false; //2分情况处理看此时的有效元素个数是1还是大于1 //2.1仅有唯一一个有效元素 LQ_Node* tmp plq-front; if (tmp-next NULL) { plq-front plq-rear NULL; free(tmp); tmp NULL; return true; } else { plq-front tmp-next;// 队头后移 free(tmp); // 释放旧队头 tmp NULL; return true; } } //4.获取队头元素值 ELEM_TYPE Front(struct List_Queue* plq) { assert(NULL ! plq); if (IsEmpty(plq)) exit(1); /*LQ_Node* p plq-front; return p-data;*/ return plq-front-data; } //5查找 LQ_Node* Search(struct List_Queue* plq, ELEM_TYPE val) { assert(NULL ! plq); if (IsEmpty(plq)) exit(1); LQ_Node* q plq-front; while (q ! NULL) { if (q-data val) return q; q q-next; } return NULL; } //6.判空 bool IsEmpty(struct List_Queue* plq) { // 队头为 NULL 表示空队列 return plq-front NULL; } //7.获取有效值个数 Size int Get_Size(struct List_Queue* plq) { assert(NULL ! plq); LQ_Node* q plq-front; int count 0; // 遍历链表统计节点数 while (q ! NULL) { count; q q-next; } return count; } //8.清空 void Clear(struct List_Queue* plq) { Destroy(plq); // plq-front plq-rear NULL; } //9.销毁 void Destroy(struct List_Queue* plq) { LQ_Node* p plq-front; LQ_Node* q NULL; while (p ! NULL) { q p-next; free(p); p q; } // 重置队头、队尾 plq-front plq-rear NULL; } //10.打印 void Show(struct List_Queue* plq) { assert(NULL ! plq); LQ_Node* p plq-front; for ( ; p!NULL; pp-next) { printf(%d , p-data); } printf(\n); }链式队列入队 单链表尾插——时间复杂度O(1)链式队列出队 删除链表第一个节点——时间复杂度O(1)五、测试主函数可直接运行int main() { List_Queue head; Init_List_Queue(head); Push(head, 1); Push(head, 2); Push(head, 3); Show(head); Pop(head); Show(head); // 输出2 3 printf(队头元素%d\n, Front(head)); // 输出2 Destroy(head); return 0; }运行结果六、链式队列 VS 顺序队列重点特性顺序队列链式队列存储结构连续数组链式节点容量固定 / 需扩容无限无溢出入队出队O(1)O(1)内存分配静态 / 动态动态假溢出会出现不会适用场景已知最大容量无法预估容量七、高频试题必背队列的特点是什么先进先出FIFO。链式队列入队、出队分别在什么位置入队在队尾rear出队在队头front。链式队列有没有队满一般认为没有只有内存不足时才会申请失败。空队列的标志是什么front NULL rear NULL。链式队列和顺序队列最大区别顺序队列会假溢出链式队列不会。时间复杂度入队、出队、取队头O(1)