讯享网

 <p style="margin-bottom: 5px;margin-top: 5px;" ><span style="font-size: 15px;" >&nbsp;&nbsp;&nbsp;&nbsp;队列和栈一样，是一种操作受限的线性表数据结构，具有<strong>先进先出</strong>的特点。队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。队列支持的操作也很有限，最基本的操作也是两个：<strong>入队 enqueue()</strong>，放一个数据到队列尾部；<strong>出队 dequeue()</strong>，从队列头部取出一个元素。</span></p><p style="margin-bottom: 5px;margin-top: 5px;"><br ></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 17px;" ><strong>一、顺序队列</strong></span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;顺序队列采用数组实现，由于数组初始化时需要一个容量，所以顺序队列声明是也需要提供一个队列的容量。除此之外，顺序队列维护了两个指针：front指向队列头部数据的前一个下标，rear指向队列尾部数据的下标。<br ></span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;数据存入时称为 入队enqueue()，包含两个步骤：</span></p><ul style="list-style-type: disc;" ><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">将尾指针后移：rear+1，当rear=front时表示队列为空；</span></p></li><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">若尾指针rear小于队列的最大下标maxSize-1，表示队列未满，则将数据存入数组中下标为rear的位置，否则无法插入数据。</span></p></li></ul><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;数据取出时称为 出队dequeue()，也包含两个步骤：<br ></span></p><ul style="list-style-type: disc;" ><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">将头指针后移：front+1，当rear=front时表示队列为空；</span></p></li><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">若队列不为空，取出数组中下标为front的数据。</span></p></li></ul><p style="margin-bottom: 5px;margin-top: 5px;"><strong><span style="font-size: 15px;">图解</span></strong><span style="font-size: 15px;"></span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">①队列初始化<br ></span></p><p style="text-align: center;" ><img style="width: 390px;height: 276px;" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__3400bf22-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">②队空队满判断条件</span><br ></p><p style="text-align: center;"><img style="text-align: center;white-space: normal;" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__b4-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">③入队出队操作</span><br ></p><p style="text-align: center;"><img style="" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__34688e54-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-bottom: 5px;margin-top: 5px;"><strong><span style="font-size: 15px;">代码实现</span></strong><span style="font-size: 15px;"></span></p><div ><ul ></ul><pre ><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></pre></div><p><br ></p><p><strong>二、链式队列</strong></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;链式队列采用链表实现，链式队列不需要指定容量，理论上只要内存足够，可以一直添加。链式队列同样需要维护两个指针：front指向队列的头部数据结点，rear指向队列的尾部数据结点。</span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;<strong>&nbsp;入队</strong> enqueue()：</span></p><ul style="list-style-type: disc;" ><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">如果队列为空：front==null，front和rear指针都指向新的数据结点</span></p></li><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">如果队列不为空：</span></p></li><ul style="list-style-type: square;" ><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">rear的next域指向新的数据结点</span></p></li><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">rear指针后移</span></p></li></ul></ul><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;<strong>出队&nbsp;</strong>dequeue()：<br ></span></p><ul style="list-style-type: disc;" ><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">将front指针所指结点保存在临时变量，避免丢失</span></p></li><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">判断front的next域是否为空</span></p></li><ul style="list-style-type: square;" ><li style="font-size: 15px;"><p style="margin-top: 5px;margin-bottom: 5px;" >如果是，说明该结点为最后一个结点，出队时将rear指针置空，front指针后移</p></li><li style="font-size: 15px;"><p style="margin-top: 5px;margin-bottom: 5px;">如果不是，front指针后移</p></li></ul><li style="font-size: 15px;"><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">然后返回临时变量保存的数据值</span></p></li></ul><p style="margin-bottom: 5px;margin-top: 5px;"><strong><span style="font-size: 15px;">图解</span></strong><span style="font-size: 15px;"></span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">①链式队列初始化及判空条件</span></p><p style="text-align: center;"><img style="" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__3496efba-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">②链式队列入队出队操作</span><br ></p><p style="text-align: center;"><img style="" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__34cf6b92-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-bottom: 5px;margin-top: 5px;"><strong><span style="font-size: 15px;">代码实现：</span></strong><span style="font-size: 15px;"></span></p><p style="margin-bottom: 5px;margin-top: 5px;"><span style="font-size: 15px;">定义结点类型</span><br ></p><div ><ul ></ul><pre ><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></pre></div><p><span style="font-size: 15px;">链式队列实现</span><br ></p><div ><ul ></ul><pre ><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></pre></div><p><br ></p><p><strong>三、环形队列</strong><br ></p><p>&nbsp;<span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;上面实现的队列中，即使数据出队了，空出来的空间也是无法重复利用的，特别是顺序队列，初始化时就定义了队列容量，为了实现空间的重复利用，可以将上面的队列调整成环形队列。</span></p><p style="margin-top: 10px;margin-bottom: 5px;" ><strong><span style="font-size: 15px;">思路分析：</span></strong><span style="font-size: 15px;"><br ></span></p><div><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;如果按照之前对rear和front的定义，当队列为空时：rear==front；当队列满时：rear==front也成立，因此通过rear==front不能判定队列是空还是满：</span></div><ul style="list-style-type: disc;" ><li><p><span style="font-size: 15px;">为了解决这个问题，可以少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志</span></p></li></ul><div><br ></div><ul style="list-style-type: disc;" ><li><p style=""><span style="font-size: 15px;">front变量的含义进行调整，由指向队列头的前一个元素改为指向队列的第一个元素,front的初始值为0；</span></p></li><li><p style=""><span style="font-size: 15px;">rear变量的含义进行调整，由指向队列尾元素改为指向队列尾的后一个元素，rear的初始值为0；&nbsp;</span></p></li><li><p style=""><span style="font-size: 15px;">当队列为空时：rear==front不变;&nbsp;</span></p></li><li><p style=""><span style="font-size: 15px;">当队列满时，条件是(rear+1)%maxSize==front</span></p></li><li><p style=""><span style="font-size: 15px;">当这样分析时，队列中有效的数据个数为：(rear+maxSize-front)%maxSize</span></p></li></ul><p style="margin-top: 10px;margin-bottom: 5px;"><strong><span style="font-size: 15px;">图解：</span></strong><span style="font-size: 15px;"></span></p><p style="text-align: center;"><img style="" src="https://oss-emcsprod-public.modb.pro/wechatSpider/modb__c-2b3f-11ec-94a3-fa163eb4f6be.png"></p><p style="margin-top: 5px;margin-bottom: 5px;"><strong><span style="font-size: 15px;">我们通过一个特殊情况说明为什么判断队列满的条件是：(rear+1)%maxSize==front：</span></strong><span style="font-size: 15px;"></span></p><p style="margin-top: 5px;margin-bottom: 5px;"><span style="font-size: 15px;">&nbsp;&nbsp;&nbsp;&nbsp;从上面的定义中，<span style="font-size: 15px;">约定以“队列头指针front在队尾指针rear的下一</span><span style="font-size: 15px;">个位</span><span style="font-size: 15px;">置上”作为队列“</span><span style="font-size: 15px;">满</span><span style="font-size: 15px;">”状态的标志</span>，如果我们直接定义队满条件是：rear+1==front，那么上图这种情况下，队列是满的，但是：rear=7，front=0，rear+1=8!=0；所以用rear+1的值对容量<span style="font-size: 15px;">maxSize</span>取余，让rear+1的值保证在0到<span style="font-size: 15px;">maxSize</span>-1之间；同理，在入队和出队移动<span style="font-size: 15px;">rea</span><span style="font-size: 15px;">r</span>和<span style="font-size: 15px;">fron</span>t指针时，也要对容量maxSize取<span style="font-size: 15px;">余</span>。</span></p><p style="margin-top: 5px;margin-bottom: 5px;"><strong><span style="font-size: 15px;">代码实现：</span></strong></p><div ><ul ></ul><pre ><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br></pre></div><p style="margin-top: 5px;margin-bottom: 5px;"><span style="font-size: 15px;"></span><br ></p>