开发者学堂课程【Go 语言核心编程 - 数据结构和算法： 数据结构和算法-数组模拟队列分析】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9831
数据结构和算法-数组模拟队列分析
内容简介：
一、队列(queue)
二、数组模拟队列分析
一、队列(queue)
(1）前言
前面讲了稀疏数组的一个用法，现在来看另外一种比较常见的数据结构，也是在前面经常用到的一种数据结构，叫队列。
队列是一种经常使用到的一种数据结构，因为在现实生活中，包括在编程过程中，都会存在一种队列，就是以队列的方式来对数据进行一个处理。
(2）队列的一个使用场景
比如排队，如下图：
经常会有一个排队，比如进来有一个人在排队，先进的排在前面，做一个叫号系统，先来的人应该先被服务，后来的人后被服务，别整反了，整反了就先来的人一直等着，没人管他，后来的全部往上怼，那这个系统就出问题了，这个排队的案例就是这样的，非常经典，这是队列的一个使用场景。
那么想一想，在编程中还有哪些会用到队列这种形式的，比如大家都知道，就是留言版，留言一般是谁先留言总是排在前面是，是排序了，还有很多其他的用法了。
(3）队列介绍
那队列有这些用法的话，这个队列到底是什么？
首先，队列它是一个有序列表，注意这里说的有序，并不是说它一定是按照从大到小或从小到大的，那个叫排序，所以有序指的是它的数据是按照一定顺序来排的，就是先进去的排在前面，后进去排在后边，这个称之为有序列表，它可以用数组来实现，同样也可以用链表来实现。
准确的讲，链表实现相对简单，数组实现其实相对麻烦，尤其是对环行数组来实现队列还是比较麻烦的，这个理解起来有一定难度，那么队列还有一个最重要的特点，即它是先入先出的原则，即先存入队列的数据要先取出来，后存储的数据要后取出来。
(4）队列介绍示意图
画了一个示意图，帮助理解，如下:
就以数组的这种方式来给大家看一下队列，假设这里有一个数组，将其横着放为了看起来更清楚一点，比如这个数组，它是有一些数据在里边，假设它一共可以存放五个元素，当存放数据的时候(假设小圆圈是一个数据)，数组本身它应该也是一个有顺序的，可以放到第一个空格的位置，
比如说这是它的第零个元素，放入第二个空格的是它第一个元素，放入第三个空格的是它第二个元素，以此类推这是它第三个元素、这是它第四个元素，那么在放数据时，它应该这样存放:
首先，在它的第一个位置存，这个相当于是它的队列的队首，它第一个在最前面，然后在它的后面放，如果我又存放了一个数据结构，后面再存放一个数据，又在这个后面存放，以此类推，就这样不停地存放，那么取的时候应该怎么取？
取的时候是从前面取。请思考一个问题:原先数组里面有三个元素，当取走一个元素时，那么其实这个数组的队列的队首就变成它了，即队列的第一个，那么这种形式下有一个问题，假设这个地方再取走一个队手，这时又往里面加数据，应该在哪加？
它其实是在最后面加，那么队尾是在哪里？就是它最后的元素队尾。这时有一个问题就是，当它都存完了之后，如果再放一个数据，应该放哪？怎么处理？
在某种情况下，数组来模拟一个队列，这个数组就没法用了，那么如果用数组来模拟这个队列，存在一个最大的问题，就是怎么有效的利用前面的空间，当然有同学曾经这样说过，他说老师你看，不停地往后面推就可以了，但是推到后面确实没法放了，但是前面还有空间，可能会想那把它放到前面就可以了呀，但是放到前面就涉及到好多东西在里面，因为要到后面去找前面这种算法了，怎么能够在这边的时候还找到前面，这是一种思路。
这肯定要涉及算法，那么有些动作是不能这样简单一点的，要把放的每一个元素精确好，现在假设有一个人取走一个元素，赶紧把前面挪一下，后面还有空间，如果这么做，这个效率极为低下。
假设这个队列里很大，整体往前移下去试试看，那这个就彻底的完了，不如不用数据结构，因为将来数字很大，假设有1000个数字移动一个，如果把整体99往前移动，速度会很慢，所以这样肯定是不行的，那么有一个问题就是怎么去有效利用空间，比如说到地方了，假设有三个数据，然后这个地方前面还有两个空，要怎么用?
这个叫环形，用数组来模拟一个环形队列，相当于说用数组来实现队列有两种形式，第一种比较简单，但是它不能有效的利用数据；第二种方式是比较烧脑的，是不容易很好理解的，这个东西相对来说有一点麻烦。
二、数组模拟队列
(1）模拟分析
看这个案例，即用数组来模拟队列，先说第一种就是，而不是环形的，那怎么来实现？
首先这里有几个思路要说清楚，第一个是队列本身是有序数列，若使用数组的结构来存储队列的数据，则队列数组的声明应该如下，应该有一个 maxSize ，就是表明队列最大的容量是多少，不管怎么样，这个队列假设最多只能存放五个数据进去，不能存六个。
即使是用环形来做，它也是一个大小的，就像在某个区域排队排到一定程度的时候，就关门，即不让进去了，容量满了；
第二个，因为队列的输入、输出是分别从前后端来处理的，因此至少需要两个变量来表示它的队尾和队首，即第一个和最后一个，那么这里用的是 front 和 rear ， front 就是前端， rear 就是尾部，用这两个人分别记录队列的前后端的两个下标，那么 front 就是队首，队首会随着数据的输出而改变，做完一个取出来一个， front 就会往后面移动，那么是随着数据的输入而改变，那么当加入一个数据的时候，real 就应该往后面挪，它其实一个是输出，一个是输入，那看一下以下这个图:
可以看到一个基本的思想，关于用数组来模拟队列，思想基本上都是这个思想，但是具体实现还是略有差别，比如以前在大学学这个数据结构的时候，它是这么一种方式实现，等到参加工作后，发现它是另一种事情，但整体思想是差不多的。
首先上图最左边的是一个数组，这个数组大小是 maxSize ，因为下标肯定不能到最大的值，那么这个就代表一个 Q ，那么它这里面的 Front 和 rear ，初始化为负一，当往里面放一个数据，这个地方扔数据的时候，整个这个 front 是没有移动的，谁在不停的移动？
这个 rear 一定要非常清楚的知道，rear 是在随着数据的添加而往后移动，而且注意一个重要特点，在这个思想里面， rear 其实就是指向队列的最后，而且包含它真正地指向了对面，最后就的确使用最后一个数据；
注意观察 front ，这个 front 它初始化为负一，其实它在里面有的时候是没有动过的，所以 front 它其实相当于是指向队列的前面，而且并没有包含第一个元素，这一点如果没有搞清楚的话，看代码可能就看不懂了，一写就容易蒙圈。
(2）应用案例
有了这个东西过后，来看一下具体的实现，来把数组模拟对立的思想先说清楚，一个是它是一个有序的数组，它的变化是由这两个数据来体现的，一个是对首，一个是对尾。
当我们将数据存入队列时称为”addqueue”， addqueue 的处理需要两个步骤:第一个是尾指针往后移， Front 等于 rear 的时候，认为它是空；第二个若尾指针rear 小于等于队列的最大下标 MaxSize-1 ，则该数组存入的这个位置满了，那么减一的时候就认为队列满了。
也就是说目前这个数组模拟队列，其实它是一个飞环形状的，用完就没有了，最多就搞五个，然后没有了，这个方法比较简单，相对比较好理解，但是它肯定不灵活。
(3）思路分析
来先完成一个飞环形的一个队列，同样是用数组来实现的，接着讲一下思路分析，如下图:
