程少为看皮肤病好吗 http://m.39.net/pf/a_8498648.htmlHello大家好，好久不见，我是最近写了好多bug的八哥。之前和大家分享了面试常用数据结构中的基础，数组与链表。如果还没有阅读的话，快点击下面的图片阅读复习一下吧。
今天我们来讲一下线性数据结构中的『队列』，来看看数组和链表在数据结构中的应用。
什么是队列？
队列Queue这种数据结构其实来源于我们生活中，排队上车，排队买饭，先来先买，后来的就乖乖在队尾等着。因此FirstInFirstOut(FIFO)是队列最重要的特点，很形象生动地概括了队列的特点。
队列不同于数组和链表这两种基础的数据结构，队列更多是一种逻辑上的数据结构，也就是说队列是通过基础数据结构进行实现的。也因此一般Queue会有链表和数组两种实现方式，以应对于不同的用途。
Queue
图源：Wikipedia
同时队列在实际productionsystem中也是非常重要的一种中间件，『消息队列』MessageQueue也是Queue很重要的一种应用。只不过是对于Queue这种数据结构，我们通过primitive的数组和链表实现，对于MessageQueue我们就需要更复杂的内部实现了。
Queue的实现
前面我们说过，Queue不是一种primitive的数据结构，依赖于其他数据结构进行实现，而且都属于线性数据结构。队列的实现一般有两种，即数组和链表。
在Java中也默认有两种impelmentation：
ArrayDequeLinkedList
其中ArrayDeque是基于数组进行实现，这两种实现最大的区别就是，能否存null元素。其中ArrayDeque不允许存储null：
链表
对于LinkedList实现队列，比较容易实现。只要我们明确头和尾即可。每次操作时在链表尾部插入新元素来实现入队：
链表实现入队操作
对于出队，在链表头部删除元素更新head指针，即可完成操作。
链表实现出队操作数组
对于数组实现队列，一般是一个固定capacity的队列，因此可以用一个定长的数组进行实现，维护一个head和tail指针即可：
offer():在tail处添加新元素并tail++poll():在head处get新元素并head++数组通过指针实现队列
这样会产生一个问题，如果对于一个数组我们最终head和tail指针都靠近数组尾部时，之前poll出去的部分存储空间仍然存储着原来本应该被删除的元素，就浪费了很多存储空间存储无用的数据：
数组队列的无用空间
因此为了优化空间，我们会使用CircularArray将数组的首尾连接起来，从而有效利用原来的空间：
CircularArrayJava中的Queue
在讨论了Queue的实现之后，我们来看一下实际使用中Java里的Queue是什么样子的，以及API如何使用。在Java中对于队列，我们一般有两种接口，Queue和Deque。
Queue
根据我们前面的讨论，最基本的队列需要支持的操作就是『入队』和『出队』，也因此Queue这种数据结构最重要的API一般就是以下三种：
offer():在队尾添加新的元素，入队开始排队poll():从队头取出第一个元素peek():看一眼队头的第一个元素是什么Deque
Deque是一种高级一点的队列，双端队列。顾名思义，就是在两头都可以入队和出队，因此API就翻了一倍：
offerFirst()offerLast():在队头或队尾入队pollFirst()pollLast():在队头或队尾出队peekFirst()peekLast():看一眼队头或队尾
双端队列比普通队列多了更多的功能，因此可以看到Queue就是一种特殊的Deque，只要我们在Deque中规定了入队和出队的位置，就只是一个普通的队列。
API比较
在Oracle的官方Java文档中对于Queue和Deque两种接口的API有详细讨论，官方提供了两套API：
returnnull：对于空队列的情况，会返回异常值nullthrowexception：设计时默认队列任何时候都不应该为空，对于空队列会报错抛出异常
对于Queue来说，两套API的区别如下：
QueueAPI
Ref:
