資料結構中的隊列了解以下，"先進先出"是隊列的最大的特點，也就是隻能在頭部通路一個元素，在尾部添加一個元素。還有一種叫做雙端隊列。可以有效地在頭部和尾部同時添加或删除元 素。 不支援在隊列中間添加元素。
在 JDK6 中引人了 Deque 接口， 并由 ArrayDeque 和 LinkedList 類實作。這兩個類都提供了雙端隊列， 而且在必要時可以增加隊列的長度。在并發包下還提供了有限隊列和有限雙端隊列。
隊列接口Queue
首先看看在JDK中，隊列接口中都定義了哪些方法：
public interface Queue extends Collection {
// 繼承自Collection接口的方法，
// 在容量允許的情況下将元素放入隊列傳回true，空間不夠時抛出異常
boolean add(E e);
// 在容量允許的情況下插入元素，在容量限制時，優于add方法，空間不夠導緻添加失敗傳回false，
boolean offer(E e);
// 傳回并且删除隊列頭的元素，隊列為空抛出異常
E remove();
// 傳回并且删除隊列頭的元素，隊列為空傳回null
E poll();
傳回但不删除隊列頭的元素，隊列為空抛出異常
E element();
傳回但不删除隊列頭的元素，隊列為空傳回null
E peek();
}
雙端隊列接口Deque
public interface Deque extends Queue {
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
void push(E e);
E pop();
}
是不是很簡單，方法都是見名知意，而且還是成雙成對的出現，需要注意的系列差別就是為空時通路元素是抛出異常還是傳回null。
還有一些方法繼承自Queue接口和Collection接口：
數組實作的雙端隊列ArrayDeque
仍然先看ArrayDeque的繼承層次：
先看看ArrayDeque中定義的屬性和構造函數：
public class ArrayDeque extends AbstractCollection
implements Deque, Cloneable, Serializable {
transient Object[] elements;
transient int head;
transient int tail;
private static final int MIN_INITIAL_CAPACITY = 8;
// 預設構造16容量的數組建構隊列
public ArrayDeque() {
elements = new Object[16];
}
// 建構指定容量的隊列
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 根據别的集合建構隊列
public ArrayDeque(Collection extends E> c) {
allocateElements(c.size());
addAll(c);
}
}
從屬性中我們可以看出，ArrayDeque是基于循環數組實作的雙端隊列，預設構造的容量是16，最小也要保證8個容量，當我們使用指定數量的容量時，需要進行計算才能得到。那麼是怎麼計算的呢，需要遵循什麼原則：
// 根據别的集合建構隊列
public ArrayDeque(Collection extends E> c) {
allocateElements(c.size());
addAll(c);
}
// numElements 指定的容量大小
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
// 根據使用者傳入的計算允許的容量，并建立數組
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
// 為了計算得到比numElements大的最小2的n次幂
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY; // MIN_INITIAL_CAPACITY = 8
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
// 系列的移位、或操作，隻是為了得到大于numElements的最小2次幂
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
// 如果進過移為操作後，得到的結果第32位為1，1代表負數，那麼就需要回退一位。
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
還有一點就是添加元素的過程中，如果超出了數組的限制，那麼怎麼做的，其實和ArrayList一樣，動态的增加數組的容量：
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
将數組增加位原來的2倍，然後拷貝資料到新數組中
知道了ArrayDeque是基于循環數組的實作，那麼對于接口方法的實作就不列舉了，具體可以檢視API文檔。
連結清單實作的雙端隊列 LinkedList
優先隊列
優先隊列按照任意的順序将元素插入到隊列中，但是出隊的時候卻按照從小到大的順序取出，它使用的是一種高效的資料結構——堆(Heap),是一種自我調整的二叉樹。元素之間需要比較，是以插入的元素需要實作Comparable接口，當然，也可以在構造器中提供一個Compator。
它的繼承層次比較簡單，如下：
需要注意的是PriorityQueue并沒有實作Cloneable接口，也就是說它不能被克隆
PriorityQueue每次通路的總是隊列中最小的元素。
public class PriorityQueue extends AbstractQueue
implements java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private final Comparator super E> comparator;
}
基于數組實作，預設容量為11。當容量不夠的時候，如何增加數組的長度？
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
至此，JDK中常用的集合類就完畢了。