德州企业网站优化公司,南宁网站建设企业网站,上海市城乡建设网站,做网站买虚拟服务器文章目录 1.假溢出的现象2.循环队列3.顺序表实现队列架构4.顺序表模拟实现队列5.设计循环队列#xff08;校招难度#xff09; 1.假溢出的现象
下面的这个就是我们的假溢出的这个现象的基本的来源#xff1a;
我们的这个队列里面是有9个位置的#xff0c;我们知道这个队列… 文章目录 1.假溢出的现象2.循环队列3.顺序表实现队列架构4.顺序表模拟实现队列5.设计循环队列校招难度 1.假溢出的现象
下面的这个就是我们的假溢出的这个现象的基本的来源
我们的这个队列里面是有9个位置的我们知道这个队列里面应该是从后面进队列从前面出队列因此这个划去的这个1,2,3就是出队列的因此我们的这个里面的这个head指针也就是我们说的这个头指针就是指向的我们的这个队列里面当前的第一个有效的元素
但是随着我们的这个数据不断地进入我们的这个队列这个时候我们的这个队列里面的尾指针也就是这个图上面的这个tail指针很快就指向了我们的这个队列的最后一个元素的下一个位置因此这个时候我们想要插入这个10这个元素的时候就不可以了
但是我们发现这个队列里面是有9个位置的但是这个里面的这个时候的有效的这个数据的个数就是6个显然在我们的这个队列的前面是有这个空位置的但是我们的这个10就是无法插入在当前的这个数据结构下面
就比如你去吃饭餐馆里面是9个桌子一共只有6个是有人的但是你进去的时候小二告诉你这个餐馆满了你作何感想这个现象就是我们的假溢出现象 假溢出说的其实就是我们的这个这个tail指向的这个位置是我们的队列外面的这个位置好像表示这个队列是溢出的但是这个队列前面还是有数据空位置的我们把这个情况称之为“假溢出”—好像是溢出的但是实际上不是满的这个其实名字和这个情况是高度匹配的很容易理解
2.循环队列
循环队列的引入就是为了解决上面出现的这个假溢出的情况
就是当我们的这个tail指向的这个位置超过我们的这个队列里面的这个最后一个元素的这个范围之后我们就让他指向我们的队列的开始位置因为这个时候我们的开始的位置是有空位置的这样就可以有效的解决这个假溢出的现象
但是随着这个循环队列的这个引入我们需要多引入一个变量就是count这个表示的就是我们的这个队列里面的这个有效元素的个数当我们的这个countsize也就是小于我们的队列的大小的时候我们就可以认为这个队列是假溢出的我们可以让这个tail指向我们的第一个元素即可 下面的这个就是我们的循环队列进行这个数据的插入的时候相关的参数的变化tail指向这个1下标的位置我们的这个count也是需要加上1的因为这个时候我们的有效数据加上一个 3.顺序表实现队列架构
基本的一些这个方法例如下面的这个里面出现的这个数据的插入push和我们的这个队列里面的元素的初始化front表示的就是获取我们的这个队列的首部的元素pop就是弹出元素clear相当于就是销毁这个队列empty就是判断这个队列是不是空的里面是不是存在元素下面的这个就是我们会实现的这些方法 4.顺序表模拟实现队列
因为我们的这个队列是基于这个顺序标的所以这个队列实现的过程中会使用到这个顺序表里面的这个相关的方法需要我们进行人为的这个补充
下面的这个代码里面使用的是queue表示的是和我们的这个队列的相关的方法这个vector就是顺序表里面的相关的方法的这个调用
1判断是不是空的直接查看这个count也就是这个数据域里面的这个有效的数据个数是不是为0即可
2push就是直接进行这个数据的插入即可首先需要看看是不是可以进行插入如果我们的这个队列本来就是满的这个时候肯定是无法进行这个插入的操作的
然后就是如果可以进行这个插入的操作我们就是调用的这个顺序表里面的这个数据的插入的方法插入之后就让我们的这个末尾的指针后移一位即可如果出现这个假溢出的情况需要让我们的这个tail指向第一个元素的位置
插入数据之后这个count也就是这个有效的数据的个数也是需要调整的 下面的这个是取出来这个队列里面的第一个元素以及删除数据也就是出队列让我们的这个head指针后移一位就可以了然后更新我们的这个count即可
这个取出来第一个元素就更加容易了直接调用这个顺序表里面的seek找到这个指定的head指针指向的这个位置的元素 下面的这个是队列的销毁和我们的这个队列里面的元素的打印销毁就是销毁释放我们的数据域然后释放我们的整个队列打印的话需要注意我们的这个seek里面的这个第二个参数需要模上这个size这个主要也是针对于我们的这个循环队列进行处理的 下面的这个就是我们的顺序表里面的相关的操作首先就是插入元素本来我们的这个顺序表里面进行这个数据的插入是需要移动元素的但是我们的这个数据结构是队列只可能是在这个tail指向的这个位置进行这个数据的插入因此这个直接放在这个tail指向的位置就可以了 查找的话就是返回的这个对应的这个position位置的元素 5.设计循环队列校招难度 (img-6kPPuWEg-1735306970521)]
[外链图片转存中…(img-YhrTnc6a-1735306970521)]
