Java容器之队列Qeque

  队列是一种数据结构，遵循FIFO(先进先出)原则的一种数据结构，简单的讲先放到队列里的元素，先出队列，跟现实生活中的排队一样，队列的使用非常广泛和灵活，详细如下：

简介

  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈(Java容器之栈Stack)一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

顺序队列(单队列)

  建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

1.jpeg

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

顺序队列中的溢出现象：

1. "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
2. "真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
3. "假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

循环队列

  在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。还是上边的例子:
rear = (rear - size) % size
当 rear 大于 队列长度时，rear = ( 4 - 4) % 4 = 0 :如图：

2.jpeg

rear指针回到了0 的位置，这样可以继续添加一个元素,如图:

3.jpeg

那如何判断队列是否装满元素了呢，单使用 front == rear 无法判断究竟是空的还是满了。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。 如图:

4.jpeg

如图所示front=2, 根据公式 front = (1+1)%4 = 2; 此队列已满.
因此，当 rear > font 时，队列中元素个数 = rear - font;
当 rear < font 时，队列中元素分为两部分： size - font 和 rear ,也就是 rear + size - font。以上述图片为例，队列中元素个数 = 1 + 4 - 2 = 3。

Java中的Queue

  在Java中Queue是一个接口形式，它同List、Set属于同一级别，都是继承了Collection接口

下面是Queue接口的实现和继承

5.jpeg

Queue用来存放等待处理的元素的集合，这种场景一般用于缓存策略，并发访问等等，以下是Queue定义的一些除Collection额外的方法。

Queue 方法介绍

public interface Queue<E> extends Collection<E> {
    boolean add(E var1);

    boolean offer(E var1);

    E remove();

    E poll();

    E element();

    E peek();
}

添加、删除、和查询操作都提供两种不同的形式，其中一种形式是在操作失败的时候直接抛出异常，另一种形式则是返回一个特殊的值:

6.jpeg

add和offer在尾部添加方法

他们的共同之处是建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；
不同之处在于 add() 方法在添加失败（比如队列已满）时会报 一些运行时错误；而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。
Queue 是个接口，它提供的 add, offer 方法初衷是希望子类能够禁止添加元素为 null，这样可以避免在查询时返回 null 究竟是正确还是错误。
事实上大多数 Queue 的实现类的确响应了 Queue 接口的规定，比如 ArrayBlockingQueue，PriorityBlockingQueue 等等。
但还是有一些实现类没有这样要求，比如 LinkedList。

remove(), poll() 删除并返回头部方法

当队列为空时 remove() 方法会报 NoSuchElementException 异常; 而 poll() 不会奔溃，只会返回 null。

element(), peek() 获取但不删除方法

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

总结

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