【数据结构】队列的完整实现

Ne0inhk

— 14 min read
【数据结构】队列的完整实现

队列的完整实现

队列的完整实现

github地址

有梦想的电信狗

前言

​ 队列（Queue）作为一种基础且重要的数据结构，在计算机科学中扮演着关键角色。无论是操作系统的任务调度、网络数据包的管理，还是算法中的广度优先搜索（BFS），队列的“先进先出”（FIFO）特性都使其成为不可或缺的工具。理解队列的实现原理，不仅能帮助开发者更高效地处理数据，还能为后续学习复杂的数据结构打下坚实基础。

​ 本文将以 链式结构 为核心，详细介绍队列的完整实现。从结构设计、接口定义到功能测试，一步步剖析如何用C语言实现一个高效、健壮的队列。文章重点讲解入队（push）、出队（pop）、获取队头/队尾元素等核心操作，并通过清晰的代码示例和测试案例，帮助读者深入理解队列的内部机制。此外，所有代码已在GitHub开源，方便读者参考和扩展。

1. 队列的概念及其结构

1.1 概念

​ 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的特性

  • 入队列：进行插入操作的一端称为队尾，入队常被称为push
  • 出队列：进行删除操作的一端称为队头，出队常被称为pop

如下图所示

在这里插入图片描述

1.2 组织结构

  • 队列可以使用数组和链表的结构实现，使用链表的结构实现更优一些。
  • 因为如果使用数组的结构，出队列时，在数组头上出数据，效率会比较低
  • 而对于链表实现的队列来说，入队对应尾插操作，出队对应头删操作。在链表中，头删和尾插操作只需要O(1)时间复杂度，因此队列更适合使用链表来实现，本文我们采用单链表来实现。
在这里插入图片描述

2. 队列的实现

接口一览

//初始化 与 销毁队列voidQueueInit(Queue* pQueue);voidQueueDestroy(Queue* pQueue);// 队尾入队列 队头出队列voidQueuePush(Queue* pQueue, QDataType data);voidQueuePop(Queue* pQueue);// 获取队列头部元素 /获取队列尾部元素 QDataType QueueFront(Queue* pQueue); QDataType QueueBack(Queue* pQueue);//获取队列中有效元素个数 检测队列是否为空，如果为空返回非零结果，如果非空返回0intQueueSize(Queue* pQueue);boolQueueEmpty(Queue* pQueue);

结构定义与架构

结构：

//队列，先进先出，数组的话在头部出数据不方便，因此用链表来实现，单链表typedefint QDataType;typedefstructQNode{//链式队列，用单链表实现structQNode* next; QDataType data;}QNode;//队列中 用两个指针来指示 队头和队尾，方便入队和出队typedefstructQueue{ QNode* head; QNode* tail;int size;}Queue;
  • 使用typedef int QDataType方便队列中存放不同的数据类型
  • QNode表示我们链表中一个个的结点，内部包含next指针和数据data
  • 使用struct Queue结构来表示整个队列，其中：
    • 规定两个QNode*的指针，分别保存链表第一个结点和尾结点的地址(分别指向第一个结点和最后一个结点)
    • 定义int size来保存队列中的有效元素个数。

架构图如下：

在这里插入图片描述

初始化和销毁

初始化：

//初始化 与 销毁队列voidQueueInit(Queue* pQueue){assert(pQueue); pQueue->head = pQueue->tail =NULL; pQueue->size =0;}
  • 通过Queue结构体的指针pQueue，来访问结构体中的成员head和tail，通过head和tail指针和链表的特性，可以访问到链表中的每个结点。head和tail指针主要是为了方便访问队头结点和队尾结点。
  • assert(pQueue)保证Queue结构存在
  • 初始化队列：
    • 链表中无节点时，head和tail指针都置为NULL
    • 初始化size为0

销毁：

//销毁voidQueueDestroy(Queue* pQueue){assert(pQueue);// 空链表也可以销毁，因此无需断言链表非空 QNode* cur = pQueue->head;while(cur !=NULL){ QNode* next = cur->next;free(cur); cur = next;} pQueue->head = pQueue->tail =NULL; pQueue->size =0;}
  • assert(pQueue)保证Queue结构存在
  • QNode* cur = pQueue->head：cur保存当前头结点的地址
    • while循环依次释放每一个结点
    • 保存cur的下一个节点cur->next
    • free(cur)释放当前结点，cur移动指向下一个节点，直到NULL时结束
  • pQueue->head = pQueue->tail = NULL：将head和tail指针各自置NULL
  • pQueue->size = 0最后将size置0

入队和出队

入队：

// 队尾入队列 队头出队列voidQueuePush(Queue* pQueue, QDataType data){assert(pQueue);// 开辟新结点，并将数据置于新结点中 QNode* newNode =(QNode*)malloc(sizeof(QNode));if(newNode ==NULL){perror("malloc failed\n");return;} newNode->data = data; newNode->next =NULL;// 初始化后，head 和 tail 都为NULLif(pQueue->head ==NULL){assert(pQueue->tail ==NULL);// head为NULL时，tail必须也为NULL pQueue->head = pQueue->tail = newNode;}else{ pQueue->tail->next = newNode; pQueue->tail = newNode;} pQueue->size++;}
  • assert(pQueue)保证Queue结构存在
  • QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc failed\n"); return; }开辟一个新结点，并进行初始化。
  • 初始化QNode后，push 一个结点本质是单链表的尾插，有两种情况：
    • 队列为空(队列中无节点)时：新开辟的QNode应当成为链表中的第一个节点，pQueue->head = pQueue->tail = newNode操作调整首尾指针即可。
    • 队列中已有其他结点时：此时是单链表的尾插。
      • pQueue->tail->next = newNode：新结点链入原链表
      • pQueue->tail = newNode：更改尾指针指向
  • push过后，pQueue->size++，队列的size应当++

出队：

v1版本仅实现：

voidQueuePop(Queue* pQueue){assert(pQueue);assert(pQueue->head !=NULL);//if(pQueue->head->next == NULL){} //考虑只剩一个结点的情况if(pQueue->head == pQueue->tail){free(pQueue->head); pQueue->head = pQueue->tail =NULL;}else{ QNode* cur = pQueue->head; pQueue->head = pQueue->head->next;free(cur); cur =NULL;} pQueue->size--;}
  • assert(pQueue)：断言队列存在，assert(pQueue->head != NULL)，确保pop时队列内有元素
  • pop出队时，销毁第一个结点，确保队列存在且有元素后，此处存在两种情况
    • 当前仅剩一个结点时：pQueue->head == pQueue->tail，直接free当前头结点，将head和tail指针置NULL即可
    • 当前存在多个节点时(else)：
      • QNode* cur = pQueue->head：记录下当前的头结点
      • pQueue->head = pQueue->head->next：头指针向后移动
      • free(cur)后cur = NULL释放之前的头结点的空间，并将cur置NULL
  • pop后size应当--

v2版本优化：

  • 可以看到，上述的代码中存在多次free，且都是对要被删除的结点进行free，那么是否可以优化为一次free呢
voidQueuePop(Queue* pQueue){assert(pQueue);assert(pQueue->head !=NULL);//优化版本 QNode* cur = pQueue->head;if(pQueue->head == pQueue->tail) pQueue->head = pQueue->tail =NULL;else pQueue->head = pQueue->head->next;free(cur); cur =NULL; pQueue->size--;}
  • assert(pQueue)：断言队列存在，assert(pQueue->head != NULL)，确保pop时队列内有元素
  • QNode* cur = pQueue->head：不管队列中剩余几个结点，最终都要free头结点，那么cur直接保存头结点的地址，方便进行操作
  • pQueue->head == pQueue->tail仅剩一个结点时：仅需对head和tail指针做修改。有多个节点时，pQueue->head = pQueue->head->next，head指针向后移动。
  • 最终cur内保存了要被删除的结点的地址，直接free(cur)并置NULL
  • pop后size应当--

取队头队尾数据

获取队头数据：

// 获取队列头部元素 获取队列尾部元素 QDataType QueueFront(Queue* pQueue){assert(pQueue);//确保队列非空assert(!QueueEmpty(pQueue));return pQueue->head->data;}
  • assert(pQueue)确保队列存在，assert(!QueueEmpty(pQueue))确保队列非空，非空队列内才有数据
  • 头部数据：return pQueue->head->data，通过头指针head访问队列内第一个结点的数据

获取队尾数据：

//获取队列尾部元素 QDataType QueueBack(Queue* pQueue){assert(pQueue);//确保队列非空assert(!QueueEmpty(pQueue));return pQueue->tail->data;}
  • assert(pQueue)确保队列存在，assert(!QueueEmpty(pQueue))确保队列非空，非空队列内才有数据
  • 尾部数据：return pQueue->tail->data，通过尾指针tail访问队列内最后一个结点的数据

获取size和判空

获取size：

intQueueSize(Queue* pQueue){assert(pQueue);return pQueue->size;}
  • assert(pQueue)：断言指针非空，确保Queue结构体存在
  • 直接返回size即可得到元素个数
    • 这里就体现出我们在Queue结构中添加一个size成员的好处，只需在每次Push/Pop后对size进行加减，即可方便的得到队列的size
    • 如果Queue结构内不维护一个size变量的话，由于我们的队列是基于单链表实现的，每次获取队列的大小时都只能遍历链表来得到size，遍历的时间复杂度较高。

判空：

boolQueueEmpty(Queue* pQueue){assert(pQueue);//return (pQueue->head == NULL && pQueue->tail == NULL);return pQueue->size ==0;// size为0时为空}
  • assert(pQueue)：断言指针非空，确保Queue结构体存在
  • pQueue->size == 0或pQueue->head == NULL && pQueue->tail == NULL，两个条件均可以标识队列为空

完整代码与功能测试

完整代码如下：

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//队列，先进先出，数组的话在头部出数据不方便，因此用链表来实现，单链表typedefint QDataType;typedefstructQNode{//链式队列，用单链表实现structQNode* next; QDataType data;}QNode;//队列中 用两个指针来指示 队头和队尾，方便入队和出队typedefstructQueue{ QNode* head; QNode* tail;int size;}Queue;//初始化 与 销毁队列voidQueueInit(Queue* pQueue);voidQueueDestroy(Queue* pQueue);// 队尾入队列 队头出队列voidQueuePush(Queue* pQueue, QDataType data);voidQueuePop(Queue* pQueue);// 获取队列头部元素 /获取队列尾部元素 QDataType QueueFront(Queue* pQueue); QDataType QueueBack(Queue* pQueue);//获取队列中有效元素个数 检测队列是否为空，如果为空返回非零结果，如果非空返回0intQueueSize(Queue* pQueue);boolQueueEmpty(Queue* pQueue);// #include "Queue.h" 多文件编译时，需正确包含头文件//初始化 与 销毁队列voidQueueInit(Queue* pQueue){assert(pQueue); pQueue->head = pQueue->tail =NULL; pQueue->size =0;}//销毁voidQueueDestroy(Queue* pQueue){assert(pQueue); QNode* cur = pQueue->head;while(cur !=NULL){ QNode* next = cur->next;free(cur); cur = next;} pQueue->head = pQueue->tail =NULL; pQueue->size =0;}// 队尾入队列 队头出队列voidQueuePush(Queue* pQueue, QDataType data){assert(pQueue); QNode* newNode =(QNode*)malloc(sizeof(QNode));if(newNode ==NULL){perror("malloc failed\n");return;} newNode->data = data; newNode->next =NULL;// 初始化后，head 和 tail 都为NULLif(pQueue->head ==NULL){assert(pQueue->tail ==NULL);// head为NULL时，tail必须也为NULL pQueue->head = pQueue->tail = newNode;}else{ pQueue->tail->next = newNode; pQueue->tail = newNode;} pQueue->size++;}//队列的头删法voidQueuePop(Queue* pQueue){assert(pQueue);assert(pQueue->head !=NULL);////if(pQueue->head->next == NULL){} //考虑只剩一个结点的情况//if (pQueue->head == pQueue->tail) { // free(pQueue->head);// pQueue->head = pQueue->tail = NULL;//}//else {// QNode* cur = pQueue->head;// pQueue->head = pQueue->head->next;// free(cur);// cur = NULL;//}//pQueue->size--;//优化版本 QNode* cur = pQueue->head;if(pQueue->head == pQueue->tail) pQueue->head = pQueue->tail =NULL;else pQueue->head = pQueue->head->next;free(cur); cur =NULL; pQueue->size--;}// 获取队列头部元素 获取队列尾部元素 QDataType QueueFront(Queue* pQueue){assert(pQueue);//确保队列非空assert(!QueueEmpty(pQueue));return pQueue->head->data;}//获取队列尾部元素 QDataType QueueBack(Queue* pQueue){assert(pQueue);//确保队列非空assert(!QueueEmpty(pQueue));return pQueue->tail->data;}//获取队列中有效元素个数 检测队列是否为空，如果为空返回非零结果，如果非空返回0// 双向链表中，不能用 哨兵位的数据 来存储 链表的长度// 之前的实现中，结点内存放的数据是int，导致哨兵位内的数据位类型也是int,intQueueSize(Queue* pQueue){assert(pQueue);return pQueue->size;}boolQueueEmpty(Queue* pQueue){assert(pQueue);//return (pQueue->head == NULL && pQueue->tail == NULL);return pQueue->size ==0;// size为0时为空}

功能测试：

// 需正确包含头文件#include"Queue.h"voidTestQueue(){ Queue queue;QueueInit(&queue);QueuePush(&queue,1);QueuePush(&queue,2);QueuePush(&queue,3);QueuePush(&queue,4);QueuePush(&queue,6);// 遍历的代码/*while (!QueueEmpty(&queue)) { printf("%d ", QueueFront(&queue)); QueuePop(&queue); }*/printf("队尾：%d 有效元素个数：%d\n",QueueBack(&queue),QueueSize(&queue));printf("队头：%d 有效元素个数：%d\n",QueueFront(&queue),QueueSize(&queue));QueuePop(&queue);printf("队尾：%d 有效元素个数：%d\n",QueueBack(&queue),QueueSize(&queue));printf("队头：%d 有效元素个数：%d\n",QueueFront(&queue),QueueSize(&queue));QueuePop(&queue);printf("队尾：%d 有效元素个数：%d\n",QueueBack(&queue),QueueSize(&queue));printf("队头：%d 有效元素个数：%d\n",QueueFront(&queue),QueueSize(&queue));QueuePop(&queue);QueuePop(&queue);printf("队列有效元素个数：%d\n",QueueSize(&queue));while(!QueueEmpty(&queue)){printf("%d ",QueueFront(&queue));QueuePop(&queue);}QueueDestroy(&queue);}//函数调用的栈帧 和 数据结构的栈// 函数调用的栈帧 是操作系统层面对内存区域的划分// 和 数据结构的栈intmain(){TestQueue();return0;}
在这里插入图片描述

结语

通过本文的学习，我们完成了队列的完整实现：从结构体设计到核心接口的实现，再到功能验证。关键点包括：

  1. 链式结构的优势：使用单链表实现队列，确保入队（尾插）和出队（头删）操作的时间复杂度均为 O(1)。
  2. 双指针的妙用：通过 head 和 tail 指针分别标记队头和队尾，避免了遍历链表的性能损耗。
  3. 健壮性保障：通过断言（assert）确保操作合法性，并结合 size 字段快速判断队列状态。

希望本文能帮助你彻底掌握队列的实现原理，并激发对数据结构更深层次的探索。

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀

Read more

SQL Prompt 通用破解步骤（主要依据v10）

原文 以下流程梳理自搜索结果，并提醒您注意其中的风险点和差异。 1. 环境准备与安装 * 确认SSMS版本兼容性 ：SQL Prompt 对 SQL Server Management Studio (SSMS) 的版本有要求。例如，SQL Prompt 10 支持 SSMS 2012 至 2018。请确保您的SSMS版本在其支持范围内。 * 获取安装包和注册机 ：网络上流传的破解资源包通常包含 SQL Prompt 安装程序（如 SQLPrompt_10.6.19.22009.exe）和注册机（如 SQL.Prompt.Keygen.exe）。 注册机极易被杀毒软件报毒，使用时通常需要暂时关闭杀毒软件或添加信任，但这会增加安全风险。 * 安装 ：以管理员身份运行安装程序，并按照提示完成安装。 2.

By Ne0inhk
构建基于 Rust 与 GLM-5 的高性能 AI 翻译 CLI 工具：从环境搭建到核心实现全解析

构建基于 Rust 与 GLM-5 的高性能 AI 翻译 CLI 工具：从环境搭建到核心实现全解析

前言 随着大语言模型（LLM）能力的飞速提升，将 AI 能力集成到终端命令行工具（CLI）中已成为提升开发效率的重要手段。Rust 语言凭借其内存安全、零成本抽象以及极其高效的异步运行时，成为构建此类高性能网络 IO 密集型应用的首选。本文将深度剖析如何使用 Rust 语言，结合智谱 AI 的 GLM-5 模型，从零构建一个支持流式输出、多语言切换及文件批处理的 AI 翻译引擎。 本文将涵盖环境配置、依赖管理、异步网络编程、流式数据处理（SSE）、命令行参数解析以及最终的二进制发布优化。 第一部分：Rust 开发环境的系统级构建 在涉足 Rust 编程之前，必须确保底层操作系统具备必要的构建工具链。Rust 虽然拥有独立的包管理器，但在链接阶段依赖于系统的 C 语言编译器和链接器，尤其是在涉及网络库（如 reqwest 依赖的 OpenSSL）

By Ne0inhk
用 C# 调用 OpenAI 大模型实战：从 Demo 到企业级封装完整架构

用 C# 调用 OpenAI 大模型实战：从 Demo 到企业级封装完整架构

2026 年，如果你的 C# 项目还没有接入 AI，大概率正在被边缘化。 过去两年，AI 生态几乎被 Python 占领。但在企业级系统中，C# 才是真正的主力军。 那么问题来了： 👉 C# 如何优雅接入大模型？ 👉 如何从简单 Demo 升级为企业级可维护架构？ 👉 如何实现流式输出、异常重试、限流控制？ 这篇文章我不讲“Hello World”，而是直接带你构建一个可商用的封装架构。 一、为什么 C# 接入 AI 是趋势？ 很多人误以为： AI = Python 但企业系统 70% 以上仍然是： * .NET * Java * 微服务架构 特别是 .NET 生态在： * 云原生 * 微服务 * 跨平台 * Native

By Ne0inhk
让数据库学会说“不“——金仓 SQL 防火墙深度解析

让数据库学会说“不“——金仓 SQL 防火墙深度解析

文章目录 * 前言 * 一、SQL 注入原理：攻击者如何"钻空子" * 二、SQL 防火墙原理：白名单驱动的主动防护 * 三、核心优势 * 1. 准确率高达 99.99% * 2. 性能损耗极低，稳定可控 * 3. 两步完成配置，上手门槛低 * 四、总结：让数据库学会辨别"友军"与"异己" 前言 SQL 注入是数据库安全领域最顽固的威胁之一。即便开发团队严格执行预编译与输入过滤，遗留代码、第三方组件或偶发的人为疏忽，依然可能留下可被利用的突破口。面对这一长期存在的安全隐患，单纯依赖应用层的"亡羊补牢"已难以为继。 金仓数据库（KingbaseES）

By Ne0inhk