文章目錄
隊列（Queue）是一種經常使用的集合。Queue實際上是實作了一個先進先出（FIFO：First In First Out）的有序表。它和List的差別在于，List可以在任意位置添加和删除元素，而Queue隻有兩個操作：
- 把元素添加到隊列末尾；
- 從隊列頭部取出元素。
超市的收銀台就是一個隊列：
Queue 用于模拟隊列這種資料結構。
Queue 接口中定義了如下幾個方法 。
- void add(Object e): 将指定元素加入此隊列 的 尾部。
- Object element() : 擷取隊列頭部的元素 ， 但是不删除該元素 。
- boolean offer(Object e) : 将指定元素加入此隊列的尾部。當使用有容量限制的隊列時， 此方法通常比add(Object e)方法更好 。
- Object peek(): 擷取隊列頭部的元素 ， 但是不删除該元素 。 如果此隊列為空，則傳回 null 。
- Object poll() : 擷取隊列頭部的元素 ， 并删除該元素。如果此隊列為空 ， 則傳回 null 。
- Object remove() : 擷取隊列頭部的元素 ， 并删除該元素 。
API: java.util.Queue
PriorityQueue 是 一個比較标準的隊列實作類。之是以說它是比較标準的隊列實作 ， 而不是絕對标準的隊列實作 ， 是因為 PriorityQueue 儲存隊列元的順序并不是按加入隊列的順序，而是按隊列元素的大小進行重新排序 。 是以當調用 peek()方法或者 poll()方法取出隊列中的元素時，并不是取出最先進入隊列的元素 ， 而是取出隊列中最小 的元素。從這個意義上來看 ， PriorityQueue 己經違反了隊列的最基本規則: 先進先出 （ FIFO ) 。
下面程式示範了 PriorityQueue 隊列的用法:
PriorityQueueTest.java
public class PriorityQueueTest
{
public static void main(String[] args)
{
PriorityQueue pq = new PriorityQueue();
// 下面代碼依次向pq中加入四個元素
pq.offer(6);
pq.offer(-3);
pq.offer(20);
pq.offer(18);
// 輸出pq隊列，并不是按元素的加入順序排列
System.out.println(pq); // 輸出[-3, 6, 20, 18]
// 通路隊列第一個元素，其實就是隊列中最小的元素：-3
System.out.println(pq.poll());
}
} Prio rityQueue 不允許插入 null 元素，它還需要對隊列元素進行排序 ， PriorityQueue 的元素有兩種排序方式 :
- 自然排序 : 采用自然順序的 PriorityQueue 集合中的元素必須實作Comparable 接口，而且應該是同 一個類的多個執行個體 ， 否則可能導緻 ClassCastException 異常 。
- 定制排序 : 建立 PriorityQueue 隊列 時， 傳入一個 Comparator 對象 ， 該對象負責對隊列中的所有元素進行排序 。 采用定制排序時不要求隊列元素實作Comparable 接口 。
PriortyQueue 隊列對元素的要求與 TreeSet 對元素的要求基本一緻。
java.util.PriorityQueue
Deque 接口是 Queue 接口的子接口 ， 它代表一個雙端隊列， Deque 接口裡定義了 一些雙端隊列的方法，這些方法允許從兩端來操作隊列的元素。
- void addFirst(Object e): 将指定元素插入該雙端隊列的開頭 。
- void addLast(Object e): 将指定元素插入該雙端隊列的末尾 。
-
Iterator descendingIterator(): 傳回該雙端隊列對應的疊代器，該法代器将以逆向順序來法代隊列
中的元素 。
- Object getFirst(): 擷取但不删除雙端隊列的第 一個元素 。
- Object getLast(): 擷取但不删除雙端隊列的最後 一個元素 。
- boolean offerFirst(Object e): 将指定元素插入該雙端隊列的開頭 。
- boolean offerLast(Object e): 将指定元素插入該雙端隊列的末尾 。
- Object peekFirst(): 擷取但不删除該雙端隊列的第 一個元素:如果此雙端隊列為 空 ，則傳回 null 。
- Object peekLast(): 擷取但不删除該雙端隊列的最後 一個元素:如果此雙端隊列為空，則傳回 null 。
- Object pollFirst(): 擷取并删除該雙端隊列的第 一個元素;如果此雙端隊列為空，則傳回 null 。
- Object pollLast() : 擷取并删除該雙端隊列的最後 一個元素;如果此雙端隊列為空，則傳回 null 。
- Object pop() (棧方法) : pop 出該雙端隊列所表示的校的技頂元素 。 相當于 removeFirstO 。
- void push(Object e) (棧方法) : 将 一 個元素 push 進該雙端隊列所表示的攏的技頂 。 相當于addFirst(e) 。
- Object removeFirst（）: 擷取并删除該雙端隊列的第一個元素 。
- Object removeFirstOccurrence(Object o): 删除該雙端隊列的第一次出現的元素 。
- Object removeLast（）: 擷取并删除該雙端隊列的最後一個元素 。
- boolean removeLastOccurrence(Object o): 删除該雙端隊列的最後一次出現的元素。
Deque 不僅可以 當成雙端隊列使用，而且可以被當成棧來使用，因為該類
裡還包含了 pop ( 出棧)、 push (入棧)兩個方法 。
Deque 的方法與 Queue 的方法對照表
Deque 的方法與 Stack 的方法對照表
java.util.Deque
Deque 接口提供了 一個典型的實作類: ArrayDeque ，從該名稱就可以看出 ， 它是一個基于數組實作的雙端隊列，建立 Deque 時同樣可指定一個 numElements 參數 ， 該參數用于指定 Object[]數組的長度 :如果不指定 numElements 參數， Deque 底層數組的長度為 16 。
ArrayList 和 ArrayDeque 兩個集合類的實作機制基本相似，它們的底層都采用一個動态的、可重配置設定的 Object[]數紐來存儲集合元素，當集合元素超出了該數組的容量時，系統會在底層重新配置設定一個 Object[]數組來存儲集合元素 。
下面程式示範了把 ArrayDeque 當成"棧"來使用 :
ArrayDequeStack.java
public class ArrayDequeStack
{
public static void main(String[] args)
{
ArrayDeque stack = new ArrayDeque();
// 依次将三個元素push入"棧"
stack.push("瘋狂Java講義");
stack.push("輕量級Java EE企業應用實戰");
stack.push("瘋狂Android講義");
// 輸出：[瘋狂Android講義, 輕量級Java EE企業應用實戰, 瘋狂Java講義]
System.out.println(stack);
// 通路第一個元素，但并不将其pop出"棧"，輸出：瘋狂Android講義
System.out.println(stack.peek());
// 依然輸出：[瘋狂Android講義, 瘋狂Java講義, 輕量級Java EE企業應用實戰]
System.out.println(stack);
// pop出第一個元素，輸出：瘋狂Android講義
System.out.println(stack.pop());
// 輸出：[輕量級Java EE企業應用實戰, 瘋狂Java講義]
System.out.println(stack);
}
} ArrayDeque也可以當成隊列使用，此處 AπayDeque 将按"先進先出"的方式操作集合元素。例如如下程式 ：
ArrayDequeQueue.java
public class ArrayDequeQueue
{
public static void main(String[] args)
{
ArrayDeque queue = new ArrayDeque();
// 依次将三個元素加入隊列
queue.offer("瘋狂Java講義");
queue.offer("輕量級Java EE企業應用實戰");
queue.offer("瘋狂Android講義");
// 輸出：[瘋狂Java講義, 輕量級Java EE企業應用實戰, 瘋狂Android講義]
System.out.println(queue);
// 通路隊列頭部的元素，但并不将其poll出隊列"棧"，輸出：瘋狂Java講義
System.out.println(queue.peek());
// 依然輸出：[瘋狂Java講義, 輕量級Java EE企業應用實戰, 瘋狂Android講義]
System.out.println(queue);
// poll出第一個元素，輸出：瘋狂Java講義
System.out.println(queue.poll());
// 輸出：[輕量級Java EE企業應用實戰, 瘋狂Android講義]
System.out.println(queue);
}
} LinkedList 也實作了 Deque 接口，可以被當成雙端隊列來使用，是以既可以被當成"棧"來使用 ，也可以當成隊列使用 。
java.util.ArrayDeque
Java 提供的 List 就是一個線性表接口，而ArrayList、LinkedList 又是線性表的兩種典型實作 : 基于數組的線性表和基于鍊的線性表。 Queue 代表了隊列， Deque 代表了雙端隊列(既可作為隊列使用， 也可作為棧使用) 。
一般來說，
- 由于數組以一塊連續記憶體區來儲存所有的數組元素，是以數組在随機通路時性能最好，所有的内部以數組作為底層實作的集合在随機通路時性能都比較好;
- 而内部以連結清單作為底層實作的集合在執行插入、删除操作時有較好的性能 。
但總體來說， ArrayList 的性能比 LinkedList 的性能要好 ， 是以大部分時候都應該考慮使用ArrayList。
關于使用 List 集合有如下建議：
- 如果需要周遊 List 集合元素，對于 ArrayList 、 Vector 集合，應該使用随機通路方法 (get) 來周遊集合元素，這樣性能更好;對于 LinkedList 集合 ，則應該采用法代器 (Iterator ) 來周遊集合元素。
- 如果 需要經常執行插入、删除操作來改變包含大量資料的 List 集合的大小,可考慮使用LinkedList 集合 。 使用 ArrayList 、 Vector 集合可能需要經常重新配置設定内部數組的大小， 效果可能較差 。
- 如果有多個線程需要同時訪 問 List 集合中的元素，開發者可考慮使用 Collections 将集合包裝成線程安全的集合 。
參考：
【1】：《瘋狂Java講義》
【2】：
廖雪峰的官方網站：使用Queue【3】：
廖雪峰的官方網站：使用PriorityQueue【4】：
廖雪峰的官方網站：使用Deque