数据结构(四):队列 之 循环队列 与 链队列

2018-02-27 11:45:15来源:https://www.jianshu.com/p/4d10a8e41302作者:林塬人点击

分享


队列概念

队列是一种先进先出的结构,只允许在一端进行插入操作,在另一端进行删除操作,简称 FIFO ,允许插入的一端称为队尾,允许删除的一端称为队头
假设队列 q=(a1,a2….an),那么a1就是队头元素,an是队尾元素,删除操作总是从a1开始,从an插入



yjDvQ.md.png
队列的抽象数据类型
Data(数据元素):同线性表,元素具有相同的类型,相邻的元素具有前驱和后继关系
基本操作







































方法描述
initQueue(*Q)初始化操作,建立一个空队列Q
DestoryQueue(*Q)若队列Q存在,则销毁它
ClearQueue(*Q)将队列Q清空
QueueEmpty(Q)若队列Q为空,返回true,否则false
GetHead(Q,*e)若队列Q存在且非空,用 e 返回队列Q的队头元素
EnQueue(*Q,e)若队列Q存在,插入新元素 e 到队尾
DeQueue(Q,e)删除队列Q中的队头元素,返回其值
QueueLength(Q)返回队列Q的元素个数

队列顺序存储的不足
入队列操作是在队尾追加一个元素,不需要移动任何元素,时间复杂度为 O(1)



yj9zE.md.png

但顺序存储的队列元素出列时元素都要向前移动,时间复杂度为 O(n)



yjmqh.md.png

为解决队列出队时需要移动全部数据,我们可以不去限制队头一定在下标为 0 位置,引入两个指针
front 指向队头元素
rear 指向队尾元素下一个位置

当 front 等于 rear 时,队列为空队列,但会产生数组越界错误与空间浪费



yjX1S.md.png
循环队列定义
为了解决假溢出,可以把队列头尾相接,rear 可以指向下标为 0 的位置(当下标超过数组最大长度时,指向下标 0)



yjHBa.md.png

但可能会出现rear与front指针重合情况,无法判断队列是空还是满



yjBk2.png

解决办法:
设置一个flag,flag = 0 时队列为空,flag = 1 时队列满
保留一个元素空间,当队列满时,还有一个空闲单元




yjTsz.png
计算队满公式
由于 rear 可能比 front 大,也可能比 front 小,所以尽管只相差一个位置,但可能相差一整圈
若队列最大尺寸为 QueueSize,那么当队列满的条件是:(rear+1)% QueueSize == front(取模 % 的目的就是为了整合 rear 与 front 大小一样的问题)
例如 QueueSize = 5,front = 0,而 rear = 4,(4+1)% 5 = 0 此时队列满
例如 QueueSize = 5,front = 2,而 rear = 1,(1+1)% 5 = 2 此时队列满
例如 QueueSize = 5,front = 2,而 rear = 0,(0+1)% 5 = 1,1 ≠ 2 此时队列未满

计算队长公式
当 rear > front 时,此时队列的长度为 rear - front ,但当 rear < front 时,队列的长度分为两段,一段是 QueueSize - front,另一段是 0 + rear,队列长度为 rear - front + QueueSize,因此通用的计算队列长度的公式为:(rear-front+QueueSize)%QueueSize

队列的链式存储结构及实现
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它称为链队列
为方便操作,我们将队头指针指向链队列的头节点,而队尾指针指向终端结点



yprdd.md.png

空队列时,front 和 rear 都指向头结点



ypaoe.png
入队操作
入队操作其实就是在链表尾部插入结点



ypezY.md.png
出队操作
出队操作时,就是头节点的后继节点出队,将头结点的后继改为它后面的节点,若链表除头结点外只剩下一个元素时,需将 rear 指向头结点



ypExr.md.png
循环队列与链队列的比较
从时间上:它们基本操作都是常数时间 O(1),不过循环队列事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点存在一些时间开销,若出队入队频繁,有细微差异
从空间上:循环队列必须要有一个固定的长度,所以就有存储元素个数和空间浪费的问题,而链队列不存在这个问题,因此链队列更加灵活







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台