栈和队列---循环队列

1.循环队列的出现

（1）上面的这个就是一个普通的数据的入队和出队的过程我们正常情况下去实现这个入队和出队的过程，就是这个数据从这个队尾进入，从队头离开，但是这个加入的时候肯定是没有其他的问题的，直接在这个队尾插入数据就可以了，但是在队头把这个数据出队之后，我们想要保持这个队列的完整性，就需要使用循环把这个队列里面的数据向前进行移动，这个是增加了这个方法的时间复杂度；

（2）我们新的方法就是定义两个指针，一个指针就是rear指针，指向这个队列的尾部，一个指针就是front指针，指向这个队列的头部，我们在进行这个数据的入队的时候，我们先让这个rear+1,然后把这个入队的数据放到这个指针指向的位置；

（3）在队头出队的时候，我们只需要把这个front的指针先向后移动，再把这个指针指向位置的元素给删除掉，实际上这个指针向后移动之后，两个指针之间的位置才属于我们的这个队列的范围，我们这个数据也不能称之为删除，而是这个数据不在我们的这个队列里面了，相当于这个数据被“删除了”而已；

（4）但是这个还会出现一个问题，对于一个队列而言，我们在前面删除数据，前面就是空的了，这个时候我们的rear如果不短的入数据，这个指针最后就会指向这个队列的队尾，我们这个时候其实队列的前面还是空的，但是这个时候这块空间已经没有办法使用了，因此我们需要把这个问题解决掉，这个现象我们称为假溢出问题；

（5）解决这个假溢出问题的方法就是我们下面即将介绍的循环队列问题，循环队列就是使用的这个队列的尾指针指向这个队列的头指针，这个头尾项链之后就可以实现我们的这个尾部的数据空间全部占用之后，我们可以向这个队列的前面的部分空间去填充数据，这个就可以大大的提高这个空间的利用率，而且出队的数据越多，这个前面的空间就越大，这个空间的利用率就会越高；

2.循环队列的实现

（1）指针指向位置的说明

front指向的是这个队列的第一个数据前面的位置，而不是指向队列里面的第一个数据，rear指向的就是这个队列的最后一个数据；

（2）循环队列的实现，就是让这个最后一个下标加上1之后和这个队列里面的元素的个数取模，等于0，这个时候就相当于这个最后一个下标之后就是第一个下标，以此来实现这个循环队列；

（3）队列是空的临界条件：

我们假设这个时候的队列里面只有一个数据，指针的指向情况如图所示，front指向的就是这个队列里面的第一个数据的前一个位置，rear指向的就是这个队列的最后一个数据；

我们把这个数据出队之后，这个数据相当于就是被删除了，这个时候队列就是空的，删除数据之后我们的front指针需要向前移动一个位置，这个时候两个指针指向相同位置；

（4）队列数据是满的临界条件：

我们假设这个时候的队列里面只有一个位置是空余的，我们这个时候的指针的指向如图所示，rear指向这个队列数据的最后一个（这个时候已经是循环队列了，所以这个时候a6才是这个队列的最后一个数据），front指向这个队列的前面的一个位置；

我们把这个数据在入队一个之后，这个队列就是满的，但是添加数据之后，rear指针需要向后移动，这个时候两个指针再次指向了相同位置，只不过上一次是这个front向前移动，追上了rear指针，这一次是这个rear指针的移动和front指针指向了相同位置，因为这个数据的入队，我们需要移动这个rear指针，数据出队，我们需要移动这个front指针，两个最后的效果是一样的，但是中间经历的过程不是一样的；

（5）

（6）循环队列实现入队和出队

我们之前的这个思路完全不变，只不过这个循环之后，原来这个入队就是把这个rear直接向后移动一位即可，但是这个时候因为是循环队列，所以我们需要多考量一下，就是让这个rear+1能够被队列元素个数整除即可，这个时候就满足循环队列的要求；

同理这个队列里面数据的出队，原来就是这个front=front+1现在就是在这个front+1后面出以这个队列元素的个数进行取模即可；

（7）得到队列的第一个数据

我们让这个front+1位置元素赋值给这个数据，这个时候我们就可以得到我们想要的数据；

3.银行排队算法

（1）基本介绍

（2）需要的结构

第一个就是这个事件链表，表示这个银行业务的时间发生情况，交给这个计算机进行处理，还有一个就是需要这个队列数组，表示每一个窗口的这个排队的情况；

（3）具体举例说明

这个事件链表和这个队列数组之间有什么关系？我们通过两个例子说明一下：

首先看一下这个事件链表里面的16 2这个节点，这个2表示的就是右边的2号窗口，这个时候我们就去右边找到2号窗口，发现这个里面5 11两个数据，表示就是时间为5的时候，窗口2来了一个客户，经过11分钟的服务，这个客户完成离开，离开时间就是16，因此左边的这个链表里面节点写的数据是16；

再看一下这个左边链表的37 1，表示这个显示的是1号窗口的事件情况，这个时候我们发现这个时间为8时候，客户办理业务，经过29分钟之后，这个客户离开，因此这个离开时间就是8+29=37符合左边的链表节点显示的数据；

由此可见，链表和队列数组有着密切的联系，两者之间的数据是相互辅助的；

由于这个算法的综合性比较强，因此学有余力的同学可以自行学习，刚开始学习栈和队列的同学不建议上手，因为这个里面涉及到链表，和这个队列数组，综合性较强，需要把这些铺垫知识学好再去学习；

懒猫老师-数据结构-(12)队列应用：银行排队模拟(离散事件模拟)_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1nE411u7n4/?spm_id_from=333.788&vd_source=a432cb5e896a2b96961d1f73a6ebe0ca