大家好
欢迎回来继续学习
C++语言程序设计
这一节我们来学习队列类
队列也是一种线性群体
那么这种数据结构呢
它也是一种受限制的线性结构
只能从一端插入数据
而从另一端删除数据
插入一数据的一端叫做队尾
删除数据的一端叫做队头
实际上就是跟我们
人去买东西
去银行办业务排队是一样的
就是跟着队走
它是一种先来先服务的结构
排列
也叫先进先出的结构
接下来我们来看一个
队列类的它的示意图
大家看
这是不是跟我们人排队很像
一边是队头 一边是对队尾
从队头出队
也就是取出数据 删除数据
从队尾入队
也就是说
把数据从队尾存进去
队列的基本状态呢
有是有队满 队空
和一般状态
现在我们来看看
这几种状态它们的示意图
队空状态呢
就是队里都还没有元素的时候
这个时候大把的空间
随便地用
可以入队
但是出队就不行了
因为没有人排到队里了
这是队空状态
它的队头 队尾
就指向了同样的位置
那么队满状态呢
就是它队列的空间
全部都占满了
这个时候呢
队头可以出队
但是从队尾就不能往里入队了
因为空间没有了
一般状态呢
就是队列中有元素
可以出队
也还有空间 也可以入队
我们想一想
我们人排队的时候是怎么排的呢
前面的人办完业务以后
后面的人跟着往前走 对吧
你总不能排队排在这儿不走吧
比如说一个房间很小
本来人很多
都挤满了
队都排到房子外面去了
大家假期买火车票的时候
经常遇到这样的情况 是吧
那这个时候
如果前面的人买完票
走了
但是紧挨着他们后面的人
不往前走
门口的人就不往里进
那我们老看着
这个门口都堵死了
人都满了 进不去了
但是里面呢
可能已经很松散了
买完票的人走了
没有及时跟进
这种情况
我们在排队的时候也见过
那我们得会催
前面赶紧往前走 赶紧往前走
后面这么多人进不去呢 对吧
在计算机中
我们在程序中
实现一个队列
也有这样的情况啊
当队头的元素出队以后
后面的元素要及时向前移动
出队一个元素移动一格
如果出队了
后面的元素不移动
会产生什么问题呢
就是假溢出
房子里面空着呢
但是后面的人以为进不去了
都堵在门外头
那如果我们在程序中
出现那样假溢出
就导致我们无法再往队列里面
添加元素了
其实呢
队列的空间空着
可是出队一个元素移动一下
出队一个元素移动一下
是不是也挺麻烦的
这是要开销的
也就是要花时间 空间开销
去移动这些元素
我们考虑到程序的效率呢
又希望能不能有元素出队了
我们不移动元素呢
也有这种办法
我们可以采用循环队列
把内存空间想象成一个弯曲的
队头 队尾连接起来
这样就可以不移动元素了
转着圈用这个内存空间
我们下面通过示意图来看一看
那么
我们看这个示意图呢
就是每当队尾
达到数组的最后一个元素的时候
就再回到数组开头去使用
那么这种弯曲成圆环状的
是模拟我们使用数组
来存放队列的情况
如果我们用链表来存放元素呢
当然就没有移动元素
这样一个问题了
大家回去可以试一试
自己写个程序
用链表来生成一个队列
是不是就没有这种假溢出
移动的问题了
那么用数组的话
我们在想象中把它弯曲出来
其实也很简单的
就是队尾和队头
都是各自往自己的行进方向去走
只要还有空间
就可以往里放
如果队头队尾到一块了
那么到底是队空了
还是队满了呢
这个时候最简单的办法
我们可以用计数的方式
看看可以有多少个元素了
元素个数达到上限了
就说明是队满了
如果元素个数是0
就说明是队空了
那也有的算法实现的时候呢
去区分到底是队头
从后面追上了队尾
还是队尾从后面追上了队头
那么这样也可以来区分
所以大家去
实现这个队列的时候呢
可以自己选一种觉得合适的算法
接下来的这个例题
就实现了一个队列类模板的代码
我们一起来看一下
这是一个简单的队列类模板程序
说它是个简单程序
因为简化了很多环节
功能也非常有限
包括数据合法性检查
是不是满
是不是空的判断呢
这些都是一种简化的方式
只是为了给大家看一看
这个队列的实现的原理
作为一个示例
看这个类模板呢
它也是有类型参数
还有这个常量SIZE
SIZE是作为这个队列的容量
然后它的数据有头指针
尾指针
以及元素个数
元素个数呢
指的是队列之中
它实际的元素个数
而SIZE呢
指的是它的总的容量
那么函数呢包括构造函数
新元素入队的函数
元素出队的函数
以及清空队列
还有读取
有就是访问队首元素
但是读取了以后呢
并不删除它
这个求队列长度
判断队是否空
判断队是否满
好 我们来看函数的实现
构造函数很简单
做一下初始化
然后新元素入队呢
看到是插在队尾
这时候还要判断205za00:06:58,040 --> 00:06:59,200队是不是满了
队不满的情况下
元素个数加1
然后向队尾插入一个元素
这个时候呢队尾
它的指针
它的下标要加1
加1以后还要除以SIZE取余
说明这个模板
实现的是一个循环队列
然后再看出队
那判断队是否空
不空的情况下呢
记录下现在的队首元素的下标
简称队首指针
那它并不是一个
真正的指针类型的指针
又指向它的位置
实际上是队首元素的下标
然后总的元素个数减1
然后将队首元素的下标加1以后
也是要除以SIZE取余
实现循环队列
最后用暂存的这个temp作下标
返回以前旧的那个队首
位置那个元素
这就是一个元素出队了
那么getFront是访问
是访问
也就是读取队首元素
直接返回队首元素就行了
它并不删除它
这个getLength函数呢
是返回队列的元素个数
直接return count就可以了
这个isEmpty判断队列是否空
count是否等于0
isFull判断count是否等于SIZE
它是否满
然后clear就是把所有的状态
恢复到初始状态
就是清空了队列
这就是一个简单的
队列类模板的代码