循环、双向、链式、数组一文搞懂队列 _队列

前言栈和队列是一对好兄弟，前面我们介绍过一篇栈的文章(栈，不就后进先出)，栈的机制相对简单，后入先出，就像进入一个狭小的山洞，山洞只有一个出入口，只能后进先出(在外面的先出去，堵在里面先进去的就有点倒霉) 。而队列就好比是一个隧道，后面的人跟着前面走，前面人先出去(先入先出) 。日常的排队就是队列运转形式的一个描述！
栈是一种喜新厌旧的数据结构，来了新的就会处理新的把老的先停滞在这(我们找人、约人办事最讨厌这种人)，队列就是大公无私的一种数据结构，排队先来先得，讲究顺序性，所以这种数据结构在程序设计、中间件等都非常广泛的应用，例如消息队列、FIFO磁盘调度、二叉树层序遍历、BFS宽度优先搜索等等。
队列的核心理念就是：先进先出！
队列的概念：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
同时，阅读本篇文章最好先弄懂顺序表的基本操作和栈的数据结构！学习效果更佳！

文章插图

队列介绍我们设计队列时候可以选择一个标准，这里就拿力扣622设计循环队列作为队列设计的标准。
队头front：删除数据的一端。
队尾rear：插入数据的一端。
对于数组，从数组后面插入更容易，数组前面插入较困难，所以一般用数组实现的队列队头在数组前面，队尾在数组后面；而对于链表，插入删除在两头分别进行那么头部(前面)删除尾部插入最方便的选择。

文章插图

实现方法：

MyCircularQueue(k): 构造器，设置队列长度为 k。
Front: 从队首获取元素。如果队列为空，返回 -1。
Rear: 获取队尾元素。如果队列为空，返回 -1。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

普通队列按照上述的介绍，我们很容易知道数组实现的方式。用数组模拟表示队列。要考虑初始化，插入，问题。

文章插图

在这个普通队列一些操作需要注意的有：
初始化：数组的front和rear都指向0. (front和rear下标相等的时候说明队列为空)
入队：队不满，数组不越界，先队尾位置传值，再队尾下标+1(队尾rear实际上超前一位，为了区分空队列情况)
出队：队不空，先取队头位置元素，在队头+1 。
但是很容易发现问题，每个空间域只能利用一次，造成空间极度浪费，非常容易越界！

文章插图

循环队列(数组实现)

针对上述的问题。有个较好的解决方法！就是对已经申请的(数组)内存重复利用。这就是我们所说的循环队列。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

数组实现的循环队列就是在逻辑上作修改。因为我们队列中只需要front和rear两个指针。rear在逻辑上在后面，front在逻辑上是在前面的，但实际上它们不一定谁在前谁在后，在计算距离的时候需要给rear先补上数组长度减去front，然后求余即可。

文章插图

初始化：数组的front和rear都指向0. 这里需要注意的是：front和rear位于同一个位置时候，证明队列里面是空的。还有在这里我具体实现时候将数组申请大了一个位置空出来，防止队列满的情况又造成front和rear在同一个位置。
入队：队不满，先队尾位置传值，再rear=(rear + 1) % maxsize;
出队：队不空，先取队头位置元素，front=(front + 1)% maxsize;
这里出队入队指标相加如果遇到最后需要转到头位置，这里直接+1求余找到位置(相比判断是否在最后更加简洁)，其中maxsize是数组实际大小。