文章目录队列的链式实现代码实现结构定义与初始化带头结点不带头结点入队尾插法带头结点不带头结点出队带头结点不带头结点查队头销毁队列的链式实现链队列是队列的链式存储结构本质上是操作受限的单链表。其解决了顺序队列循环队列“容量固定、可能溢出”的缺陷。链队列需要两个指针front队头指针指向头结点注意不是第一个数据结点。头结点的data闲置next指向真正的首元结点。rear队尾指针指向最后一个数据结点尾结点。带头结点后空队时front rear均指向头结点所有操作逻辑完全统一。图示空队 front(rear) - [头结点 | nextNULL] 入队10 front - [头结点 | next] - [10 | NULL] rear-^ 入队20 front - [头结点 | next] - [10 | next] - [20 | NULL] rear -^代码实现结构定义与初始化与顺序队列不同链队列通常将front和rear封装在一个结构体中便于函数传参。带头结点#includestdio.h#includestdlib.h#includestdbool.h// ① 结点定义与单链表完全一样typedefstructLNode{intdata;structLNode*next;}LNode;// ② 链队列定义封装了队头和队尾指针typedefstruct{LNode*front;// 队头指针指向头结点LNode*rear;// 队尾指针指向最后一个结点}LinkQueue;// 带头结点// 初始化 创建空队列创建头结点boolInitQueue(LinkQueueQ){// 1. 申请头结点空间 队尾指针也指向头结点表示空队Q.frontQ.rear(LNode*)malloc(sizeof(LNode));if(Q.frontNULL)returnfalse;// 内存分配失败// 2. 头结点的 next 置空Q.front-nextNULL;returntrue;}// 判空boolQueueEmpty(LinkQueue Q){returnQ.frontQ.rear;// 或者 Q.front-next NULL 若 front rear 则为空}// 判满 链队列不存在 “满 ”的概念// 唯一的限制是堆内存耗尽。通常不写判满函数而是在入队时检测 malloc 返回值。boolQueueFull(LinkQueue Q){returnfalse;// 理论永远不满只要内存够}不带头结点#includestdio.h#includestdlib.h#includestdbool.htypedefstructLNode{intdata;structLNode*next;}LNode;typedefstruct{LNode*front;// 队头指针指向第一个数据结点不是头结点LNode*rear;// 队尾指针指向最后一个数据结点}LinkQueue;// 不带头结点// 初始化 创建空队列不分配头结点voidInitQueue(LinkQueueQ){Q.frontNULL;// 直接置空Q.rearNULL;// 直接置空}// 判空boolQueueEmpty(LinkQueue Q){returnQ.frontNULL;// 只要队头为空队列就为空// 也可以这样判断Q.rear NULL;}入队尾插法带头结点步骤新建结点 → 接到rear后面 → 更新rear为新结点// 带头结点// 入队 在队尾rear 后面插入元素 eboolEnQueue(LinkQueueQ,inte){// 1. 申请新结点空间LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;// 内存耗尽相当于 “队满 ”// 2. 初始化新结点s-datae;s-nextNULL;// 3. 将新结点挂到当前尾结点后面Q.rear-nexts;// 4. 尾指针后移指向新的尾结点Q.rears;returntrue;}不带头结点// 不带头结点// 入队 在队尾插入元素 eboolEnQueue(LinkQueueQ,inte){LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;s-datae;s-nextNULL;// 必须特别判断是不是第一个结点// 不带头结点的队列第一个元素入队时需要特别处理if(Q.frontNULL){// 情况1空队front 和 rear 都指向新结点Q.fronts;// 修改队头队尾指针Q.rears;}else{// 情况2非空队挂在尾结点后面Q.rear-nexts;// 新结点插入到 rear 结点之后Q.rears;// 修改 rear 指针}returntrue;}出队删除队头第一个有效结点特殊边界如果删除后队列为空需要将rear重置回头结点防止rear悬空。带头结点删除头结点的后继。// 带头结点// 出队 删除队头元素并通过 e 带回其值boolDeQueue(LinkQueueQ,inte){// 1. 判空if(Q.frontQ.rear)returnfalse;// 2. p 指向首元结点第一个数据结点LNode*pQ.front-next;ep-data;// 保存数据// 3. 头结点跨过 p指向 p 的下一个结点Q.front-nextp-next;// 注意如果 p 恰好是最后一个结点即出队后队列变空// 必须把 rear 重新指向头结点否则 rear 将指向已释放的内存if(pQ.rear){Q.rearQ.front;}// 4. 释放 p 结点内存free(p);returntrue;}不带头结点// 不带头结点// 出队 删除队头元素并通过 e 带回其值boolDeQueue(LinkQueueQ,inte){// 1. 判空if(Q.frontNULL)returnfalse;// 2. p 指向队头结点直接就是 frontLNode*pQ.front;ep-data;// 3. 队头指针后移指向下一个数据结点Q.frontp-next;// 如果删除的是唯一结点出队后队列变空if(Q.frontNULL){// 必须把 rear 也置为 NULL否则 rear 指向已释放的内存Q.rearNULL;}// 或这样写// if(Q.rear p ){// Q.rear NULL;// Q.front NULL;// }free(p);returntrue;}查队头// 带头结点// 查队头 只读操作不删除元素boolGetHead(LinkQueue Q,inte){if(Q.frontQ.rear)// 空队returnfalse;eQ.front-next-data;// 头结点的后继才是第一个数据returntrue;}// 不带头结点// 查队头 只读操作boolGetHead(LinkQueue Q,inte){if(Q.frontNULL)returnfalse;eQ.front-data;// front 直接指向数据结点无需绕 -nextreturntrue;}销毁// 带头结点// 销毁 释放所有结点包括头结点voidDestroyQueue(LinkQueueQ){LNode*pQ.front;// p 从头结点开始while(p!NULL){LNode*qp;pp-next;free(q);}// 防止野指针虽然 Q 是引用但置空是好习惯Q.frontNULL;Q.rearNULL;}// 不带头结点// 销毁 释放所有数据结点voidDestroyQueue(LinkQueueQ){LNode*pQ.front;while(p!NULL){LNode*qp;pp-next;free(q);}Q.frontNULL;Q.rearNULL;}链队列是采用链式存储结构的队列通常使用带头结点的单链表实现并附设front和rear两个指针分别指向头结点和尾结点。入队操作对应单链表的尾插法rear-next s; rear s;出队操作对应删除头结点的后继结点。在出队时若被删结点是尾结点必须将rear重置为front。链队列克服了顺序队列容量固定的缺陷入队、出队、判空操作的时间复杂度均为O(1)。