本文转载自微信公众号「bigsai」，作者bigsai。转载本文请联系bigsai公众号。前言栈和队列是好兄弟。我们之前介绍过一篇关于栈的文章（stacks,lastinfirstout）。栈的机制比较简单。后进先出就像进入一个小山洞。一个出入口只能是后进先出（外面的先出去，卡在里面的有点倒霉）。队列就像一个隧道，后面的人跟在前面的，前面的人先出去（先进先出）。日常排队就是对队列运行方式的说明！栈是一种喜新厌旧的数据结构。新的来了，它会处理新的，把旧的先停在这里（我们找人、约人的时候最讨厌这种人了）。,队列是一种公正性的数据结构，排队先来先服务，顺序很重要，所以这种数据结构在程序设计，中间件等方面有广泛的应用，比如消息队列，FIFO磁盘调度，二进制树层顺序遍历，BFS广度优先搜索等。队列的核心概念是：先进先出！这个非常基础又重要的数据结构一定要掌握手写！虽然队列是先进先出的核心规则，但是手写还是有很多细节需要考虑的！队列的概念：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作。和栈一样，队列是一个有限操作的线性表。插入操作结束的称为队尾，删除操作结束的称为队头。同时，最好在看这篇文章之前了解序列表的基本操作和栈的数据结构！学习效果更好！队列介绍我们在设计队列的时候可以选择一个标准。这里，我们将使用力扣622来设计一个循环队列作为队列设计。标准。队前：删除数据结束。rearofthequeue：插入数据的末端。对于数组来说，从数组后面插入比较容易，从数组前面插入比较困难，所以数组实现的队头一般在数组前面，而队尾队列在数组后面；而对于链表，插入和删除是在两端进行的。)删除了最方便的尾部插入选项。实现方法：MyCircularQueue(k):构造函数，设置队列长度为k。Front：从队列的前面获取元素。如果队列为空，则返回-1。Rear：获取队列尾部的元素。如果队列为空，则返回-1。enQueue(value)：向循环队列中插入一个元素。如果插入成功则返回true。deQueue()：从循环队列中移除一个元素。如果删除成功则返回真。isEmpty()：检查循环队列是否为空。isFull()：检查循环队列是否已满。普通队列根据上面的介绍，我们可以很容易的知道数组是如何实现的。队列是用数组建模的。要考虑初始化，插入，问题。这个普通队列需要注意的一些操作是：初始化：数组前后都指向0。（前后下标相等时，队列为空）入队：队列未满，数组没有越界，队列尾部先传值，然后在队列尾部下标+1（队列尾部其实是提前一位，为了区分情况一个空队列）并出队：如果队列不为空，先取队头的元素，给队头加1。但是很容易找到问题所在。每个空间域只能使用一次，造成空间的极度浪费，而且非常容易越界！循环队列（数组实现）就是针对上面的问题。有更好的解决办法！就是复用已经申请的（数组）内存。这就是我们所说的循环队列。循环队列的一个好处是我们可以利用这个队列上以前使用过的空间。在普通队列中，一旦队列满了，我们就不能插入下一个元素，即使队列的前面还有空间。但是有了循环队列，我们??可以使用这个空间来存储新值。数组实现的循环队列逻辑修改。因为我们只需要队列中前后两个指针。后方按道理在后，前方按道理在前，但实际上他们不一定是谁在前，谁在后。计算距离的时候需要把数组的长度加上后面减去前面，然后计算余数。能。初始化：数组的front和rear都指向0。这里需要注意的是，当front和rear在同一位置时，证明队列为空。还有这里，我在实现的时候，把array申请的大一些，空出一个位置，防止队列满了的时候前后排在同一个位置。入队：队未满，先传队尾的值，然后rear=(rear+1)%maxsize；出队：队伍不为空，先取队头的元素，front=(front+1)%maxsize；这里留队如果在添加入口指标的时候需要去头部位置，这里直接+1找位置（相比判断是否在末尾，更简洁），其中maxsize是实际的数组的大小。是否为空：returnrear==front;尺寸：return(rear+maxsize-front)%maxsize；这里很容易理解，一张图就能解释清楚，不管是正面还是反面，都能满足要求。这里有几个需要注意的地方，就是如果遇到结束，是否需要转向结束索引加法。可以判断是否在数组末尾。也可以直接+1求余数。其中maxsize是数组的实际大小。具体实现：publicclassMyCircularQueue{privateintdata[];//数组容器privateintfront;//headprivateintrear;//tailprivateintmaxsize;//最大长度publicMyCircularQueue(intk){data=newint[k+1];front=0;rear=0;maxsize=k+1;}publicbooleanenQueue(intvalue){if(isFull())returnfalse;else{data[rear]=value;rear=(rear+1)%maxsize;}returntrue;}publicbooleandeQueue(){if(isEmpty())返回假；else{front=(front+1)%maxsize;}returntrue;}publicintFront(){if(isEmpty())return-1;returndata[front];}publicintRear(){if(isEmpty())return-1;returndata[(rear-1+maxsize)%maxsize];}publicbooleanisEmpty(){returnrear==front;}publicbooleanisFull(){return(rear+1)%maxsize==front;}}循环队列（链表实现）为链表实现的队列，要按照先进先出的规则来考虑头尾的位置。我们知道队列是先进先出的。对于链表，我们可以尽可能使用单链表。同时，必须考虑效率。使用链表的实现方案大致有两种：方案一如果把队头设置在链表的尾部，则把队尾设置在链表的头部。那么队尾的插入在链表头是没有问题的，实现起来也很容易，但是如果在链表的尾部进行队头的删除，如果尾部没有设置指针，会遍历到队尾，但是设置尾指针delete需要删除。它的前驱节点需要是双向链表，比较麻烦。解法2如果把队头设置在链表的头部，把队尾设置在链表的尾部，那么在链表尾部插入队列是没有问题的（使用tail指针直接指向next），实现起来很简单。如果在链表的头部删除队头也很容易进行，也就是我们之前常说的头节点删除节点。所以我们最终采用的是方案2的首节点尾指针的单链表！主要操作是：初始化：设置一个头节点，front和rear都先指向它。入队：rear.next=va;rear=va;(va为插入节点)退出：队伍不为空，front.next=front.next.next；经典lead节点被删除，但是如果只删除一个节点，则需要添加一个rear=front，否则rear会失去连接。是否为空：returnrear==front;或者自定义维护len判断返回len==0大小：front遍历到rear的节点个数，或者自定义维护len直接返回（这里不实现）。实现代码：publicclassMyCircularQueue{classnode{intdata;//节点nodenext的结果;//下一个连接的节点publicnode(){}publicnode(intdata){this.data=data;}}nodefront;//相当于headnodenoderear;//相当于tail/endintmaxsize;//最大长度intlen=0;publicMyCircularQueue(intk){front=newnode(0);rear=front;maxsize=k;len=0;}publicbooleanenQueue(intvalue){if(isFull())returnfalse;else{nodeva=newnode(value);rear.next=va;rear=va;len++;}returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse;else{front.next=front.next.next;len--;//注意如果删除，需要将rear指向frontif(len==0)rear=front;}returntrue;}publicintFront(){if(isEmpty())return-1;returnfront.next.data;}publicintRear(){if(isEmpty())return-1;returnrear.data;}publicbooleanisEmpty(){returnlen==0;//returnrear==front;}publicbooleanisFull(){returnlen==maxsize;}}双向队列（加餐）旨在实现双端队列。其实大家经常用到的ArrayDeque就是一个经典的双向队列，它是基于数组实现的，效率很高。我们这里实现的双向队列模板是基于里扣641设计的CircularDouble-EndedQueue，你的实现需要支持以下操作：MyCircularDeque(k):构造函数，双端队列的大小为k。insertFront()：向双端队列的头部添加一个元素。如果操作成功则返回true。insertLast()：向双端队列的尾部添加一个元素。如果操作成功则返回true。deleteFront()：从双端队列的头部删除一个元素。如果操作成功则返回true。deleteLast()：从双端队列的尾部删除一个元素。如果操作成功则返回true。getFront()：从双端队列的头部获取一个元素。如果双端队列为空，则返回-1。getRear()：获取双端队列的最后一个元素。如果双端队列为空，则返回-1。isEmpty()：检查双端队列是否为空。isFull()：检查双端队列是否满。其实有了上面的基础，实现一个双端队列就非常容易了。与单端循环队列一致的操作有很多。只多了一个在队头插入，在队尾删除的操作。下面简单分析一下这两个操作：在队头插入：队友前面的下标位置本身是有值的，所以前面应该先背一个再赋值，但是必须考虑是满还是满数组越界。队尾删除：只需要从后面的位置减1，还要考虑是否为空或越界。具体实现代码：publicclassMyCircularDeque{privateintdata[];//数组容器privateintfront;//headprivateintrear;//tailprivateintmaxsize;//最大长度/*初始化最大尺寸为k*/publicMyCircularDeque(intk){data=newint[k+1];front=0;rear=0;maxsize=k+1;}/**headinsert*/publicbooleaninsertFront(intvalue){if(isFull())returnfalse;else{front=(front+maxsize-1)%maxsize;data[front]=value;}returntrue;}/**Tailinsert*/publicbooleaninsertLast(intvalue){if(isFull())returnfalse;else{data[rear]=value;rear=(rear+1)%maxsize;}returntrue;}/**正常头删除*/publicbooleandeleteFront(){if(isEmpty())returnfalse;else{front=(front+1)%maxsize;}returntrue;}/**taildelete*/publicbooleandeleteLast(){if(isEmpty())returnfalse;else{rear=(rear+maxsize-1)%maxsize;}returntrue;}/**Getthefrontitem*/publicintgetFront(){if(isEmpty())return-1;returndata[front];}/**Getthelastitemfromthedeque.*/publicintgetRear(){if(isEmpty())return-1;returndata[(rear-1+maxsize)%maxsize];}/**检查swhetherthecirculardequeisemptyornot.*/publicbooleanisEmpty(){returnfront==rear;}/**Checkswhetherthecirculardequeisfullornot.*/publicbooleanisFull(){return(rear+1)%maxsize==front;}}小结对于队列来说，数据结构比栈复杂，但是并不难。理解先进先出，用数组或者链表就可以实现。对于数组，队列尾指向的位置为空，而链表的前面（同头）是头指针为空，所以需要注意实现方法一样在不同结构中的作用。数组实现的循环队列可以很好的利用数组空间，双向队列是一种既可以作为队列又可以作为栈使用的高效数据结构。掌握它还是很有必要的。
