数据结构——Queue 队列

循环队列

rear = (rear - size) % size

接着上面的例子，当 rear 大于 队列长度时，rear = ( 5 - 5) % 5 = 0 :

这样继续添加时，还可以添加几个元素：

那如何判断队列是否装满元素了呢，单使用 front == rear 无法判断究竟是空的还是满了。

有两种方法处理上述问题：

1. 另设一个标志位以区别队列是空还是满。
2. 少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即： (rear + 1) % maxsize = front

接着上面的情况，当 rear 从后面添加元素跑到前面 0 时，再添加一个元素 a6，rear 后移一位到 1，这时 front = 2，用上面公式计算 (1 + 1) % 5 = 2, 满足放满条件。

Java 中的队列 Queue

Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都

实现了它。

Queue 用来存放 等待处理元素的集合，这种场景一般用于缓冲、并发访问。

除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。

添加、删除、查询这些个操作都提供了两种形式，其中一种在操作失败时直接抛出异常，而另一种则返回一个特殊的值：

Queue 方法介绍：

1. add(E), offer(E) 在尾部添加:

booleanadd(Ee);

booleanoffer(Ee);

共同之处：

• 是建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；

不同之处：

• 在于 add() 方法在添加失败（比如队列已满）时会报 一些运行时错误 错；
• 而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。

注意：

• Queue 是个接口，它提供的 add, offer 方法初衷是希望子类能够禁止添加元素为 null，这样可以避免在查询时返回 null 究竟是正确还是错误。
• 事实上大多数 Queue 的实现类的确响应了 Queue 接口的规定但还是有一些实现类没有这样要求，比如 LinkedList。

1. remove(), poll() 删除并返回头部：

Eremove();

Epoll();

当队列为空时 remove() 方法会报 NoSuchElementException 错;

而 poll() 不会奔溃，只会返回 null。

1. element(), peek() 获取但不删除

Eelement();

Epeek();

当队列为空时 element() 抛出异常；peek() 不会奔溃，只会返回 null。

补充

1. 虽然 LinkedList 没有禁止添加 null，但是一般情况下 Queue 的实现类都不允许添加 null 元素，为啥呢？因为 poll(), peek() 方法在异常的时候会返回 null，你添加了 null 以后，当获取时不好分辨究竟是否正确返回。
2. Queue 一般都是 FIFO 的，但是也有例外，比如优先队列 priority queue（它的顺序是根据自然排序或者自定义 comparator 的）；再比如 LIFO 的队列（跟栈一样，后来进去的先出去）。不论进入、出去的先后顺序是怎样的，使用 remove()，poll() 方法操作的都是 头部 的元素；而插入的位置则不一定是在队尾了，不同的 queue 会有不同的插入逻辑。

队列的抽象数据类型

队列同样是一种特殊的线性表，其插入和删除的操作分别在表的两端进行，队列的特点就是先进先出(First In First Out)。我们把向队列中插入元素的过程称为入队(Enqueue)，删除元素的过程称为出队(Dequeue)并把允许入队的一端称为队尾，允许出的的一端称为队头，没有任何元素的队列则称为空队。其一般结构如下：

关于队列的操作，我们这里主要实现入队，出队，判断空队列和清空队列等操作，声明队列接口Queue（队列抽象数据类型）如下：

publicinterfaceQueue<T> {

  /**
   * 返回队列长度
   * @return
   */
  intsize();

  /**
   * 判断队列是否为空
   * @return
   */
  booleanisEmpty();

  /**
   * data 入队,添加成功返回true,否则返回false,可扩容
   * @param data
   * @return
   */
  booleanadd(Tdata);

  /**
   * offer 方法可插入一个元素,这与add 方法不同，
   * 该方法只能通过抛出未经检查的异常使添加元素失败。
   * 而不是出现异常的情况，例如在容量固定（有界）的队列中
   * NullPointerException:data==null时抛出
   * @param data
   * @return
   */
  booleanoffer(Tdata);

  /**
   * 返回队头元素,不执行删除操作,若队列为空,返回null
   * @return
   */
  Tpeek();

  /**
   * 返回队头元素,不执行删除操作,若队列为空,抛出异常:NoSuchElementException
   * @return
   */
  Telement();

  /**
   * 出队,执行删除操作,返回队头元素,若队列为空,返回null
   * @return
   */
  Tpoll();

  /**
   * 出队,执行删除操作,若队列为空,抛出异常:NoSuchElementException
   * @return
   */
  Tremove();

  /**
   * 清空队列
   */
  voidclearQueue();
}

顺序队列的设计与实现

关于顺序队列（底层都是利用数组作为容器）的实现，我们将采用顺序循环队列的结构来实现，在给出实现方案前先来分析一下为什么不直接使用顺序表作为底层容器来实现。实际上采用顺序表实现队列时，入队操作直接执行顺序表尾部插入操作，其时间复杂度为O(1)，出队操作直接执行顺序表头部删除操作，其时间复杂度为O(n)，主要用于移动元素，效率低，既然如此，我们就把出队的时间复杂度降为O(1)即可，为此在顺序表中添加一个头指向下标front和尾指向下标，出队和入队时只要改变front、rear的下标指向取值即可，此时无需移动元素，因此出队的时间复杂度也就变为O(1)。其过程如下图所示

从图的演示过程，（a）操作时，是空队列此时front和rear都为-1，同时可以发现虽然我们通过给顺序表添加front和rear变量记录下标后使用得出队操作的时间复杂度降为O(1)，但是却出现了另外一个严重的问题，那就是空间浪费，从图中的（d）和（e）操作可以发现，20和30出队后，遗留下来的空间并没有被重新利用，反而是空着，所以导致执行（f）操作时，出现队列已满的假现象，这种假现象我们称之为假溢出，之所以出现这样假溢出的现象是因为顺序表队列的存储单元没有重复利用机制，而解决该问题的最合适的方式就是将顺序队列设计为循环结构，接下来我们就通过循环顺序表来实现顺序队列。

顺序循环队列就是将顺序队列设计为在逻辑结构上收尾相接的循环结构，这样我们就可以重复利用存储单元，其过程如下所示：

其中采用循环结构的顺序表，可以循环利用存储单元，因此有如下计算关系(其中size为队列长度)：

//其中front、rear的下标的取值范围是0~size-1，不会造成假溢出。
front= (front+1) %size;//队头下标
rear= (rear+1) %size;

1. front为队头元素的下标，rear则指向下一个入队元素的下标
2. 当front=rear时，我们约定队列为空。
3. 出队操作改变front下标指向，入队操作改变rear下标指向，size代表队列容量。
4. 约定队列满的条件为front=(rear+1)%size,注意此时队列中仍有一个空的位置，此处留一个空位主要用于避免与队列空的条件front=rear相同。
5. 队列内部的数组可扩容，并按照原来队列的次序复制元素数组了解了队列的实现规则后，我们重点分析一下入队add方法和出队poll方法，其中入队add方法实现如下：

/**
 * data 入队,添加成功返回true,否则返回false,可扩容
 * @param data
 * @return
 */
@Override
publicbooleanadd(Tdata) {
    //判断是否满队
    if (this.front==(this.rear+1)%this.elementData.length){
        ensureCapacity(elementData.length*2+1);
    }
    //添加data
    elementData[this.rear]=data;
    //更新rear指向下一个空元素的位置
    this.rear=(this.rear+1)%elementData.length;
    size++;
    returntrue;
}

在add方法中我们先通过this.front==(this.rear+1)%this.elementData.length判断队列是否满，在前面我们约定过队列满的条件为front=(rear+1)%size,如果队列满，则先通过ensureCapacity(elementData.length*2+1)扩容，该方法实现如下：

/**
 * 扩容的方法
 * @param capacity
 */
publicvoidensureCapacity(intcapacity) {
    //如果需要拓展的容量比现在数组的容量还小,则无需扩容
    if (capacity<size)
        return;

    T[] old=elementData;
    elementData= (T[]) newObject[capacity];
    intj=0;
    //复制元素
    for (inti=this.front; i!=this.rear ; i=(i+1)%old.length) {
        elementData[j++] =old[i];
    }
    //恢复front,rear指向
    this.front=0;
    this.rear=j;
}

这个方法比较简单，主要创建一个新容量的数组，并把旧数组中的元素复制到新的数组中，这里唯一的要注意的是，判断久数组是否复制完成的条件为i!=this.rear，同时循环的自增条件为i=(i+1)%old.length。扩容后直接通过rear添加新元素，最后更新rear指向下一个入队新元素。对于出队操作poll的实现如下：

/**
* 出队,执行删除操作,返回队头元素,若队列为空,返回null
* @return
*/
@Override
publicTpoll() {
   Ttemp=this.elementData[this.front];
   this.front=(this.front+1)%this.elementData.length;
   size--;
   returntemp;
}

链式队列的设计与实现

对于链式队列，将使用带头指针front和尾指针rear的单链表实现，front直接指向队头的第一个元素，rear指向队尾的最后一个元素，其结构如下：

之所以选择单链表（带头尾指针）而不采用循环双链表或者双链表主要是双链表的空间开销（空间复杂度，多前继指针）相对单链表来说大了不少，而单链表只要新增头指针和尾指针就可以轻松实现常数时间内（时间复杂度为O(1)）访问头尾结点。下面我们来看看如何设计链式队列：

1. 以上述的图为例分别设置front和rear指向队头结点和队尾结点，使用单链表的头尾访问时间复杂度为O(1)。
2. 设置初始化空队列，使用front=rear=null，并且约定条件front==null&&rear==null成立时，队列为空。
3. 出队操作时，若队列不为空获取队头结点元素，并删除队头结点元素，更新front指针的指向为front=front.next
4. 入队操作时，使插入元素的结点在rear之后并更新rear指针指向新插入元素。
5. 当第一个元素入队或者最后一个元素出队时，同时更新front指针和rear指针的指向。这一系列过程如下图所示：

队列应用的简单举例

1. 模拟现实世界中的队列，如售票柜台的队列以及其他先到先服务的场景。
2. 计算客户在呼叫中心等待的时间。
3. 异步数据的传输（文件输入输出、管道、嵌套字）。
4. 操作系统中的优先级任务执行。
5. 短信群体发送 应用的发布订阅模式