引言在上一篇文章中我们讲解了基于单向链表的链式队列。单向链式队列虽然能实现 O(1) 的入队和出队但获取队尾元素需要依赖rear指针且无法从队尾方向遍历。本文介绍的双向循环链式队列在每个节点上增加了prev指针并将整个链表设计为循环结构。这种设计带来的优势是队列可以双向遍历删除节点时不需要额外的指针判断操作更加统一。第一部分数据结构设计一、核心结构体// 双向循环节点 typedef struct CycleQueuenode { ElempType val; // 数据域 struct CycleQueuenode* prev; // 前驱指针 struct CycleQueuenode* next; // 后继指针 } CycleQueuenode, *PCycleQueuenode; // 队列管理结构体带头结点 typedef struct CycleLinkQueue { PCycleQueuenode front; // 队头指针指向头结点 PCycleQueuenode rear; // 队尾指针指向最后一个实际节点 } CycleLinkQueue, *PCycleLinkQueue;二、循环结构设计第二部分初始化与节点管理一、初始化void InitCycleLinkQueue(PCycleLinkQueue ps) { assert(ps ! NULL); // 创建头结点 CycleQueuenode* p (CycleQueuenode*)malloc(sizeof(CycleQueuenode)); if (p NULL) return; // 头结点的 prev 和 next 都指向自己 p-prev p; p-next p; // 空队列front 和 rear 都指向头结点 ps-front p; ps-rear p; }二、创建节点CycleQueuenode* buynode(ElempType val) { CycleQueuenode* p (CycleQueuenode*)malloc(sizeof(CycleQueuenode)); if (p NULL) return NULL; // 新节点的 prev 和 next 先指向自己 p-prev p; p-next p; p-val val; return p; }设计要点新节点创建时prev和next指向自己这是一个安全的默认状态。入队时再根据实际位置调整指针。三、判空bool Isempty(const PCycleLinkQueue ps) { assert(ps ! NULL); return ps-front ps-rear; }第三部分核心操作实现一、入队Push原代码中Push函数的指针调整逻辑存在错误以下是修正后的正确实现bool Push(PCycleLinkQueue ps, ElempType val) { assert(ps ! NULL); // 1. 创建新节点 CycleQueuenode* p buynode(val); if (p NULL) return false; // 2. 获取当前队尾节点 CycleQueuenode* rear ps-rear; // 3. 调整指针在 rear 之后插入新节点 p-next rear-next; // 新节点的 next 指向头结点 rear-next-prev p; // 头结点的 prev 指向新节点 p-prev rear; // 新节点的 prev 指向原队尾 rear-next p; // 原队尾的 next 指向新节点 // 4. 更新队尾指针 ps-rear p; return true; }入队过程图解正确的插入步骤二、出队Popbool Pop(PCycleLinkQueue ps, ElempType* pval) { assert(ps ! NULL pval ! NULL); if (Isempty(ps)) return false; // 1. 获取队头节点头结点后的第一个节点 CycleQueuenode* p ps-front-next; // 2. 获取数据 *pval p-val; // 3. 调整指针跳过被删除的节点 ps-front-next p-next; p-next-prev ps-front; // 4. 特殊处理如果删除的是最后一个节点rear 回退到头结点 if (p ps-rear) { ps-rear ps-front; } // 5. 释放节点 free(p); return true; }注意原代码中缺少了rear回退的特殊处理。当队列只有一个元素时出队后rear应该回退到头结点。出队过程图解三、获取队头和队尾// 获取队头元素 bool Getfront(PCycleLinkQueue ps, ElempType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; *pval ps-front-next-val; return true; } // 获取队尾元素 bool Getrear(PCycleLinkQueue ps, ElempType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; *pval ps-rear-val; return true; }四、获取元素个数int Getsize(const PCycleLinkQueue ps) { assert(ps ! NULL); int n 0; // 从头结点的下一个节点开始遍历到头结点结束 for (CycleQueuenode* p ps-front-next; p ! ps-front; p p-next) { n; } return n; }五、清空和销毁// 清空保留头结点 void Clear(PCycleLinkQueue ps) { assert(ps ! NULL); if (Isempty(ps)) return; CycleQueuenode* p ps-front-next; while (p ! ps-front) { CycleQueuenode* q p-next; free(p); p q; } // 恢复头结点的循环状态 ps-front-next ps-front; ps-front-prev ps-front; ps-rear ps-front; } // 销毁释放所有节点包括头结点 void Destroy(PCycleLinkQueue ps) { assert(ps ! NULL); // 先释放所有数据节点 CycleQueuenode* p ps-front-next; while (p ! ps-front) { CycleQueuenode* q p-next; free(p); p q; } // 释放头结点 free(ps-front); // 指针置空 ps-front NULL; ps-rear NULL; }第四部分打印遍历void Print(PCycleLinkQueue ps) { assert(ps ! NULL); if (ps-front NULL) { printf(队列已销毁无法打印\n); return; } // 从头结点的下一个节点开始遍历到头结点结束 for (CycleQueuenode* p ps-front-next; p ! ps-front; p p-next) { printf(%c , p-val); } printf(\n); }遍历终止条件双向循环链表的遍历终止条件是p ! ps-front即当遍历指针回到头结点时停止。第五部分单向 vs 双向循环链式队列对比项单向链式队列双向循环链式队列节点指针数1 个next2 个prev next内存开销低高每节点多一个指针正向遍历✅ O(n)✅ O(n)反向遍历❌ 不支持✅ O(n)获取队尾O(1)rear 指针O(1)rear 指针删除节点O(1)头部O(1)头部循环结构非循环头尾相连循环判空front rearfront rear实现复杂度简单稍复杂第六部分完整测试代码int main() { CycleLinkQueue l; InitCycleLinkQueue(l); // 入队测试 printf(入队测试\n); for (int i 0; i 5; i) { Push(l, i); } Print(l); // 输出0 1 2 3 4 // 出队测试 printf(\n出队测试\n); ElempType p; Pop(l, p); printf(出队元素%c\n, p); Print(l); // 输出1 2 3 4 // 获取队头队尾测试 printf(\n队头队尾测试\n); Getfront(l, p); printf(队头%c\n, p); Getrear(l, p); printf(队尾%c\n, p); // 清空测试 printf(\n清空测试\n); Clear(l); printf(清空后大小%d\n, Getsize(l)); // 销毁测试 Destroy(l); Print(l); // 输出队列已销毁无法打印 return 0; }运行结果入队测试0 1 2 3 4出队测试出队元素01 2 3 4队头队尾测试队头1队尾4清空测试清空后大小0队列已销毁无法打印总结一、双向循环链式队列核心要点操作关键步骤时间复杂度入队在 rear 和 head 之间插入新节点O(1)出队删除 front-next调整 prevO(1)获取队头front-next-valO(1)获取队尾rear-valO(1)判空front rearO(1)二、入队四步法在 rear 和 head 之间插入新节点 p① p-next rear-next → 新节点后继指向头结点② rear-next-prev p → 头结点的前驱指向新节点③ p-prev rear → 新节点前驱指向原队尾④ rear-next p → 原队尾后继指向新节点⑤ ps-rear p → 更新队尾指针三、一句话记忆双向循环链式队列在单向链式队列的基础上给每个节点增加了 prev 指针头尾节点通过 prev 和 next 首尾相连形成闭环入队时在 rear 和头结点之间插入新节点出队时删除 front-next所有操作均为 O(1)。