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

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

MySQL 从入门到精通完全教程

目录 1. 前言 2. MySQL 基础认知 3. MySQL 安装与配置 4. MySQL 核心语法 5. 高级查询技巧 6. MySQL 函数 7. 数据约束 8. 事务管理 9. 索引优化 10. 存储过程与函数 11. 用户与权限管理 12. 性能优化实战 13. 常见问题与解决方案 1. 前言 1.1 什么是MySQL？ MySQL 是一款开源的关系型数据库管理系统（RDBMS），基于SQL（结构化查询语言）实现数据管理，广泛应用于Web开发（如PHP+MySQL、Python+MySQL），特点是轻量、高效、跨平台、

By Ne0inhk
MySQL 进阶：库与表的DDL核心操作全指南（含实战案例）

MySQL 进阶：库与表的DDL核心操作全指南（含实战案例）

🔥草莓熊Lotso：个人主页 ❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》 ✨生活是默默的坚持，毅力是永久的享受！ 🎬 博主简介： 文章目录 * 前言： * 一. 数据库（库）的核心操作 * 1.1 创建数据库：指定字符集与校验规则 * 1.1.1 语法格式 * 1.1.2 实战案例 * 1.2 字符集与校验规则：影响查询和排序 * 1.2.1 查看系统默认配置 * 1.2.2 查看支持的字符集和校验规则 * 1.2.3 校验规则的实际影响 * 1.3 操纵数据库：查询、修改、

By Ne0inhk
SpringBoot 整合 Langchain4j 实现会话记忆存储深度解析

SpringBoot 整合 Langchain4j 实现会话记忆存储深度解析

目录 一、前言 二、AI大模型会话记忆介绍 2.1 AI 大模型的会话记忆是什么 2.2 AI 大模型为什么需要会话记忆 2.3 AI 大模型会话记忆常用实现方案 2.4 LangChain4j 会话记忆介绍 2.4.1 LangChain4j 会话记忆介绍 2.4.2 LangChain4j 会话记忆类型 三、Langchain4j 会话记忆操作案例使用 3.1 前置准备 3.1.1 导入依赖文件 3.1.2 添加配置文件 3.1.3 前置案例 3.

By Ne0inhk