Java Collection - Stack & Queue & Deque

概述

Java里有一个叫做Stack的类，却没有叫做Queue的类(它是个接口名字)。

当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；
既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了(次选是LinkedList)。

为什么Stack被弃用
Java 中的 Stack 实现，是被业界一直认为非常糟糕的实现。
实际上，它犯了面向对象设计领域的一个基本错误：Stack 和 Vector 之间的关系，不应该是继承关系，而应该是组合关系（composition）。

Queue

Queue接口继承自Collection接口，除了最基本的Collection的方法之外，它还支持额外的insertion, extraction和inspection操作。
这里有两组格式，共6个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Deque

Deque是”double ended queue”，表示双向的队列，英文读作”deck”。
Deque 继承自 Queue接口，除了支持Queue的方法之外，还支持insert，remove和examine操作。
由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。

	First Element - Head		Last Element - Tail
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

ArrayDeque

ArrayDeque和LinkedList是Deque的两个通用实现，官方更推荐使用AarryDeque用作栈和队列。

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。
ArrayDeque是非线程安全的(not thread-safe)，当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。

head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。