队列
概述
队列(queue)可以认为是一种特殊的线性表,因为他仍然满足线性表的特点:
- 存在一个唯一的没有前驱的(头)数据元素.(注意与具体实现中的"头结点"有别)
- 存在一个唯一的没有后继的(尾)数据元素.
- 除此之外,其他每一个数据元素均有一个直接前驱和一个直接后继数据元素.
如前所述,链表和顺序表可以在表中的任何位置操作数据;栈只能在栈顶操作数据.
队列的操作则是:只允许在表的头部和尾部操作数据,并且表(队)头只能弹出元素(出队),表(队)尾只能插入元素(入队).当然,可以获取队头的元素值.
数据结构上的队列和日常生活中的排队是一致的,要遵循"先来后到"的原则,也就是满足了所谓的FIFO原则.
另外,和现实生活不同,队列中的元素(不是队头)一般是不允许进行插入(现实生活当然也不能插队doge)和删除(现实生活可以取消排队自行离开)的.因为我们只能操作队头和队尾.
队列的实现
基于数组(顺序表)
假设我们的队列有如下信息:----属性
- front指针: 指示队头位置
- tail/rear指针: 指示队尾
- size值: 队列当前的元素个数
- max_size值: 队列的最大容量—
循环队列需要—使用数组(realloc),而链栈(一般)则不需要
其中,tail不指向任何有效元素,我们稍后将会讲解为何需要这样做!
队列的状态
有如下3种状态:
队列空
由于tail不指向任何有效元素,front永远指向队头元素(除非队空),那么显然可以(和栈类似)指定:
队列为空,等价于front==tail
队列非空
与队列空互斥,则有:
队列非空,等价于front!=tail
队列满
仅适用于数组实现(循环)队列,由于数组有长度上限,因此队列会满!
队列满,等价于size==max_size (初步考虑)
关于max_size如何定义需要另外讨论.
指针的指向问题
我们使用front指针来指向队头元素;用tail指向队尾元素的下一个空间.
这样设计tail指针的指向,是为了避免假溢出问题,同时解决判断队列状态的歧义问题.
假溢出问题
由于数组的长度固定,如果简单地在末尾插入,在头部删除,整个队列就会在数组中逐渐向后"平移",前面的元素空间都会被浪费掉,直到到达数组末尾,导致无法插入元素,即发生了溢出,但是此时前面的很多元素空间很可能都是空的!
假溢出的情况发生图:
这种溢出叫做假溢出,即队列无法插入任何元素,但是实际上仍然有空间可用!
为了解决这个问题,我们需要想办法让队列在到达数组末尾时,新入队的元素能够存储到数组开头被出队的空间中,从整个数组来看,就像是一个圆圈,这样的实现称为循环队列.循环队列是从存储实现方式上看的,但是从队列ADT的角度来看,整个队列仍然只能从队头出队,从队尾入队.
循环队列的入队逻辑图如下:
你可能有点懵,那么不妨把数组当成一条"蛇",把他拧成一个圆圈再看看呢?
也就是说,通过某种手段,让tail在递增时,如果发生越界,则让他回到0的位置,继续递增.
队列的状态判定
队空和队列有一个元素
前面说了,该实现中,用tail指向队尾元素的下一个空间,这是为了防止状态判断发生歧义.
想一下,如果我们让tail指向队尾元素:
假设有2个队列a,b.其中a有1个元素,b为空,那么队列的图示如下:
显然这2种状态如果使用指针来判断是否为空就会发生歧义->不好
当然也有解决方案—我们直接用size和max_size来判断是否为空即可.
不过设计程序的一个原则就是:尽可能避免各种潜在的歧义.
从这个角度去考虑,这里选择将tail的指针后移,这样就能区分出2种状态了:
队满的判定
同样,既然选择"用tail指向队尾元素的下一个空间",那么避免"队空"和"队满"的歧义,我们需要人为地"浪费"一个空间,即front指针的前一个位置.
假设有2个队列a,b.其中a为空,b为满:
这是不浪费的情况:
这是人为浪费一个空间的情况:
显然后者无歧义.
至于"让tail指向队尾元素"的实现,也是可以的,这里使用"让tail指向队尾元素的下一个空间"的实现.
队列的操作
入队-push
先判断队列是否已满.
由于tail指向当前队尾元素的下一个位置,所以直接复制元素进去,然后将tail递增即可,注意考虑回绕.
注意size++.
出队-pop
先判断队列是否为空.
(可能)需要将队首元素值备份并返回,然后直接将front递增即可,注意同样要考虑回绕.
注意size--.
销毁队列-destory
(可能)将存储表的数组free掉.
然后将队列的实例销毁.
获取状态信息
这些方法都只需要返回对应的状态信息即可,例如队列当前的元素个数get_size(),当前队头元素值get_front().
wechat
alipay