基于顺序表实现队列循环队列的处理

1.假溢出的现象

下面的这个就是我们的假溢出的这个现象的基本的来源：

我们的这个队列里面是有9个位置的，我们知道这个队列里面应该是从后面进队列，从前面出队列，因此这个划去的这个1,2,3就是出队列的，因此我们的这个里面的这个head指针，也就是我们说的这个头指针，就是指向的我们的这个队列里面当前的第一个有效的元素；

但是随着我们的这个数据不断地进入我们的这个队列，这个时候，我们的这个队列里面的尾指针，也就是这个图上面的这个tail指针很快就指向了我们的这个队列的最后一个元素的下一个位置，因此这个时候我们想要插入这个10这个元素的时候，就不可以了；

但是我们发现这个队列里面是有9个位置的，但是这个里面的这个时候的有效的这个数据的个数就是6个，显然在我们的这个队列的前面是有这个空位置的，但是我们的这个10就是无法插入，在当前的这个数据结构下面；

就比如你去吃饭，餐馆里面是9个桌子，一共只有6个是有人的，但是你进去的时候，小二告诉你这个餐馆满了，你作何感想？这个现象就是我们的假溢出现象；

假溢出说的其实就是我们的这个这个tail指向的这个位置是我们的队列外面的这个位置，好像表示这个队列是溢出的，但是这个队列前面还是有数据空位置的，我们把这个情况称之为“假溢出”—好像是溢出的，但是实际上不是满的，这个其实名字和这个情况是高度匹配的，很容易理解；

2.循环队列

循环队列的引入就是为了解决上面出现的这个假溢出的情况：

就是当我们的这个tail指向的这个位置超过我们的这个队列里面的这个最后一个元素的这个范围之后，我们就让他指向我们的队列的开始位置，因为这个时候我们的开始的位置是有空位置的，这样就可以有效的解决这个假溢出的现象；

但是随着这个循环队列的这个引入，我们需要多引入一个变量，就是count，这个表示的就是我们的这个队列里面的这个有效元素的个数，当我们的这个count<size也就是小于我们的队列的大小的时候，我们就可以认为这个队列是假溢出的，我们可以让这个tail指向我们的第一个元素即可；

下面的这个就是我们的循环队列进行这个数据的插入的时候，相关的参数的变化：tail指向这个1下标的位置，我们的这个count也是需要加上1的，因为这个时候我们的有效数据加上一个；

3.顺序表实现队列架构

基本的一些这个方法：例如下面的这个里面出现的这个数据的插入push，和我们的这个队列里面的元素的初始化，front表示的就是获取我们的这个队列的首部的元素，pop就是弹出元素，clear相当于就是销毁这个队列，empty就是判断这个队列是不是空的，里面是不是存在元素，下面的这个就是我们会实现的这些方法；

4.顺序表模拟实现队列

因为我们的这个队列是基于这个顺序标的，所以这个队列实现的过程中会使用到这个顺序表里面的这个相关的方法，需要我们进行人为的这个补充；

下面的这个代码里面使用的是queue表示的是和我们的这个队列的相关的方法，这个vector就是顺序表里面的相关的方法的这个调用；

1）判断是不是空的，直接查看这个count也就是这个数据域里面的这个有效的数据个数是不是为0即可；

2）push就是直接进行这个数据的插入即可，首先需要看看是不是可以进行插入，如果我们的这个队列本来就是满的，这个时候肯定是无法进行这个插入的操作的；

然后就是如果可以进行这个插入的操作，我们就是调用的这个顺序表里面的这个数据的插入的方法，插入之后就让我们的这个末尾的指针后移一位即可，如果出现这个假溢出的情况需要让我们的这个tail指向第一个元素的位置；

插入数据之后这个count也就是这个有效的数据的个数也是需要调整的；

下面的这个是取出来这个队列里面的第一个元素以及删除数据（也就是出队列，让我们的这个head指针后移一位就可以了，然后更新我们的这个count即可）；

这个取出来第一个元素就更加容易了，直接调用这个顺序表里面的seek，找到这个指定的head指针指向的这个位置的元素）；

下面的这个是队列的销毁和我们的这个队列里面的元素的打印，销毁就是销毁释放我们的数据域，然后释放我们的整个队列，打印的话，需要注意我们的这个seek里面的这个第二个参数，需要模上这个size，这个主要也是针对于我们的这个循环队列进行处理的；

下面的这个就是我们的顺序表里面的相关的操作：首先就是插入元素，本来我们的这个顺序表里面进行这个数据的插入是需要移动元素的，但是我们的这个数据结构是队列，只可能是在这个tail指向的这个位置进行这个数据的插入，因此这个直接放在这个tail指向的位置就可以了；

查找的话，就是返回的这个对应的这个position位置的元素：

5.设计循环队列（校招难度）

(img-6kPPuWEg-1735306970521)]

[外链图片转存中…(img-YhrTnc6a-1735306970521)]