讯享网

 <p id="33FQF3CG">队列也是一种操作受限的线性数据结构，与栈很相似。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F9e4a7003j00slce0013d000iv00kfp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>01、定义</h5></p><p id="33FQF3CI">栈的操作受限表现为只允许在队列的一端进行元素插入操作，在队列的另一端只允许删除操作。这一特性可以总结为先进先出（First In First Out，简称FIFO）。这意味着在队列中第一个加入的元素将第一个被移除。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fdfd99f19j00slcf0019d0015o00glp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33FQF3CK"><strong>入队</strong>：向队列中添加新元素的行为叫做入队；</p><p id="33FQF3CL"><strong>出队</strong>：从队列中移除元素的行为叫做出队；</p><p id="33FQF3CM"><strong>队头</strong>：在队列中允许进行元素移除行为的一端称为队头；</p><p id="33FQF3CN"><strong>队尾</strong>：在队列中运行进行元素添加行为的一端称为队尾；</p><p id="33FQF3CO"><strong>空队列</strong>：当队列中没有元素时称为空队列。</p><p id="33FQF3CP"><strong>满队列</strong>：当队列是有限容量，并且容量已用完，则称为满队列。</p><p id="33FQF3CQ"><strong>队列容量</strong>：当队列是有限容量，队列容量表示队列可以容纳的最大元素数量。</p><p id="33FQF3CR"><strong>队列大小</strong>：表示当前队列中的元素数量。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Ff249fd16j00slcg002md0015o0129p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>02、分类</h5></p><p id="33FQF3CT">队列根据存储方式和功能特性有两种分类方式。</p><p><h5>1、根据存储方式分类</h5></p><p id="33FQF3CU">队列是逻辑结构，因此以存储方式的不同可以分为顺序队列和链式队列。</p><p id="33FQF3CV">顺序队列就是所有的队列元素都存储在连续的地址空间中，因此可以通过数组来实现顺序队列，因为数组的特性也导致顺序队列容量是固定的，不易扩容，这也导致容易浪费空间，同时还要注意元素溢出等问题。</p><p id="33FQF3D0">链式队列顾名思义就是采用链式方式存储，可以通过链表实现，因此链式队列可以做到无限扩容，大大的提高了内存利用率。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F709bd19fj00slcqpb0022d0010h00swp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>2、根据功能特性分类</h5></p><p id="33FQF3D2">根据功能特性可以分类出很多专有队列，下面我们列举几个简单介绍一下。</p><p id="33FQF3D3"><strong>阻塞队列</strong>：当空队列时会阻塞出队操作，当满队列时会阻塞入队操作。</p><p id="33FQF3D4"><strong>优先队列</strong>：队列中每个元素都有一个优先级别属性，而元素的出队操作取决于这个优先级别属性，即优先级别高则优先出队。</p><p id="33FQF3D5"><strong>延迟队列</strong>：队列中每个元素都标记一个时间记录，元素只有在指定的延时时间后才会触发出队操作。</p><p id="33FQF3D6"><strong>循环队列</strong>：当使用数组实现队列时，可以通过把队头和队尾相连接，即当队尾到达数组的尾端可以“绕回”数组的开头，通过这种巧妙的设计来提高数组空间利用率。</p><p id="33FQF3D7"><strong>双端队列</strong>：是一种两端都可以进行入队和出队操作的数据结构。</p><p id="33FQF3D8">根据这些队列特性，在不同的场景中可以起到意想不到的效果。</p><p id="33FQF3D9">下面我们将顺序队列和链式队列的实现进行详细讲解。</p><p><h5>03、实现（顺序队列）</h5></p><p id="33FQF3DA">下面我们借助数组来实现顺序队列，其核心思想是把数组的起始位置作为队头，把数组尾方向作为队尾。当发生出队行为时，需要把剩余所有数据向队头方向移动一位，为什么要做这步操作呢？</p><p id="33FQF3DB">首先顺序队列内部是数组，假设数组内可以存放7个元素，此时数组已存满，因此不可以再进行添加新元素入队操作了，然后我们对数组头元素进行出队操作，此时数组因为出队会留下一个空位，如下图。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fj00slcqpc001vd000y800qgp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33FQF3DD">那么此时是否可以进行入队操作呢？直接告诉我们应该可以，因为数组头已经有空位了。但是我们约定了队列只能从数组尾进行入队操作，而此时数组尾并没有空位提供给新入队的元素，因此实际上无法进行入队操作。</p><p id="33FQF3DE">那要如何处理呢？最简单的方法就是当发生出队操作时，后面所有的元素都向着队头方向移动一位，把队尾空出一位，这每出一个元素就可以入一个元素。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fj00slcqpe001vd000y800qgp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33FQF3DG">当然这也不是唯一方案，还是通过循环队列解决这一问题，有兴趣的可以研究一下。</p><p><h5>1、ADT定义</h5></p><p id="33FQF3DH">我们首先来定义顺序队列的ADT。</p><p id="33FQF3DI">ADT Queue{</p><p id="33FQF3DJ">数据对象：D 是一个非空的元素集合，D = {a1, a2, ..., an}，其中 ai 表示队列中的第i个元素，n是队列的长度。</p><p id="33FQF3DK">数据关系：D中的元素通过它们的索引（位置）进行组织，索引是从0到n-1的整数，并且遵循元素先进先出的原则。</p><p id="33FQF3DL">基本操作：[</p><p id="33FQF3DM">Init(n) ：初始化一个指定容量的空队列。</p><p id="33FQF3DN">Capacity：返回队列容量。</p><p id="33FQF3DO">Length：返回队列长度。</p><p id="33FQF3DP">Head：返回队头元素，当为空队列则报异常。</p><p id="33FQF3DQ">Tail：返回队尾元素，当为空队列则报异常。</p><p id="33FQF3DR">IsEmpty()：返回是否为空队列。</p><p id="33FQF3DS">IsFull()：返回是否为满队列。</p><p id="33FQF3DT">Enqueue()：入队即添加元素，当为满队列则报异常。</p><p id="33FQF3DU">Dequeue()：出队即返回队头元素并把其从队列中移除，当为空队列则报异常。</p><p id="33FQF3E1">定义好队列ADT，下面我们就可以开始自己实现的队列。</p><p><h5>2、初始化 Init</h5></p><p id="33FQF3E2">首先定义3个变量用于存放队列元素数组、队列容量以及队尾索引，而没有定义队头索引是因为队头索引永远等于0。</p><p id="33FQF3E3">初始化结构主要做几件事。</p><p id="33FQF3E4">a. 初始化队列的容量；</p><p id="33FQF3E5">b. 初始化存放队列元素数组；</p><p id="33FQF3E6">c. 初始化队尾索引；</p><p id="33FQF3E7">具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F4850f2e3j00slcqpg0063d000z800r3p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>3、获取队列容量 Capacity</h5></p><p id="33FQF3E9">这个比较简单直接把队列容量私有字段返回即可。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F2d01f476j00slcqpi0028d000z800ghp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>4、获取队列长度 Length</h5></p><p id="33FQF3EB">我们并没有定义队列长度的私有字段，因为队尾索引即表示数组最后一个元素索引，即可以代表队列长度，因此只需用队尾索引加1即可得到队列长度，同时需要注意判断队列是否为空，如果为空则报错。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F8d4e965dj00slcqpk002ud000z800map.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>5、获取队头元素 Head</h5></p><p id="33FQF3ED">基于我们上面的约定，队头元素永远对应数组的第一个元素，因此可以直接获取索引为0的数组元素。空队列则报错。具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fc3ffa45fj00slcqpm003md000z800map.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>6、获取队尾元素 Tail</h5></p><p id="33FQF3EF">因为我们定义了队尾索引私有变量，因此可以直接通过队尾索引获取。具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F33ae35abj00slcqpo003md000z800map.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>7、获取是否空队列 IsEmpty</h5></p><p id="33FQF3EH">是否空队列只需判断队尾索引是否小于0即可。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F7a9ea99cj00slcqpp002ed000z800ekp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>8、获取是否满队列 IsFull</h5></p><p id="33FQF3EJ">是否满队列只需判断队尾索引是否与队列容量减1相等，代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fe8c70236j00slcqpr002nd000z800ekp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>9、入队 Enqueue</h5></p><p id="33FQF3EL">入队只需向队列内部数组尾添加一个新元素即可，因此先把队尾索引先后移动一位，然后再把新元素赋值给队尾元素，同时还需要检查是否为满队列，如果是满队列则报错，具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F4de17b5cj00slcqpt0048d000z800n7p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>10、出队 Dequeue</h5></p><p id="33FQF3EN">出队则大致分为以下几步：</p><p id="33FQF3EO">a. 判断是否为空队列，空队列则报错；</p><p id="33FQF3EP">b. 取出队头元素暂存，重置队头元素为默认值；</p><p id="33FQF3EQ">c. 把队头后面所有元素向队头方向移动一位；</p><p id="33FQF3ER">d. 重置队尾元素为默认值；</p><p id="33FQF3ES">e. 队尾索引向队头方向移动一位，即队尾索引减1；</p><p id="33FQF3ET">f. 返回暂存的队头元素；</p><p id="33FQF3EU">具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F61d09be8j00slcqpw006zd000z8010op.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>04、实现（链式队列）</h5></p><p id="33FQF3F0">我们借助链表来实现链式队列，其核心思想是把链表尾节点作为队尾，把链表首元节点作为队头。</p><p><h5>1、ADT定义</h5></p><p id="33FQF3F1">相对于顺序队列的ADT来说，链式队列的ADT少了两个方法即获取队列容量和是否满队列，这也是链表特性带来的好处。</p><p><h5>2、初始化 Init</h5></p><p id="33FQF3F2">首先需要定义链表节点类，包含两个属性数据域和指针域。</p><p id="33FQF3F3">然后需要定义3个变量用于存放队头节点、队尾节点以及队列长度。</p><p id="33FQF3F4">而初始化结构主要初始化3个变量初始值，具体实现如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fb93cb536j00slcqpz008zd000z8019bp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>3、获取队列长度 Length</h5></p><p id="33FQF3F6">这个比较简单直接把队列长度私有字段返回即可。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F4255e2c2j00slc10025d000z800hdp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>4、获取队头元素 Head</h5></p><p id="33FQF3F8">获取队头元素可以通过队头节点数据域直接返回，但是要注意判断队列是否为空队列，如果为空队列则报异常。具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F12775c0ej00slc30040d000z800o3p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>5、获取队尾元素 Tail</h5></p><p id="33FQF3FA">获取队尾元素可以通过队尾节点数据域直接返回，但是要注意空栈则报异常。具体代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F96b29065j00slc5003yd000z800o3p.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>6、获取是否空队列 IsEmpty</h5></p><p id="33FQF3FC">是否空队列只需判断队头节点和队尾节点是否都为空即可。</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F0e5a00b5j00slc7002pd000z800fgp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>7、入队 Enqueue</h5></p><p id="33FQF3FE">入队大致分为以下几步：</p><p id="33FQF3FF">a. 需要先创建一个新节点；</p><p id="33FQF3FG">b. 如果原队尾节点不为空，则把原队尾节点指针域指向新节点；</p><p id="33FQF3FH">c. 把原队尾节点更新为新节点；</p><p id="33FQF3FI">d. 如果队头节点为空，则说明这是第一个元素，所以队头和队尾都是同一个节点，因此要把队尾节点赋值给队头节点；</p><p id="33FQF3FJ">e. 队列长度加1；</p><p id="33FQF3FK">具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2F73aed0b9j00slc9005rd000z800twp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p><h5>8、出队 Dequeue</h5></p><p id="33FQF3FM">出队则大致分为以下几步：</p><p id="33FQF3FN">a. 判断是否空队列，空队列则报错；</p><p id="33FQF3FO">b. 获取队头节点数据域暂存；</p><p id="33FQF3FP">c. 更新头节点为原队头节点对应的下一个节点；</p><p id="33FQF3FQ">d. 如果队头节点为空，则说明为空队列，队尾节点也要置空；</p><p id="33FQF3FR">e. 队列长度减1；</p><p id="33FQF3FS">f. 返回暂存的队头节点数据；</p><p id="33FQF3FT">具体实现代码如下：</p><p class="f_center"><img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F1014%2Fc9372d45j00slcc006ad000z800uvp.jpg&thumbnail=660x&quality=80&type=jpg"/><br/><br/></p><p id="33FQF3FV"><strong>注</strong>：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner</p>