数据结构队列详解：从概念到代码实现

个人专栏《数据结构-初阶》《经典OJ题目》《C语言》欢迎各位大佬交流目录一、队列的概念及结构1、队列的基本概念2、队列的结构二、代码实现0、初始化1、入队2、出队3、获取队头元素4、获取队尾元素5、获取队列中有效元素个数6、检测队列是否为空7、销毁队列三、测试代码1、测试入队 出队 判空2、测试获取队头元素3、测试获取队尾元素一、队列的概念及结构1、队列的基本概念队列是一种线性数据结构遵循**先进先出FIFO, First In First Out**原则最早进入队列的元素最先被移除类似于现实生活中的排队场景队列的操作通常限制在两端进行元素从队尾rear入队从队头front出队2、队列的结构队列的存储结构既可以用数组来实现也可以用链表来实现注意此处我们说的链表是单链表不考虑双向链表是因为双向链表空间较大且双向链表功能复杂性能较低那么到底是用数组来实现栈还是链表呢同样地我们和分析栈的实现方式一样通过一些操作的时间复杂度来来进行分析a、对于入队而言如果是链表实现的队列首先需要找到队尾元素这样就需要O(N)级别的时间复杂度如果是数组实现的队列我们可以判断完空间情况后直接利用 top 尾插属于O(1)级别b、对于出队而言如果是链表实现的队列更改释放完头节点后更改头节点即可O(1)级别如果是数组实现的队列想要出队就需要从第二个节点开始均向前挪动一位属于O(N)级别显然我们不想频繁地移动数据但是如果使用链表的话入队又是O(N)级别的该怎么优化呢为什么入队是O(N)级别的是因为每次都需要遍历一遍队列才能找到最后一个节点那不妨我们在设计参数时带上尾指针这样不就将O(N)降低到了O(1)级别吗这样的话我们在入队时传入的参数就有三个分别是头指针尾指针变量x并且传入的还得是二级指针这样就使得函数看起来很冗余能不能再优化一下如果我们定义一个结构体包含头尾指针会怎样这样每次传入只需要传入这个结构体的地址即可并且用一级指针来接收完全可行这样就使得函数显得简洁、高效综上我们选择用链表来实现队列二、代码实现注意我们是用链表来实现栈说明由于队列的实现较为简单因此所有函数都封装好之后再一起测试首先来完成准备工作同样创建三个文件Queue.c、Queue .h、test.c接着定义出Queue结构体#include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int QDatatype; //定义Queue typedef struct QListNode { struct QListNode* next; QDatatype val; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; }Queue;0、初始化分析逻辑将Queue结构体中phead 和 ptail 置为空//初始化 void QueueInit(Queue* pq) { assert(pq); pq-phead pq-ptail NULL; //在获取队列中有效元素个数中说明size pq-size 0; }1、入队分析逻辑首先申请节点空间记得将 val 置为 xnext 置为空接着判断是否是入队的第一个元素如果是就要修改头尾指针否则就直接像链表尾插操作一样//入队 void QueuePush(Queue* pq, QDatatype x) { assert(pq); assert(pq-phead); //申请节点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc failed!\n); return; } newnode-val x; newnode-next NULL; if (pq-ptail NULL) { //第一个入队元素 pq-phead pq-ptail newnode; } else { //直接在队尾插入 pq-ptail-next newnode; pq-ptail newnode; } //在获取队列中有效元素个数中说明size pq-size; }2、出队分析逻辑注意出队是从头节点那一端出队由链表中头删的经验可知无论是一个元素还是多个元素删除逻辑都是一样的因此我们先暂存头节点的下一个节点next接着 free 头节点最终将 next 赋值给 头节点最后一个元素出队后将尾指针置为空//出队 void QueuePop(Queue* pq) { assert(pq); //队列不能为空 assert(pq-size 0); QNode* next pq-phead-next; free(pq-phead); pq-phead next; if (pq-phead NULL) { pq-ptail NULL; } //在获取队列中有效元素个数中说明size pq-size--; }3、获取队头元素分析逻辑直接返回头节点的 val 即可//获取队头元素 QDatatype QueueFront(Queue* pq) { assert(pq); assert(pq-phead); return pq-phead-val; }4、获取队尾元素分析逻辑直接返回尾节点的 val 即可//获取队尾元素 QDatatype QueueBAck(Queue* pq) { assert(pq); assert(pq-ptail); return pq-ptail-val; }5、获取队列中有效元素个数分析逻辑注意不能直接用尾指针 - 头指针两者并非顺序存储那难道还要遍历一遍队列吗我们直接在定义头尾指针的结构体中加入 size 变量用 size 统计元素个数此时我们就需要更新我们上面的代码更新 pq-size //获取队列中有效元素个数 int QueueSize(Queue* pq) { //不能直接用尾指针 - 头指针 //两个指针并非顺序存储 assert(pq); return pq-size; }6、检测队列是否为空分析逻辑其实就是判断头指针或尾指针是否等于NULL//检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); //return pq-phead NULL; //在获取队列中有效元素个数中说明size return pq-size 0; }7、销毁队列分析逻辑按照顺序从头到尾遍历一遍按顺序销毁即可最终在执行完函数之后记得显式将结构体指针置为空因为传入的是一级结构体指针无法修改指针本身//销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur pq-phead; while (cur) { QNode* next cur-next; free(cur); cur next; } pq-phead pq-ptail NULL; pq-size 0; }三、测试代码1、测试入队 出队 判空2、测试获取队头元素3、测试获取队尾元素如有不足之处恳请指出