0.前言
在資料結構與算法中，隊列是被經常使用的一種資料結構，總體上構成較為簡單，但是Java在實際使用時易用錯，經常會。比如 poll() 方法，add() 方法，offer() 方法，addFirst()方法，removeFirst()方法，removeLast() 方法，它們之間的對應關系是怎麼樣的，Queue和Deque使用和功能有何不同？本文主要探究這些問題。
1.隊列這種資料結構
作為一種經典的資料結構，棧承擔了先進後出的責任，而在先進先出這方面，則由隊列來完成。隊列有單向隊列，即最經典的隊列，一頭進，另一頭出，而雙端隊列，兩端都可以進出，比較靈活，是以造成了雙端隊列的api較多，在實際使用中經常會搞錯方向。
還有就是隊列的頭尾問題，分不清很容易在雙端隊列的removeFirst()方法或者是removeLast()方法中混淆。隊列中的元素從哪邊出去就是隊列頭，雙端隊列中兩邊都可以出去，但是沿着元素進入的方向能走出隊列的一端為頭。
需要注意的是，隊列是操作受限的線性表，是以，不是任何對線性表的操作都可以作為隊列的操作。比如，不可以随便讀取隊列中間的某個資料。【3】
關于隊列的結構還可參考這篇文章，有助于了解：
棧和隊列互相實作 (用隊列實作棧/用棧實作隊列) 超詳細~
2.Java Queue
在Java中，Queue是隊列的接口，主要的方法有6個，比較簡單。常用的實作類有兩個：LinkedList<>()和ArrayDeque<>()。
官方文檔：
1.add() 方法
添加元素到隊尾
2.element()方法
檢視隊首元素
3.offer()方法
添加元素到隊尾，和add()作用相同。隊列有大小限制，在一個滿的隊列中加入一個新項，調用 add() 方法就會抛出一個 unchecked 異常，而調用 offer() 方法會傳回 false，是以就可以在程式中進行有效的判斷。【1】
4.peek()方法
檢視隊首元素，和peek()相同。隊列為空， element()方法會抛出一個異常，peek() 傳回 null。
5.poll()方法
删除隊首元素
6.remove()方法
删除隊首元素，和poll()方法相同。如果隊列元素為空，調用remove()會出現異常，而 poll() 方法傳回null。
7.其他方法
其他還有isEmpty()方法檢視是否為空，size()方法檢視隊列長度等。
8.案例解析
可參考【3】
3.Java Deque
雙端隊列的接口是Deque，和Queue一樣，常見的實作的類都是LinkedList<>()和ArrayDeque<>()，因為兩邊都可以插入、删除元素，是以方法比較多。
1.插入元素
add() 添加元素到隊尾,空間不足報異常，成功傳回true。
addFirst() 添加元素到隊頭，空間不足報異常。
offerFirst() 添加元素到隊頭，成功傳回true，否則傳回false。
addLast() 添加元素到隊尾，空間不足報異常。
offerLast() 添加元素到隊尾，成功傳回true，否則傳回false。
push() 添加元素到隊頭，此處承擔棧的作用，等價于addFirst()，空間不足報異常。
2.删除元素
remove() 删除頭元素
removeFirst() 删除頭元素，為空報異常。
removeLast() 删除尾元素，為空報異常。
pollFirst() 删除頭元素，為空傳回null。
pollLast() 删除尾元素，為空傳回null。
pop() 删除頭元素，此處承擔棧的作用，等價于removeFirst()，為空報異常。
3.檢視元素
getFirst() 檢視頭元素，為空報異常。
getLast() 檢視尾元素，為空報異常。
peekFirst() 檢視頭元素，為空傳回null。
peekLast() 檢視尾元素，為空傳回null。
4.案例示範
可參考【2】
4.辨析
在整體上，Queue可以看作是Deque的子集，Queue有的功能Deque都有，因為是雙端隊列，兩邊都可以插入和删除，是以Deque要比Queue更靈活，在有些題目中，會出現必須要雙端隊列的情況，因為兩邊都需要删除，而Queue做不到這一點。
還有，在一些題目中，會要求隻能用隊列，不能使用雙端隊列，需要注意。另外，由于雙端隊列可以先進後出，也可以當作棧來使用，例如經典的問題，使用隊列實作棧，可以用一個雙端隊列實作，也可以用兩個隊列實作。
等效方法【1】：
5.leetcodde案例
1. leetcode225 用隊列實作棧
請你僅使用兩個隊列實作一個後入先出（LIFO）的棧，并支援普通棧的全部四種操作（push、top、pop 和 empty）。
實作 MyStack 類：
void push(int x) 将元素 x 壓入棧頂。
int pop() 移除并傳回棧頂元素。
int top() 傳回棧頂元素。
boolean empty() 如果棧是空的，傳回 true ；否則，傳回 false 。
注意：
你隻能使用隊列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。你所使用的語言也許不支援隊列。 你可以使用 list （清單）或者 deque（雙端隊列）來模拟一個隊列 , 隻要是标準的隊列操作即可。
class MyStack {
Deque<Integer> list1;
Deque<Integer> list2;
public MyStack() {
list1 = new ArrayDeque<>();
list2 = new ArrayDeque<>();
}
public void push(int x) {
list2.add(x);
while(!list1.isEmpty()){
list2.add(list1.remove());//add poll
}
Deque<Integer> temp = list1;
list1 = list2;
list2 = temp;
}
public int pop() {
return list1.remove();
}
public int top() {
return list1.peek();
}
public boolean empty() {
return list1.isEmpty();
}
}
本題小結
（1）一個主隊列，一個輔助隊列，主隊列時刻保持最新狀态
（2）主隊列保持最新就意味着(top/Empty/pop)等操作都對最新的隊列即主隊列操作
（3）來一個新的元素放到輔助隊列，然後把主隊列的元素都丢到輔助隊列，交換即最新
以題中的案例為例，畫出主輔隊列的變化：
輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]
解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 傳回 2
myStack.pop(); // 傳回 2
myStack.empty(); // 傳回 False
此題目也可以使用一個雙端隊列來實作
可見另一篇文章：
棧和隊列互相實作 (用隊列實作棧/用棧實作隊列) 超詳細~
2. leetcode232 用棧實作隊列
可見這篇文章，比較詳細 棧和隊列互相實作 (用隊列實作棧/用棧實作隊列) 超詳細~
3. leetcode102 二叉樹的層序周遊
給你二叉樹的根節點 root ，傳回其節點值的 層序周遊 。 （即逐層地，從左到右通路所有節點）。
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
if(root == null) return list;
queue.addLast(root);
while(!queue.isEmpty()){
int len = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i = 0; i < len; i++){
TreeNode cur = queue.pollFirst();
temp.add(cur.val);
if(cur.left != null){
queue.addLast(cur.left);
}
if(cur.right != null){
queue.addLast(cur.right);
}
}
list.add(temp);
}
return list;
}
}
詳細解析：
Java-資料結構-二叉樹＜三＞
4.leetcode 面試題59 - II. 隊列的最大值
請定義一個隊列并實作函數 max_value 得到隊列裡的最大值，要求函數max_value、push_back 和 pop_front 的均攤時間複雜度都是O(1)。
若隊列為空，pop_front 和 max_value 需要傳回 -1
輸入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
輸出: [null,null,null,2,1,2]
class MaxQueue {
Deque<Integer> deque1;
Deque<Integer> deque2;
public MaxQueue() {
deque1 = new LinkedList<>();
deque2 = new LinkedList<>();
}
public int max_value() {
if(deque2.isEmpty()) return -1;
return deque2.peekFirst();
}
public void push_back(int value) {
deque1.addLast(value);
while(!deque2.isEmpty() && value > deque2.peekLast()){
deque2.removeLast();
}
deque2.addLast(value);
}
public int pop_front() {
if(deque1.isEmpty()){
return -1;
}
if(deque1.peekFirst().equals(deque2.peekFirst())){
deque2.removeFirst();
return deque1.removeFirst();
}
return deque1.removeFirst();
}
}
本題小結
（1）一個主隊列，一個輔助隊列，主隊列存所有的元素，而輔助隊列隻存最大值
（2）一個新的隊列元素來到之後，放到主隊列，而在輔助隊列中，要依次比較新值和輔助隊列中的值
（3）在去除元素時，要注意輔助隊列和主隊列元素是否一緻，主隊列的元素一直比輔助隊列多，因為輔助隊列隻儲存最大值
6.參考來源
【1】CSDN Jason&Zhou Java資料結構之Deque(雙端隊列)
【2】CSDN onedegree java關于Deque的使用
【3】CSDN Sueko Java中隊列（Queue)用法
【4】Leetcode Krahets(K神) 劍指 Offer 59 - II. 隊列的最大值（單調雙向隊列，清晰圖解）