数据结构：Queue
Queue列队
1、Queue是典型的先进先出容器，FIFO（first-in-first-out），通俗点说就，这个容器就像一个管道，从一端放入从另一端取出，放入的顺序和取出的顺序是相同的。下面是在百度上搜索的一张图，很形象：
2、Queue是一个接口类，继承至Collection接口，与List、Set同属于Collection的子类Interface
3、Queue除了继承了Collection的接口外，自身拥有以下个接口：
add ：往列队中添加一个元索，如果队列已满，则抛出一个IIIegaISlabEepeplian异常
element：返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
offer：添加一个元素，成功返回true，如果队列已满，则返回false
peek：返回队列头部的元素，如果队列为空，则返回null
poll：移除并返回队列头部的元素，如果队列为空，则返回null
remove：移除并返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
3.1、个方法区别
offer & add区别
一些队列有大小限制，如果想在容量满了的队列中加入元素，会被拒绝。
offer()方法将一个元素插入队尾，成功返回true，失败返回false，一般在queue容量有限制并且满员的情况下会插入失败；
add()方法将一个元素插入队尾，queue容量如果满了，插入将会失败，失的时候会抛出异常；
peek & element区别
element() 和 peek() 都是在不移除元素的情况下返回列队头部元素。
在队列为空的情况下 peek() 返回 null，而element() 将抛出NoSuchElementException异常
poll & remove区别
remove() 和 poll() 方法都移除并返回队列头部元素（head）。
poll() 方法在集合为空的时候返回 null，remove() 则抛出NoSuchElementException异常
4、Queue的子类有4个
5、AbstractQueue:
一个抽象类，对Queue中的接口做了基本的实现
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E> {
/**
* Constructor for use by subclasses.
*/
protected AbstractQueue() {
}
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public void clear() {
while (poll() != null)
;
}
public boolean addAll(Collection<? extends E> c) {
if (c == null)
throw new NullPointerException();
if (c == this)
throw new IllegalArgumentException();
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
}AbstractQueue其拥有以下子类
6、BlockingQueue
接口，一个阻塞式的队列
1）检索元素时，如果队列为空，便阻塞等待，直到列队中有元素了再进行操作，
2）存储元素时，如果空间不够，阻塞等待直到有空间可以用
下面是该类各个接口的源码及解释
public interface BlockingQueue<E> extends Queue<E> {
/**
* 如果可以在不违反容量限制的情况下立即执行此操作，将指定的元素插入队列，成功时返回true，
* 如果当前没有空间，则抛出异常IllegalStateException。使用有限容量队列时，
* 通常最好使用offer
*/
boolean add(E e);
/**
* 如果可以在不违反容量限制的情况下立即执行此操作，则将指定的元素插入此队列，成功时返回true，
* 如果当前没有可用空间，则返回false。使用容量限制队列时，
* 此方法通常优于add，可能插入元素会失败，此时仅仅会抛出一个异常
*/
boolean offer(E e);
/**
* 往列队中插入指定元素，如果列队空间不够则等待空间可用
*/
void put(E e) throws InterruptedException;
/**
* 将指定的元素插入队列，如果空间不够，则等待指定的时间。
*
*/
boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
/**
* 检索并删除此队列的头部元素，如果没有可用元素，则阻塞等待，直到有元素可用。
*/
E take() throws InterruptedException;
/**
* 检索并删除此队列的头部元素，如果没有可用元素，则阻塞等待指定时间，指定时间内还是没有元素可用，则结束。
*/
E poll(long timeout, TimeUnit unit) throws InterruptedException;
/**
* 返回理想情况下此队列可以添加的元素的数量（在没有内存或资源限制的情况下）接受没有阻塞，或
* Integer.MAX_VALUE}，如果没有内在限制
*/
int remainingCapacity();
/**
*
* 从此队列中删除指定元素的单个实例，如果该实例存在。更确切地说，如果此队列包含一个或多个此元素，会通过
* o.equals（e）来进行比较，删除首先满足条件的元素，并会返回true，
*/
boolean remove(Object o);
/**
*
* 如果此队列包含指定的元素，则返回true，通过 o.equals（e）来进行比较
*
*/
boolean contains(Object o);
/**
* 从队列中移除所有可用元素，并将它们添加到指定集合中。此操作可能比重复轮询此队列更高效。
* 尝试向集合c添加元素时可能会失败，这将导致抛出关联的异常时元素丢失，元素既不在集合C中，也不在原列队集合中。
* 将队列自身元素排到自身会抛出IllegalArgumentException
* 此外，操作正在被修改的集合时，则此操作是不确定的
*/
int drainTo(Collection<? super E> c);
/**
* 与上面的重载方法不同的是，增加了一个最大元素的限制
*/
int drainTo(Collection<? super E> c, int maxElements);
}
7、Deque:
Deque是继承自Queue的一个Interface，deque 是双端队列，全名double-ended queue，是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行，也就是说，插入和删除操作只能在表的两端进行。双端列队看起来似乎比栈和队列更灵活，但实际在应用程序中远不及栈和队列有用。
7.1、Deque个方法的作用
增
void push(E) 向双端队列表示的栈中压入一个元素,失败时抛出异常IllegalStateException
void addFirst(E) 向双端队列头部插入一个指定元素,失败时抛出异常
void addLast(E) 向双端队列尾部插入一个元素,失败时抛出异常
boolean offerFirst(E) 向双端队列头部加入一个元素,失败时返回false
boolean offerLast(E) 向双端队列尾部加入一个元素,失败时返回false
删
E pop() 从双端队列表示的栈中弹出一个元素。换句话说，删除并返回此双端队列的第一个元素,队列为空时抛出异常
boolean removeFirstOccurrence(Object) 删除第一次出现的指定元素,不存在时返回false
boolean removeLastOccurrence(Object) 删除最后一次出现的指定元素,不存在时返回false
E removeFirst() 检索并移除队列头部元素,队列为空时抛出异常
E removeLast() 检索移除队列尾部元素,队列为空时抛出异常
E pollFirst() 检索移除队列头部元素,队列为空时返回null
E pollLast() 检索移除队列尾部元素,队列为空时返回null
查
E getFirst() 获取队列头部元素,队列为空时抛出异常
E getLast() 获取队列尾部元素,队列为空时抛出异常
E peekFirst() 获取队列头部元素,队列为空时返回null
E peekLast() 获取队列尾部元素,队列为空时返回null
迭代器
Iterator<E> descendingIterator() 返回队列反向迭代器
下面实在网上搜的一幅图来表示deque，比我自己画的要好
8、ConcurrentLinkedQueue
ConcurrentLinkedQueue是一个基于链接节点的*线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait－free”算法来实现
类结构图如下：
ConcurrentLinkedQueue由head节点和tail节点组成，每个Node节点由节点元素（item）和指向下一个节点的引用(next)组成，节点与节点之间就是通过这个next关联起来，从而组成一张链表结构的队列。默认情况下head节点存储的元素为空，tair节点等于head节点
public ConcurrentLinkedQueue() {
head = tail = newNode(null);
}
下面一片技术贴讲得很好：http://ifeve.com/concurrentlinkedqueue/
9、阻塞列队和非阻塞列队
阻塞队列（BlockingQueue）提供了可阻塞的put和take方法，它们与可定时的offer和poll是等价的。如果Queue已经满了，put方法会被阻塞直到有空间可用；如果Queue是空的，那么take方法会被阻塞，直到有元素可用。Queue的长度可以有限，也可以无限；无限的Queue永远不会充满，所以它的put方法永远不会阻塞。
阻塞队列（BlockingQueue）在队列容量达到上限，往列队里添加元素的操作会被阻塞；当队列为空，从队列中获取元素的操作将会被阻塞。试图往容量已满的阻塞队列中添加新元素的线程会被阻塞，直到有其他的线程使操作队列，让该队列有可用空间出现，即从该队列中移除元素一个、多个元素，或者清空队列。从空的阻塞队列中获取元素的线程将会被阻塞，直到有其他的线程往空的队列插入新的元素。
阻塞列队：
- ArrayBlockingQueue：基于数组的并发阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
- SynchronousQueue ：并发同步阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
- DelayQueue：延期阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
- LinkedBlockingQueue：基于链表的FIFO阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
- LinkedBlockingDeque：基于链表的FIFO双端阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
- PriorityBlockingQueue:：带优先级的*阻塞队列，继承自AbstractQueue，实现了BlockingQueue接口
非阻塞列队：
- ConcurrentLinkedQueue：基于链表的并发队列，继承自AbstractQueue，实现了Queue接口
- PriorityQueue：带优先级的*队列，继承自AbstractQueue，实现了BlockingQueue接口
- ArrayDeque,：数组双端队列，继承自AbstractCollection，实现了Deque接口