湘潭做网站价格问下磐石网络,p2p网站建设 上海,企业建设厂房需要办哪些证,通州网站建设站开发评价1.循环队列的出现 #xff08;1#xff09;上面的这个就是一个普通的数据的入队和出队的过程我们正常情况下去实现这个入队和出队的过程#xff0c;就是这个数据从这个队尾进入#xff0c;从队头离开#xff0c;但是这个加入的时候肯定是没有其他的问题的#xff0c;直接…1.循环队列的出现 1上面的这个就是一个普通的数据的入队和出队的过程我们正常情况下去实现这个入队和出队的过程就是这个数据从这个队尾进入从队头离开但是这个加入的时候肯定是没有其他的问题的直接在这个队尾插入数据就可以了但是在队头把这个数据出队之后我们想要保持这个队列的完整性就需要使用循环把这个队列里面的数据向前进行移动这个是增加了这个方法的时间复杂度
2我们新的方法就是定义两个指针一个指针就是rear指针指向这个队列的尾部一个指针就是front指针指向这个队列的头部我们在进行这个数据的入队的时候我们先让这个rear1,然后把这个入队的数据放到这个指针指向的位置
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直接向后移动一位即可但是这个时候因为是循环队列所以我们需要多考量一下就是让这个rear1能够被队列元素个数整除即可这个时候就满足循环队列的要求
同理这个队列里面数据的出队原来就是这个frontfront1现在就是在这个front1后面出以这个队列元素的个数进行取模即可 7得到队列的第一个数据
我们让这个front1位置元素赋值给这个数据这个时候我们就可以得到我们想要的数据 3.银行排队算法
1基本介绍 2需要的结构
第一个就是这个事件链表表示这个银行业务的时间发生情况交给这个计算机进行处理还有一个就是需要这个队列数组表示每一个窗口的这个排队的情况 3具体举例说明 这个事件链表和这个队列数组之间有什么关系我们通过两个例子说明一下
首先看一下这个事件链表里面的16 2这个节点这个2表示的就是右边的2号窗口这个时候我们就去右边找到2号窗口发现这个里面5 11两个数据表示就是时间为5的时候窗口2来了一个客户经过11分钟的服务这个客户完成离开离开时间就是16因此左边的这个链表里面节点写的数据是16
再看一下这个左边链表的37 1表示这个显示的是1号窗口的事件情况这个时候我们发现这个时间为8时候客户办理业务经过29分钟之后这个客户离开因此这个离开时间就是82937符合左边的链表节点显示的数据
由此可见链表和队列数组有着密切的联系两者之间的数据是相互辅助的
由于这个算法的综合性比较强因此学有余力的同学可以自行学习刚开始学习栈和队列的同学不建议上手因为这个里面涉及到链表和这个队列数组综合性较强需要把这些铺垫知识学好再去学习
懒猫老师-数据结构-(12)队列应用银行排队模拟(离散事件模拟)_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1nE411u7n4/?spm_id_from333.788vd_sourcea432cb5e896a2b96961d1f73a6ebe0ca
