电子工程师技术服务社区
公告
登录
|
注册
首页
技术问答
厂商活动
正点原子
板卡试用
资源库
下载
文章
社区首页
文章
真香!20张图揭开「队列」的迷雾,一目了然
分 享
扫描二维码分享
真香!20张图揭开「队列」的迷雾,一目了然
数据结构
李肖遥
关注
发布时间: 2020-09-16
丨
阅读: 669
## 队列的概念 首先我们联想一下链表,在单链表中,我们只能对他的链表表尾进行插入,对链表的表头进行结点的删除,这样强限制性的链表,就是我们所说的队列。 也就是说,队列(queue)是限定在表的一端进行插入,表的另一端进行删除的数据结构。 如下图所示,假如你去买票排队,每一列队伍都有一个队尾和对头,先来的先买票,后来的后买,买好的就从对头出去,新来买票的就需要从队尾继续排队。 ![](https://cf04.ickimg.com/bbsimages/202008/343be69be4f5ebe9cfb763cb16a34f77.png) 通常,称进数据的一端为 **队尾**,出数据的一端为 **队头**,数据元素进队列的过程称为 **入队**,出队列的过程称为 **出队**。 ### 我们可以总结如下 队列是一个线性的数据结构,并且这个数据结构只允许在一端进行插入,另一端进行删除,禁止直接访问除这两端以外的一切数据,且队列是一个先进先出的数据结构。 ![](https://cf04.ickimg.com/bbsimages/202008/80588252720a87ce38b7a6cabda7d2fc.png) 如上图,队列就像一个两端相通的水管,只允许一端插入,另一端取出,取出的球就不在水管里面了,而先放入管中的球就会先从管中拿出。 ### 队列存储结构的实现有以下两种方式 - 顺序队列:在顺序表的基础上实现的队列结构 - 链队列:在链表的基础上实现的队列结构 两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。 ## 队列的结点设计与初始化 队列只有链式的设计方法,其本身分为多种队列,如**顺序队列**和**循环队列**,还有衍生的**优先队列**等等,我们以顺序队列的设计为例。 首先是队列的结点设计,我们可以设计出两个结构体,一个结构体Node表示结点,其中包含有一个data域和next指针,如图所示: ![](https://cf04.ickimg.com/bbsimages/202008/aea67765c7113398ed473013ea897334.png) 其中data表示数据,其可以是简单的类型,也可以是复杂的结构体。 next指针表示,下一个的指针,其指向下一个结点,通过next指针将各个结点链接。 然后我们再添加一个结构体,其包括了两个分别**永远指向队列的队尾和队头的指针**,看到这里是不是觉得和栈很像? 我们主要的操作只对这两个指针进行操作,如图所示: ![](https://cf04.ickimg.com/bbsimages/202008/9213d8f9615a25771b0b73072f6a0e41.png) 其结构体设计的代码可以表示为: ``` //结点定义 typedef struct node{ int data; struct node *next; }node; //队列定义,队首指针和队尾指针 typedef struct queue{ node *front; //头指针 node *rear; //尾指针 }queue; ``` 对于初始化需要初始化两个类型,一个是初始化结点,一个是初始化队列。 我们看到代码中的描述,初始化队列有些不同,当初始化队列的时候,需要将**头尾两个结点指向的内容**统统置为空,表示是一个空队列,两个创建的函数代码可以表示为: ``` //初始化结点 node *init_node(){ node *n=(node*)malloc(sizeof(node)); if(n==NULL){ //建立失败,退出 exit(0); } return n; } ``` ``` //初始化队列 queue *init_queue(){ queue *q=(queue*)malloc(sizeof(queue)); if(q==NULL){ //建立失败,退出 exit(0); } //头尾结点均赋值NULL q->front=NULL; q->rear=NULL; return q; } ``` ## 判断队列是否为空 这是一个既简单也很要紧的操作,判断队列是否为空直接就是判断**队列头指针是否是空值**即可,判断队列是否为空是比较常用的操作,切勿忘记。 其代码可以表示为: ``` //队列判空 int empty(queue *q){ if(q->front==NULL){ return 1; //1--表示真,说明队列非空 }else{ return 0; //0--表示假,说明队列为空 } } ``` 或者直接利用返回值进行更简单的判断也可以,代码如下: ``` int empty(queue *q){ return q->front==NULL; } ``` ## 入队操作 入队操作变化如下图: ![](https://cf04.ickimg.com/bbsimages/202008/da73cac81f7404156f5965b05af2e14d.png) 进行入队(push)操作的时候,同样的,我们首先需要特判队列是否为空,如果队列为空的话,需要将**头指针和尾指针**一同指向**第一个结点**,代码如下 ``` front=n; rear=n; ``` 如图所示: ![唯一结点n](https://cf04.ickimg.com/bbsimages/202008/7f484f2fdf3254920e43ed1420230215.png) 当如果队列不为空的时候,这时我们只需要将尾结点向后移动,通过不断移动`next`指针指向新的结点构成队列即可。如图所示: ![](https://cf04.ickimg.com/bbsimages/202008/78960aa6a55dc8e5beff9fb0c93dd271.png) 其代码可以表示为: ``` //入队操作 void push(queue *q,int data){ node *n =init_node(); n->data=data; n->next=NULL; //采用尾插入法 //if(q->rear==NULL){ //使用此方法也可以 if(empty(q)){ q->front=n; q->rear=n; }else{ q->rear->next=n; //n成为当前尾结点的下一结点 q->rear=n; //让尾指针指向n } } ``` ## 出队操作 出队操作变化如下图: ![](https://cf04.ickimg.com/bbsimages/202008/3d362b822a422f47a50e9fb4b9ac8582.png) 出队(pop)操作,是指在队列不为空的情况下进行的一个判断,当然我们在此也一定要进行队列判空的操作,你懂的。 如图,如果队列只有一个元素了,也就是说**头尾指针**均指向了**同一个结点**,那么我们直接将头尾两指针制空`NULL`,并释放这一个结点即可,如下图所示: ![](https://cf04.ickimg.com/bbsimages/202008/706d813356920d6cc2383885acbea35c.png) 当队列含有以上个元素时,我们需要将**队列的头指针**指向**头指针当前指向的下一个元素**,并释放掉当前元素即可,如下图所示 ![](https://cf04.ickimg.com/bbsimages/202008/b946902c67c739241ab53835a5c1313c.png) 其代码可以表示为: ``` //出队操作 void pop(queue *q){ node *n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } if(q->front==q->rear){ q->front=NULL; //只有一个元素时直接将两端指向置为空即可 q->rear=NULL; free(n); //记得归还内存空间 }else{ q->front=q->front->next; free(n); } } ``` ## 打印队列元素(遍历) 打印队列的全部元素可以帮助我们调试,看到队列中具体的数据,在队列不为空的情况下,通过结点的`next`指向依次遍历并输出元素既可。 其代码可以表示为 ``` //打印队列元素 void print_queue(queue *q){ node *n = init_node(); n=q->front; if(empty(q)){ return ; //此时队列为空,直接返回函数结束 } while (n!=NULL){ printf("%d\t",n->data); n=n->next; } printf("\n"); //记得换行 } ``` 遍历操作还有很多别的表示方法,比如说进行计算队列中含有多少元素,代码如下: ``` int calac(queue *q){ node *n = init_node(); n=q->front; int cnt=0; //计数器设计 if(empty(q)){ return 0; //此时队列为空,直接返回函数结束 } while (n!=NULL) { n=n->next; cnt++; } return cnt; } ``` ## 顺序队列的假溢出 什么是假溢出?我们可能会有疑问,溢出还有假的! 这里我们也需要考虑到顺序队列有什么缺点,对于顺序队列而言,其存在已经足够解决大多时候的设计问题了,但是其依旧存在一些缺陷和不足。 从上面的解析中我们看到,入队和出队操作均是直接在其后面进行结点的链接和删除,这种操作会造成其使用空间不断向出队的那一边偏移,产生假溢出。 我们来打打一个比方,先看看下面的图: ![示例顺序队列](https://cf04.ickimg.com/bbsimages/202008/5a8dae6058eecba47be813d010debad8.png) 上图所示,有一个顺序队列,这个队列的大小为5,其已经包含了四个元素`data1,data2,data3,data4`。 接着,我们对这个队列进行出队操作,出队2个元素,队列就变成了这个样子,如下图所示: ![](https://cf04.ickimg.com/bbsimages/202008/667991042554ffce13fdeaf9504dda8e.png) 从图上看到似乎没有什么问题,但是当我们接着再进行入队操作,比如我们入队2个元素,分别是`data5`和`data6`。 此时我们已经发现问题了,尾指针移动到我们可以进行队列操作的范围之外去了,有没有发现? 这种现象我们称呼作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为**假溢出**。如下图所示: ![出队产生假溢出](https://cf04.ickimg.com/bbsimages/202008/6428a17876dd39ae776557e8eefc7680.png) 那么我们有什么办法解决这个问题呢?这就要涉及到循环队列的性质了! ## 循环队列的概念 可能这个时候会产生一个疑问,我们学习的队列不是使用链表实现的动态队列么? **没有空间的时候会开辟空间,这难道还会产生假溢出么?** 的确,当进行动态创建队列的时候,也只不过是向后继续不断的申请内存空间; 即使前面出队操作释放掉了前面的空间,但是指针依旧会**向后进行移动**,直到达到系统**预留给程序的内存上界**被强行终止; 这对于极为频繁的队列操作和程序而言是致命的,这时候,就需要对我们的队列进行优化,使用更为优秀的结构——**循环队列**。 循环队列就是将队列存储空间的最后一个位置转而绕到第一个位置,**形成逻辑上的环状空间**,以此来供队列循环使用,如下图。 ![](https://cf04.ickimg.com/bbsimages/202008/642b6dc220d422ad9f6e87421b8a5ed1.png) 循环队列就是给定我们队列的大小范围,在原有队列的基础上,只要队列的后方满了,就从这个队列的前面开始进行插入,以达到重复利用空间的效果; 由于循环队列的设计思维更像一个环,因此常使用一个环图来表示,但我们需要注意,实际上循环队列不是一个真正的环,它依旧是单线性的。 ## 循环队列的结构设计 由于循环对列给定了数据范围的大小,所以不需要使用链式的动态创建方法了。 因为如果使用链式存储,会无法确定何时再回到队头进行插入操作,所以我们采用**模拟的方法**,如图所示: ![](https://cf04.ickimg.com/bbsimages/202008/fd35eb6d98d216dec23a6cfab790bd2c.png) 其中,data表示一个数据域,int为类型,其可以修改为任意自定义的类型,比如说简单的char,float类型等等,也可以是复杂的结构体类型。 - `maxsize`表示循环队列的最大容纳量,其表示队列的全部可操作空间。 - `rear`代表尾指针,入队时移动。 - `front`代表头指针,出队时移动。 其代码可以表示为: ``` #define maxsize 10 //表示循环队列的最大容量 //循环队列的结构设计 typedef struct cir_queue{ int data[maxsize]; int rear; int front; }cir_queue; ``` ## 循环队列的初始化 循环队列的初始化核心就在于申请空间,并且将front指针和rear指针内容赋值为0,即指向第0个元素即可,这里要注意第 0个元素内容为空,如下图所示: ![](https://cf04.ickimg.com/bbsimages/202008/a04e382ef1702a6fd30f56dc9a3e0727.png) 其代码可以表示为: ``` //初始化 cir_queue *init(){ cir_queue *q = (cir_queue*)malloc(sizeof(cir_queue)); if(q==NULL){ exit(0); //申请内存失败,退出程序 } q->front=0; q->rear=0; return q; } ``` ## 入队操作 入队操作同顺序队列的方法,直接将rear向后移动即可。 但是要注意判断,如果rear达到了队列的空间上线,将要从头继续开始移动。 这里推荐使用余数法,即无论如何求余都是在这片空间内进行操作,防止一次错误执行就直接整体崩溃,而且也相对而言更为简洁,不推荐使用if语句,这样显得比较累赘。 ![入队操作](https://cf04.ickimg.com/bbsimages/202008/2b5150a808feea41114e79ec0a0a4b3e.png) 注意进行加一移动位置操作的时候,不能直接`q->rear++`这样的操作,这样计算机判断优先级会产生让自己意想不到的后果。 此外这里还需要进行一次是否队列已满的判断,当我们rear指针的下一个位置就是front的位置的时候,即改循环队列已满。 如图: ![队列已满](https://cf04.ickimg.com/bbsimages/202008/a37f0648626490b2d8d4a140577d5761.png) 其代码可以表示为: ``` //入队操作push void push(cir_queue *q,int data){ if((q->rear+1)%maxsize==q->front){ printf("溢出,无法入队\n"); return; }else{ q->rear=(q->rear+1)%maxsize; q->data[q->rear]=data; } } ``` ## 出队操作 如果顺序队列的出队操作,直接将front进行后移一位即可。 这里上面很多地方都提过了,有一个需要留意的地方,即队列是否为空,当队列为空的时候是无法进行出队操作的。 ![出队操作](https://cf04.ickimg.com/bbsimages/202008/294757bfa5f9ca118bbb8bdc4b11640a.png) 其代码可以表示为: ``` //出队操作pop void pop(cir_queue *q){ if(q->rear==q->front){ printf("队列为空,无法出队\n"); return; }else{ q->data[q->front]=0; q->front=(q->front+1)%maxsize; } } ``` ## 遍历操作 遍历操作需要借助一个临时变量储存位置front的位置信息,利用i逐步向后移动,直到i到达了rear的位置即可宣告遍历的结束。 ``` //遍历队列 void print(cir_queue *q){ int i=q->front; while(i!=q->rear){ i=(i+1)%maxsize; printf("%d\t",q->data[i]); } printf("\n"); //记得换行 } ``` ## 关于队列的总结 请牢记这句话:队列是一个先进先出的数据结构。 今天队列基础就讲到这里,下一期,我们再见! 原文:https://mp.weixin.qq.com/s/GYQrxBOasKpvF4uZsMdOSw
原创作品,未经权利人授权禁止转载。详情见
转载须知
。
举报文章
点赞
(
0
)
李肖遥
关注
评论
(0)
登录后可评论,请
登录
或
注册
相关文章推荐
MK-米客方德推出工业级存储卡
Beetle ESP32 C3 蓝牙数据收发
Beetle ESP32 C3 wifi联网获取实时天气信息
开箱测评Beetle ESP32-C3 (RISC-V芯片)模块
正点原子数控电源DP100测评
DP100试用评测-----开箱+初体验
Beetle ESP32 C3环境搭建
【花雕体验】16 使用Beetle ESP32 C3控制8X32位WS2812硬屏之二
X
你的打赏是对原创作者最大的认可
请选择打赏IC币的数量,一经提交无法退回 !
100IC币
500IC币
1000IC币
自定义
IC币
确定
X
提交成功 ! 谢谢您的支持
返回
我要举报该内容理由
×
广告及垃圾信息
抄袭或未经授权
其它举报理由
请输入您举报的理由(50字以内)
取消
提交