隊列 Queue 一個方向進，一個方向出

Queue隊列提供的核心方法：

入隊列：offer add

出隊列：poll remove

取隊首元素： peek element

前面一列發生錯誤是返回null? 后面一列發生錯誤時拋出異常

Queue是否能夠使用isEmpty()/size 等這樣的方法呢？

答案：是可以的，因為Queue接口繼承自Collection接口，而Collection接口實現了這一系列方法。

因此，判定隊列是否為空也就有了兩種表示方法：

        //判定隊列是否為空if(queue.peek()==null){}if(queue.isEmpty()){}

一、模擬實現隊列

package Queue;
//基于單鏈表實現的隊列
public class MyQueue {//鏈表的一個節點public class Node{public String val;public Node next;//提供構造方法public Node(String val) {this.val = val;this.next = null;}}//把隊列的頭部和尾部都記錄下來//基于倆表實現隊列//1.入隊—>尾插//2.出隊—>尾刪private Node head;private Node tail;//入隊public void offer(String val) {Node newNode = new Node(val);//考慮特殊情況 如果鏈表中沒有元素if(head== null){head = newNode;tail = newNode;return;}//一般情況tail.next = newNode;tail = newNode;}//出隊列public String poll(){//如果鏈表是空的if(head == null){return null;}//一般情況//保存頭部節點的值//接下來把這個節點刪除后，需要返回這個值String val = head.val;head = head.next;//如果鏈表的節點數目超出一個，刪掉一個元素，不影響tail的指向//但是，如果鏈表的節點數目只有一個，刪掉這個元素，此時tail就應該指向nullif(head.next== null){tail = null;}return  val;}//取隊首元素public String peek(){//如果鏈表是空的if(head == null){return null;}return head.val;}//判斷隊列是否為空public Boolean isEmpty(){return head == null;}//計算隊列的長度public int size(){int size = 0;for(Node cur = head;cur!= null;cur =cur.next){size++;}return size;}//一些測試public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer("a");queue.offer("b");queue.offer("c");queue.offer("d");queue.offer("e");System.out.println(queue.peek());System.out.println(queue.poll());System.out.println(queue.peek());System.out.println(queue.poll());}
}

二、數組實現隊列

        //這是一個基于數組的隊列Queue<Integer> queue1 = new ArrayDeque<>();//基于數組實現的雙端隊列

首先先創建一個數組new int[8]

和順序表設定類似，不是一上來這8個格子都被使用了，而是隨著后續入隊列逐漸使用。

由于是一個隊列，使用head下標記錄隊首位置，使用tail下標記錄隊尾元素的下一個位置。

初始情況下，head 和tail都指向0位置，此時認為是一個空的隊列。

隊列能入也能出，出隊列，得從head的位置進行考慮，如果是按照順序表頭刪的做法，此時就需要搬運大量的元素，實現隊列的效率就太低了。

所以這里的出隊列我們選擇用邏輯刪除：這里的刪除，不是真的把數據給改成別的，而是在邏輯上將其標記成無效。

此處也是往后移動head的位置，由于[head，tail)構成前閉后開開區間，當head++之后，之前head指向元素就被視為無效了。

當tail到達數組末尾，此時是否就意味著隊列滿了呢？并非。數組版本的隊列，就像是把數組彎過來，頭尾相接，構成了一個環。也就是“循環隊列”

如果在這個循環隊列中，隊列滿了怎么辦？有人說，可以通過head 和tail是否重合來判斷隊列是否滿了，但是最初隊列為空的時候，head和tail也是重合的。

如何區分上述隊列是空的還是滿的呢？

此時我們有兩種方案來解決這個問題：

方案一：直接浪費一個格子，當tail走到head的前一個位置的時候哦，就視為隊列滿了，確保再隊列滿的時候，tail就是head的前一個位置。隊列為空的時候，tail與head才重合。

方案二：引入一個size變量即可，size ==0 就是空 size = arr.length就是滿了

雖然隊列是有 基于鏈表 和 基于數組兩種風格，實際開發中，基于數組的方案是用的更多的。

數組這種方案的優點是什么呢？

1.擁有更高的效率：入隊列/出貨隊列就是簡單的head++ tail++ 執行速度更快。這時候就有人想問：“鏈表，不也就是修改一下引用的指向，時間復雜度也是(1)？為什么說基于數組的執行速度更快？”原因是：鏈表在進行訪問下一個元素的時候，需要多義詞間接尋址（先讀取引用的值，得到了地址，再根據地址找到對應內存空間）由此處我們可以知道，效率的高與低，運行速度的快和慢都是相對的。

2.對于隊列中元素個數的上限是可控的：對于鏈表版本來說，無限地往里面插入元素，只要你元素夠，就可以插入。但是如果你的代碼吹按bug了，不小心再入隊列，這里就會出現死循環。此時鏈表版本，不會直接報錯，而是把所有的內存都耗盡，導致嚴重的后果（比如整個程序癱瘓了）但是，如果是數組版本，并且不去自動擴容的話，如果出現類似的問題，后續就能夠再入隊列的時候及時報錯，把問題影響范圍縮小。

3.數組版本的隊列，內存使用率是更高的：鏈表版本，由于需要保存額外的next引用，導致內存的利用率更加低。

實現代碼：

package Queue;public class MyQueueByArray {//首先創建一個數組private String[] arr = null;//隊首private int head = 0;//隊尾private  int tail = 0;//隊列的元素個數private int size = 0;//來一個構造方法public MyQueueByArray(){arr = new String[1000];}//再來一個給定參數的構造方法public MyQueueByArray(int capacity){arr = new String[capacity];}//1.入隊列操作public void offer(String val){//如果隊列滿了 直接返回if(size == arr.length){return;}//把新的元素，放到tail的位置arr[tail] = val;//更新tail的指向tail++;if(tail == arr.length){tail =0;}//更新tail的指向，其實還有另外一種寫法//更推薦上面的寫法，而不是這里的 % 的寫法//tail=(tail+1)%arr.length;size++;}//2.出隊列操作public String poll(){//如果隊列為空，直接返回nullif(size ==0){return  null;}//取出隊首元素 保存起來 以便接下來返回值String elem = arr[head];head++;//更新head的指向并且進行判斷if(head == arr.length){head = 0;}size--;return elem;}//3.查看隊首元素public String peek(){if(size ==0){return  null;}return arr[head];}//4.判斷隊列是否為空public Boolean isEmpty(){return  size ==0;}//5.獲取隊列長度public int size(){return size;}//測試public static void main(String[] args) {MyQueueByArray myQueueByArray = new MyQueueByArray();myQueueByArray.offer("a");myQueueByArray.offer("b");myQueueByArray.offer("c");myQueueByArray.offer("d");System.out.println(myQueueByArray.peek());System.out.println(myQueueByArray.poll());System.out.println(myQueueByArray.poll());}
}

三、雙端隊列

雙端隊列，雖然是叫“隊列”，但他也能當作“棧”來使用，addLast搭配removeLast，相當于棧

addFirst 搭配 removeLast 相當于隊列

雙端隊列的實現：

public class Test2 {public static void main(String[] args) {//創建雙端隊列//Deque<Integer> deque = new ArrayDeque<>();Deque<Integer> deque = new LinkedList<>();//對于Queue提供的各種功能，deque也都是支持的//除此之外，Deque提供了其他的功能}
}

四、有關隊列的OJ題

實現思路：

1.準備兩個隊列A,B

2.入棧：先把A中的所有元素往B里面倒騰（A循環出隊列，把出來的元素，入隊列到B中）當A中就剩最后一個元素的時候，把這個元素當作棧的元素，刪除掉就可以了

當完成一次出棧，所有的元素都被倒騰到B這個隊列中了，此時就可以交換A和B的指向，后續如果再需要入棧操作，還是繼續往A中添加

4.取棧頂元素：和出棧類似，把A中的元素往B里倒騰，倒騰的過程中，當就剩一個元素的時候，把這個元素的值返回，接下來繼續把這個值添加到B中的，然后還是交換A和B

代碼段：

// 通過兩個隊列實現棧.
public class MyStack {private Queue<Integer> A = new LinkedList<>();private Queue<Integer> B = new LinkedList<>();public MyStack() {}private void swap() {Queue<Integer> tmp = A;A = B;B = tmp;}public void push(int x) {// 入棧的時候// 把 x 添加到隊列 A 中.A.offer(x);}public int pop() {// 出棧的時候// 判定一下是否為空if (empty()) {// 為空, 直接返回.return 0;}// 把 A 中的元素往 B 里面倒騰. 直到 A 中就剩最后一個元素的時候, 這個元素就可以被刪除了.// 循環結束, 就剩一個元素.while (A.size() > 1) {int n = A.poll();B.offer(n);}// 循環結束, 說明 A 中就剩一個元素了. 最后這個元素不能插入到 B 中.int ret = A.poll();// 交換 A 和 B.swap();return ret;}public int top() {if (empty()) {// OJ 題不能拋出異常. 并且也不能修改 返回值類型為 Integer 此時也無法返回 null. 只能返回 0.// 題目本身應該不會有棧為空再 top 的情況.return 0;}// 取棧頂元素, 也是把 A 的元素往 B 里倒騰.while (A.size() > 1) {int n = A.poll();B.offer(n);}// 取出最后一個元素int ret = A.poll();// 把最后一個元素添加到 B 中. (和 pop 相比, 就只是這里多了一行, 別的地方都一樣) .B.offer(ret);// 交換 A 和 B.swap();return ret;}public boolean empty() {// 會交換 A 和 B. 所以 B 始終為 空的 . 抓住 A 的空就可以判定整體的 空.return A.isEmpty();}}
/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

思路：創建兩個棧

1.入隊列：把所有B中的元素倒騰到A，往A中入棧

2.出隊列：把所有A的元素倒騰給B，從B出棧

3.取隊首元素：也是把A的元素倒騰給B，取B的棧頂

4.判定空，確保兩個棧都不空，此時整體為空

代碼段：

// 使用兩個棧, 模擬實現隊列.
public class MyQueue {// 創建兩個棧// A 用于入隊列, B 用于出隊列.Stack<Integer> A = new Stack<Integer>();Stack<Integer> B = new Stack<Integer>();public void push(int x) {// 先把 B 中的所有元素倒騰到 A 里, 然后把元素添加到 A 中.while (!B.isEmpty()) {A.push(B.pop());}A.push(x);}public int pop() {// 先把 A 中的所有元素倒騰到 B 里, 然后彈出 B 棧頂元素.while (!A.isEmpty()) {B.push(A.pop());}return B.pop();}public int peek() {// 先把 A 的所有元素倒騰到 B 里, 取 B 的棧頂元素.while (!A.isEmpty()) {B.push(A.pop());}return B.peek();}public boolean empty() {return A.isEmpty() && B.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/