今天继续给大家端上一盘硬菜，保证你吃到一半——打嗝。和栈一样，队列也是一种非常有用的数据结构。同时，它也很特别。它只允许在队尾插入元素，在队头删除元素，即一端入一端出。在网络购票普及之前，我们大多数人都不得不去车站的售票大厅买票。我们经常排到无处可去的地步。队列和现实中的队列一模一样。排队的第一个人先买票，然后离开，后面的人移到队伍的最前面，直到队伍消失。队列遵循FirstInFirstOut，简称FIFO，即先进先出，第一个进入队列的先出来。上图中，1比2早入队，也比2早出队，表现良好。对于队列这样的数据结构，它有两个常见的动作：enqueue，我个人喜欢翻译成queue，指的是将元素放入队列的动作。Dequeue，出列，是指从队列中移除元素的动作。了解了队列的基本操作之后，我们再深入思考一下队列是如何工作的。1）建立顺序队列结构，需要静态分配或动态申请一系列连续的存储空间。2）然后设置两个管理指针：队列头指针FRONT，指向队列头部的元素；队列尾指针REAR，指向队列尾部的元素。初始化时，FRONT和REAR都设置为-1。3）入队时，检查队列是否满，需要一个isFull()方法来判断；对于第一个元素，将FRONT的值设置为0；每次在队尾插入一个元素时，REAR加1，然后把队尾的元素指向REAR。4）出队时检查队列是否为空，需要一个isEmpty()方法来判断；使用临时变量保存队头元素，以便出队后返回；队头每删除一个元素，FRONT加1；如果它是最后一个元素，则将FRONT和REAR重置为-1。当队列为空时，FRONT和REAR等于-1；当元素1入队时，FRONT变为1，REAR加1变为0，queue[FRONT]=queue[REAR]为1；元素2入队时REAR加1，变为1，queue[REAR]为2，queue[FRONT]仍为1；然后，元素3进入队列；元素4进入队列；元素5入队，REAR变为4，queue[REAR]为5，queue[FRONT]仍为1。当元素1出队时，FRONT为0，queue[FRONT]为1，则FRONT加1变为1；当元素2出队时，queue[FRONT]为2，则FRONT加1变为2；然后，当元素3出队时；元素4出列；并且元素5出队，queue[FRONT]为5，FRONT为4，REAR为4。出队后，FRONT和REAR重置为-1。假设队列中的元素是int类型，队列的大小为5，我们可以用Java语言定义最简单的队列。需要3个字段：intqueue[]，一个int类型的数组存放数据intfront，一个int类型的headmarkintrear，一个int类型的tailmarkclassQueue{intSIZE=5;intitems[]=newint[SIZE];intfront,rear;}初始化队列：Queue(){front=-1;rear=-1;}入队：voidenQueue(intelement){if(isFull()){System.out.println("队列已满");}else{if(front==-1)front=0;rear++;items[rear]=element;System.out.println("insert"+element);}}出列：intdeQueue(){intelment;if(isEmpty()){System.out.println("队列为空");return(-1);}else{element=items[front];if(front>=rear){front=-1;rear=-1;}else{front++;}System.out.println("删除->"+元素);return(element);}}检查队列是否满：booleanisFull(){if(front==0&&rear==SIZE-1){returntrue;}returnfalse;}检查队列是否为空：booleanisEmpty(){if(front==-1)returntrue;elsereturnfalse;}来个main()方法测试一下：voiddisplay(){inti;if(isEmpty()){System.out.println("队列为空");}else{System.out.println("\n团长下标->"+front);System.out.println("element->");for(i=front;i<=rear;i++)System.out.print(items[i]+"");System.out.println("\n队尾下标->"+rear);}}publicstaticvoidmain(String[]args){Queueq=newQueue();//队列为空时不允许入队q.deQueue();//enQueue5elementsq.enQueue(1);q.enQueue(2);q.enQueue(3);q.enQueue(4);q.enQueue(5);//队列满时不允许入队q.enQueue(6);q.display();//出队q.deQueue();//Printq.display();}打印结果如下：队列为空Insert1Insert2Insert3Insert4Insert5队列满头的下标->0元素->12345尾的下标->4删除->1队头的下标->1个元素->2345尾部下标->4队列为空插入1插入2插入3插入4插入5队列已满队下标head->0element->12345队尾下标->4delete->1队头下标->1element->2345队尾下标->4我们ll，这个基本队列已经可以正常工作了，但是它有一个问题：出列N个元素后，应该可以入列N个元素吧？因为节省了N空间Queueq=newQueue();//enQueue5个元素q.enQueue(1);q.enQueue(2);q.enQueue(3);q.enQueue(4);q.enQueue(5);//队列q.deQueue();q.deQueue();q.enQueue(6);q.enQueue(7);但实际上这段代码运行时报错：Insert1Insert2Insert3Insert4Insert5Delete->1Delete->2Exceptioninthread"main"java.lang.ArrayIndexOutOfBoundsException:Index5outofboundsforlength5在com.itwanger.queue.Queue.enQueue(Queue.java:23)atcom.itwanger.queue.Queue.main(Queue.java:89)查看ArrayIndexOutOfBoundsException我们会知道，数组超出范围。这是因为我们用数组来实现队列，出队时REAR没有递减，导致入队时items[rear++]超出了数组的边界。问题可能归咎于我们实现队列的方式，或者很明显队列的基本类型存在局限性。随着不断的进出队列操作，队列中的元素在不断变化，队列占用的存储空间也在分配的连续空间中不断移动。当REAR增加超过数组大小时，队列不能添加新元素。其实还有很多空间可以使用，只是它们仍然被已经出队的元素占据——所谓的“占有”。除非在删除所有元素后重置FRONT和REAR，否则无法重用队列。由于队列基本类型的局限性，我们迫切需要一种新型队列的出现——循环队列（Circularqueue）登场。环形队列如何工作？它是如何解决这个问题的？1）还需要一系列连续的存储空间。2）初始化与基本类型队列完全相同；3）入队时检查队列是否已满。此时的条件除FRONT=0&&REAR=SIZE+1外，即队头有元素，队尾有元素，即第一个填满队列时时间。还需要补充一点：FRONT=REAR+1，也就是当队尾紧跟在队头之后，循环填满队列的时候。代码如下所示。booleanisFull(){if(front==0&&rear==SIZE-1){returntrue;}if(front==rear+1){returntrue;}returnfalse;}一旦REAR加1超过分配的连续空间，就让它指向连续空间的起始位置。也就是说，REAR需要重新取整，从0开始，可以用(REAR+1)%SIZE余数的形式表示。代码如下所示。voidenQueue(intelment){if(isFull()){System.out.println("队列已满");}else{if(front==-1)front=0;rear=(rear+1)%SIZE;items[rear]=element;System.out.println("insert"+element);}}4)出队时，当FRONT加1超过分配的连续空间时，让它指向连续空间起点。也就是说，FRONT需要重新旋转，从0开始，可以用(FRONT+1)%SIZE来表示。代码如下所示。intdeQueue(){intelment;if(isEmpty()){System.out.println("队列为空");return(-1);}else{element=items[front];if(front>=rear){front=-1;rear=-1;}else{front=(front+1)%SIZE;}System.out.println("delete->"+element);return(element);}}main()method测试代码不再贴出，和基本类型的队列区别不大。一图胜千言，我们画一张图来展示一下环队列是如何工作的。当队列第一次被填满时，两个元素被出队。此时下标为0和1的两个位置空出，然后将元素6加入队列，也就是说6成为队尾，即REAR等于0；再入元素7，7成为队尾，即REAR等于1。现在，我们来思考一个问题。如果此时执行deQueue()方法出列一个元素，会移除哪个元素？答案是元素3，因为此时它在队首，后面跟着元素4和元素5、元素6、元素7，虽然直观上好像不是这样，但是很容易理解是否将其想象为圆形而不是直线。相比之下，环形队列比普通类型的队列在容量上得到了更充分的利用。队列除了基本类型和循环队列外，还有优先级队列和双端队列。虽然都属于队列的范畴，但实际上并没有遵循先进先出的规则，所以打算拿出来单独说说。.本文转载自微信公众号“沉默王二”，可通过以下二维码关注。转载本文请联系沉默王二公众号。
