数据结构—队列(Queue)的原理以及Java实现案例

Answer 1

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。本文详细介绍了队列的特性，并且使用Java语言分别实现了基于顺序结构和链式结构的队列。

1 队列的概述

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,......,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。

因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。

关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

2 队列的顺序存储结构实现2.1 队列的顺序存储结构概述

和栈不同的是，队列的入队和出队操作在不同端。采用数组来实现时，如果和实现栈的思想一样，如果队头在数组元素最大索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为O(1)；但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)。如果队头在数组元素的起始索引处，那么出队列到时变快了，但是入队列的时间复杂度却又变成O(n)了。

因此，这里要灵活处理对头或者队尾，不再是固定在数组起始索引或者最大索引处，应该是可变的，此时需要添加外部指针用来保存“队头”和“队尾”。操作数据的时候只需要操作队头和队尾就行了，这样入队和出队的时间复杂度都是O(1)。

按照上面的做法，队头和队尾是不用固定了，入队和出队操作确实很方便。但是可能造成索引溢出以及内存浪费，如下图：

可能会出现图上的情况，队头被移动到数组的中间，而队尾由于添加元素，移动到数组尾部，此时如果再次入队，由于数组索引溢出将会抛出ArrayIndexOutOfBoundsException，但是数组的前半部分空间却还没有使用，此时又造成了空间浪费。

上面这种溢出，称为“假溢出”。假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列解决了假溢出的问题，同时入队和出队时间都是O(1)。此时需要考虑的就只是数组的容量有限的问题了。

2.2 数组循环队列的简单实现/***数组实现的循环队列,为了方便,这里底层数组设计为不可扩展*/publicclassMyArrayLoopQueue<E>{/***采用数组实现链式存储*/privatefinalObject[]elements;/***容量*/privatefinalintcapacity;/***队头元素索引*/privateintfirst;/***队尾元素索引*/privateintend;/***元素个数*/privateintsize;/***构造器初始化数组**@paramcapacity容量*/publicMyArrayLoopQueue(intcapacity){this.capacity=capacity;this.elements=newObject[capacity];}/***入队,元素添加在队尾**@paramelement添加的元素*@return添加成功返回true，添加失败返回false*/publicbooleanadd(Eelement){//如果队列容量已满.添加失败返回falseif(size==capacity){returnfalse;}if(size==0){/*如果是第一次放元素,则队头和队尾都指向索引0处的元素*/elements[end]=element;}elseif(end+1==capacity){/*如果end+1等于capacity说明队尾空间满了，转向队头,队尾队尾索引置0，循环*/end=0;elements[end]=element;}else{/*否则,队尾索引正常自增*/elements[++end]=element;}//size自增1size++;returntrue;}/***出队,删除队头元素**@return被移除的元素,或者null*/publicEremove(){//队列是否已空if(size==0){//返回nullreturnnull;}Objecto=elements[first];//移除队头元素elements[first]=null;//如果队头索引+1之后等于capacity，重置队头索引，循环if(++first==capacity){first=0;}//如果出队列后队列为空,那么重置队头和队尾索引if(--size==0){first=0;end=0;}return(E)o;}/***返回队列元素数量**@return*/publicintsize(){returnsize;}/***清空队列*/publicvoidclear(){for(inti=0;i<size;i++){elements[i]=null;}size=0;first=0;end=0;}/***重写了toString方法**@return*/@OverridepublicStringtoString(){StringBuilderstringBuilder=newStringBuilder();if(size==0){stringBuilder.append("[]");returnstringBuilder.toString();}stringBuilder.append("[");if(first<end){for(inti=first;i<=end;i++){stringBuilder.append(elements[i]);if(i!=end){stringBuilder.append(",");}}}elseif(size==1){stringBuilder.append(elements[first]);}else{for(inti=first;i<capacity;i++){stringBuilder.append(elements[i]);stringBuilder.append(",");}for(inti=0;i<=end;i++){stringBuilder.append(elements[i]);if(i!=end){stringBuilder.append(",");}}}stringBuilder.append("]");returnstringBuilder.toString();}/***增强toString方法,用于测试**@return*/publicStringtoStringPlus(){StringBuilderstringBuilder=newStringBuilder();if(size==0){stringBuilder.append("[]");stringBuilder.append(";first:").append(first).append(";end:").append(end).append(";size:").append(size);returnstringBuilder.toString();}stringBuilder.append("[");if(first<end){for(inti=first;i<=end;i++){stringBuilder.append(elements[i]);if(i!=end){stringBuilder.append(",");}}}elseif(size==1){stringBuilder.append(elements[first]);}else{for(inti=first;i<capacity;i++){stringBuilder.append(elements[i]);stringBuilder.append(",");}for(inti=0;i<=end;i++){stringBuilder.append(elements[i]);if(i!=end){stringBuilder.append(",");}}}stringBuilder.append("]");stringBuilder.append(";first:").append(first).append(";end:").append(end).append(";size:").append(size);returnstringBuilder.toString();}}2.2.1 测试MyArrayLoopQueue<Object>objectMyArrayLoopQueue=newMyArrayLoopQueue<>(4);System.out.println("入队========>");objectMyArrayLoopQueue.add(11);objectMyArrayLoopQueue.add(22);objectMyArrayLoopQueue.add(33);System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");objectMyArrayLoopQueue.remove();System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");objectMyArrayLoopQueue.remove();System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("入队========>");objectMyArrayLoopQueue.add(44);objectMyArrayLoopQueue.add(55);System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("入队========>");objectMyArrayLoopQueue.add(null);System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("入队失败========>");booleanadd=objectMyArrayLoopQueue.add(77);System.out.println(add);System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");System.out.println(objectMyArrayLoopQueue.remove());System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");System.out.println(objectMyArrayLoopQueue.remove());System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");System.out.println(objectMyArrayLoopQueue.remove());System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");System.out.println(objectMyArrayLoopQueue.remove());System.out.println(objectMyArrayLoopQueue.toStringPlus());System.out.println("出队========>");System.out.println(objectMyArrayLoopQueue.remove());System.out.println(objectMyArrayLoopQueue.toStringPlus());3 队列的链式存储结构及实现3.1 队列的链式存储结构概述

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

可以看出来，使用链式结构实现队列相比顺序结构的实现更加简单。

3.2 队列的链式存储结构简单实现/***队列的链式储存结构的简单单链表实现*/publicclassMySingleLinkedQueue<E>{/***空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。*/publicMySingleLinkedQueue(){}/***元素个数*/privateintsize;/***指向队头结点的引用*/privateNode<E>first;/***指向队尾结点的引用*/privateNode<E>end;/***单链表内部的节点*/privatestaticclassNode<E>{//下一个结点的引用Node<E>next;//结点数据Edata;//节点构造器publicNode(Edata,Node<E>next){this.data=data;this.next=next;}}/***入队，添加元素到单链表尾部**@parame要添加的元素*/publicvoidadd(Ee){//创建新节点Node<E>newNode=newNode<>(e,null);if(end!=null){/*如果尾结点不为空*/end.next=newNode;//改变队尾节点引用end=newNode;}else{end=newNode;first=newNode;}++size;}/***出队，删除单链表头部元素**@return被删除的元素*/publicEremove(){//如果头结点为空,抛出异常if(first==null){thrownewNoSuchElementException("队列已经为空");}Ee=first.data;//改变队头节点引用first=first.next;//如果元素为0,则将队尾节点引用置空if(--size==0){end=null;}returne;}/***获取元素数量*/publicintsize(){returnsize;}@OverridepublicStringtoString(){StringBuilderstringBuilder=newStringBuilder();if(size>0){Node<E>f=first;stringBuilder.append("[");for(inti=0;i<size;i++){stringBuilder.append(f.data);if(i!=size-1){stringBuilder.append(",");}f=f.next;}stringBuilder.append("]");returnstringBuilder.toString();}return"[]";}}3.2.1 测试MySingleLinkedQueue<Object>objectMySingleLinkedQueue=newMySingleLinkedQueue<>();System.out.println("入队========>");objectMySingleLinkedQueue.add(11);objectMySingleLinkedQueue.add(22);objectMySingleLinkedQueue.add(33);System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");objectMySingleLinkedQueue.remove();System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");objectMySingleLinkedQueue.remove();System.out.println(objectMySingleLinkedQueue.toString());System.out.println("入队========>");objectMySingleLinkedQueue.add(44);objectMySingleLinkedQueue.add(55);System.out.println(objectMySingleLinkedQueue.toString());System.out.println("入队========>");objectMySingleLinkedQueue.add(null);System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");System.out.println(objectMySingleLinkedQueue.remove());System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");System.out.println(objectMySingleLinkedQueue.remove());System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");System.out.println(objectMySingleLinkedQueue.remove());System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队========>");System.out.println(objectMySingleLinkedQueue.remove());System.out.println(objectMySingleLinkedQueue.toString());System.out.println("出队异常========>");System.out.println(objectMySingleLinkedQueue.remove());System.out.println(objectMySingleLinkedQueue.toString());4 总结

本文介绍了队列的基本概念，并且提供了简单的实现，队列属于一种特殊的线性表。“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛，实际上我们能够直接接触到的队列的应用是要高于栈的应用的，比如各种并发队列，消息队列。另外在广度优先搜索算法中，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

另外，关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

作者：刘Java