开发者学堂课程【Go 语言核心编程 - 数据结构和算法: 数据结构和算法-数组模拟环形队列】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/627/detail/9833
数据结构和算法-数组模拟环形队列
思路分析
(1)大体思路
之前实现的队列结构,它有一个缺陷,就是没有有效的利用数组空间,它用一次就完了,就好比是一次性的队列,这肯定是不合理的,那怎么办?
那么现在,就要使用数组来实现一个环形的队列,先做它的一个思考分析。大体是这样的一个思路:在前面的数组模拟队列进行优化,在其上面进行优化,充分利用数组,因此,将数组看成是一个环形的。
(2)怎么形成此环境
那么怎么来形成此环境?
它关键点是在于要取模,因为到最后再往下面走,加一它就回去吗?打个比方,
如下图:
怎么让 rear 这个尾部能够到前面去?
举个例子, rear 目前是等于4,那怎么能够让它的下标又重新回到1?最简单的方式就是让 rear加上一个1,再模上它的最大值,即就是 maxSize ,如上图所示就变成零了,这样就有效的让它又回到了前面去了,这样的一个思路就分析出来了。所以说这个地方的关键点就是可以通过像刚才一个取模的方式来实现。
(3)怎么判断环形列表
那这边又有一个问题,就是怎么去判断环形列表,即环状的数组,其实这地方有一个约定,就是用数组来模拟一个环形列表,尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,在判断队列满的时候需要注意 (tail +1 )% maxSize == head 满,这点不是特别容易分析出来的。
(4)“空”的含义及使用
它要空一格,如果一格都不空的话,会很难实现。讲述一下这是什么含义,以上图为例,假如箭头指向首先在1的位置,然后往前移动一步又一步,移到4的位置时,如果要继续往前走,那么就先要去探测一下还能不能往后走,因为要留一个空间,比如它原先初始化的时候, rear 它在初始化时在0的位置, tail在4的位置,如果在 tail 最后尾部再加一个,发现已经相等了,那就不能再往里加东西了,再加也是加不进去的,所以在这地方有一个约定,就是要去给 tail 加一,再模上 maxSize 的时候,要去看它到底还能否往里加,所以要留一个容量,做出一个空,即留出一个容量做一个约定。那么什么时候为空?什么是为空?
就是它的尾部和头部相等的时候,认为它是空,跟原先一样的道理,就是不停的追,追到最后追到相同了。
(5)总体思路分析
总结出来有几个比较重要的地方:第一点就是它的满度是什么时候表示满?
即什么时候表示这个队列满了?那么它的条件,就是刚才说的尾部加一,加起来过后再模上一个 maxSize ,模上它的最大值;第二点是什么时候为空?
就是 tail 等于 head 的时候就表示空,就它们两个下标相等就表示空;第三点是刚开始时 tail 和 head 等于多少,刚开始初始化的时候, tail 和 head 都等于零,那等于零的情况下,就相当于直接指到了这个数组的最前面,这个跟刚才有点区别,就是在上图中时箭头是指向最前面的,第三点中还有一点就是不知道它到底有多少个数据,是怎么计算出来的、怎么统计该数组一共有多少个元素?该队列有多少个元素?
那么到时候是这样算的:就是(tail + maxSize - head)”% maxSize,那么为什么这样算?
从理论上来说,尾部总是应该比头部要大,但是因为这个队列,它在最后反过来跑到后面去,所以在统计的时候,把它最大值加上,再减掉它,再模上。举个例子,
如下图:
箭头不停的走,它原先 front 初始化为零,然后加了一个元素走,我加一,加了过后,往后面走一下,看共有多少元素,它头部现在还没有数据,就头部的内容是相当于是还没取,按照上述公式算的话,它就是这样子的,尾部现在变成了一, maxSize 假设为5,,头部为零,那就是(5+1-0)%5=1,刚好等于1 。