隊列

什么是隊列

是一種線性的數據結構，和棧不同，隊列遵循“先進先出”的原則。如下圖所示：

在集合框架中我們可以看到LinkedList類繼承了Queue類（隊列）。

普通隊列（Queue）

Queue中的方法

方法	功能
add()	入隊列
offer()	入隊列
remove()	出隊列
poll()	出隊列
element()	獲取隊頭元素
peek()	獲取隊頭元素

add()和offer()都是添加數據、remove()和poll()都是刪除數據、element()和peek()都是獲取隊列頭部元素信息這些方法有什么區別呢？（下面都是豆包總結的，可以參考一下）


總結：
add()、remove()、element()方法對于滿和空隊列的時候會拋出異常。而offer()、poll()、peek()方法不會，它們更具有靈活性。我們則常用offer()、poll()、peek()方法來對隊列進行操作。

其他方法

在Collection接口中還有size()、isEmpty()等其他方法我們可以使用。

模擬實現隊列

用鏈表實現

public class MyQueue {static class ListNode{private final int val;private ListNode next;private ListNode prev;private ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;/*** 入隊操作：尾插法* @param val*/public void offer(int val) {ListNode node = new ListNode(val);if(empty()) {first = last = node;}last.next = node;node.prev = last;last = last.next;}/*** 出隊操作：刪除頭節點* @return*/public int poll() {if(empty()) {return -1;}int value = first.val;if(first == last) {first = last = null;return value;}else {first = first.next;first.prev = null;return first.val;}}/*** 獲得頭節點不刪除* @return*/public int peek() {if(empty()) {return -1;}return first.val;}/*** 獲得有效數據* @return*/public int size() {ListNode cur = first;int usedSize = 0;while (cur != null) {usedSize++;cur = cur.next;}return usedSize;}/*** 判斷是否為空* @return*/public boolean empty() {return first == null;}
}

循環隊列

對于普通的數組來說，再用隊列的思想時，很容易造成數組下標越界等問題。這時候我們可以將數組循環起來。如下圖所示：

這時候就產生問題了。

1、rear 和 front 如何訪問從最后一個下標訪問到0下標？

由于循環，可以將（下標+偏移量）/ length。這里的偏移量為1（每次只走一格）。也就是對于有關下標的需要用(rear+1) / len 和 (front+1) / len。

2、如何判斷數組是否滿了。

解決的方法有：
1、使用size個數，當等于數組長度，則說明滿了；
2、用一個boolean值來標記是否滿了。初始時，front == rear，isFull == false。當每次添加數據時判斷 front == rear，當相等時isFull == true，說明滿了。在刪除數據時，不可能滿了，將isFull == false；
3、留出一個空間來判斷是否滿了。當rear的下一個是front的時候，就說明是滿的。

在入隊時，放一個元素，rear往后走，一開始 rear == front。當rear的下一個是front的時候，也就只存放了 len - 1個數據。

代碼展示：

采用預留空間的方法

class MyCircularQueue {public int[] elem;int rear = 0;int front = 0;public MyCircularQueue(int k) {elem = new int[k];//由于采用預留空間的方法，使得實際數據只有k - 1個}/*** 向循環列隊中插入一個元素* @param value* @return*/public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;//rear指向預留的空間rear = (rear + 1) % elem.length;//這樣rear下標始終控制在合理范圍return true;}/*** 刪除循環列隊中的一個元素* 由于隊列是先進先出的，所以刪除的是front下標的元素* @return*/public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % elem.length;//這樣front下標始終控制在合理范圍return true;}/*** 從隊首獲取元素* @return*/public int Front() {if(isEmpty()) {return -1;}return elem[front];}/*** 獲取隊尾元素* @return*/public int Rear() {if(isEmpty()) {return -1;}//rear并不是隊尾元素，rear的上一個才是。//rear - 1就得到了，但當rear為0時，rear - 1 就會越界，這時候就要if判斷了if(rear == 0) {return elem[elem.length - 1];}return elem[rear - 1];}/*** 判斷循環隊列是否為空* @return*/public boolean isEmpty() {return rear == front;}/*** 判斷循環隊列是否滿了* @return*/public boolean isFull() {return (rear + 1) % elem.length == front;//rear為預留空間，下一個指向front}
}

雙端隊列（Deque）

它是一種特殊的隊列，允許在隊列的兩端進行元素的插入與刪除操作。這意味著既能在隊列頭部添加或移除元素，也能在隊列尾部添加或移除元素。一般創建ArrayDeque、LinkedList這兩個類的對象。
ArrayDeque是用數組實現的雙端隊列，LinkedList是用雙向鏈表實現的雙端隊列。其中的優缺點和順序表與鏈表的優缺點類似。
對于雙端隊列的方法是在Queue方法名中后面加上Last、First（例如：offerFirst()、pollFirst()、peekLast()等，但要注意的是：對于拋異常的獲取元素并不是用的element()而是getFirst()和getLast() ）。

代碼展示：

public static void test1() {Deque<Integer> deque = new ArrayDeque<>();deque.offerFirst(1);deque.offerFirst(10);deque.offerFirst(100);deque.offerFirst(1000);deque.offerLast(2);deque.offerLast(20);System.out.println(deque);deque.pollFirst();//出隊列的頭元素：1000System.out.println(deque);deque.pollLast();//出隊列的尾元素：20System.out.println(deque);System.out.println(deque.peekFirst());System.out.println(deque.peekLast());System.out.println(deque);
}

public static void test2() {Deque<Integer> deque = new LinkedList<>();deque.offerFirst(1);deque.offerFirst(10);deque.offerFirst(100);deque.offerFirst(1000);deque.offerLast(2);deque.offerLast(20);System.out.println(deque);deque.pollFirst();//出隊列的頭元素：1000System.out.println(deque);deque.pollLast();//出隊列的尾元素：20System.out.println(deque);System.out.println(deque.peekFirst());System.out.println(deque.peekLast());System.out.println(deque);
}

ArrayDeque、LinkedList兩個實現的效果是一樣的。

用隊列實現棧

首先一個隊列肯定是實現不了棧的，兩個運行邏輯都不一樣，一個先進先出，一個先進后出。此時需要兩個隊列來實現棧。

對于出"棧"方法：將其余數據依次放入空隊列中（對非空隊列進行出"棧"操作）。

對于入"棧"，只需要將元素放入非空的隊列中即可。

對于拿到"棧"頂的元素，前面和出"棧"一樣：將其余數據依次放入空隊列中，直接輸出剩下的元素，在將剩下的元素放到另一個隊列中。

代碼展示：

import java.util.LinkedList;
import java.util.Queue;class MyStack {public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}/*** 入棧* @param x*/public void push(int x) {if(!queue1.isEmpty()) {queue1.offer(x);}else if(!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}/*** 出棧* @return*/public int pop() {//當都為空時，說明"棧"中沒有元素if(empty()) {return -1;}//對于非空隊列進行操作if(!queue1.isEmpty()) {int size = queue1.size();//將其余元素移到空隊列while (size != 1) {queue2.offer(queue1.poll());size--;}//返回隊列中僅有的元素，并刪除return queue1.poll();}else {//下面是!queue2.isEmpty()的情況int size = queue2.size();while (size != 1) {queue1.offer(queue2.poll());size--;}return queue2.poll();}}/*** 獲取"棧"頂元素* @return*/public int top() {//判斷棧是否為空if(empty()) {return -1;}if(!queue1.isEmpty()) {int size = queue1.size();while (size != 1) {queue2.offer(queue1.poll());size--;}//上述操作和出棧一樣，下面只需輸出元素，并不刪除數據int value = queue1.poll();queue2.offer(value);//將元素入隊，避免丟失return value;}else {int size = queue2.size();while (size != 1) {queue1.offer(queue2.poll());size--;}int value = queue2.poll();queue1.offer(value);return value;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();//當隊列都為空時，說明"棧"為空}
}

用棧實現隊列

同樣的，也是需要兩個棧的。

對于出"隊列"，只需要將非空棧（stack1）中的元素全部放到另一個棧中（stack2），再從stack2中出元素。

當stack2為空，則將stack1全部放入stack2中。

對于入"隊列"來說，只需要將元素放到stack1中。

代碼展示：

import java.util.Stack;class MyQueue {public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if (stack2.empty()) {while (!stack1.empty()) {//需要將stack1中的元素 全部 放到stack2中（用while循環）stack2.push(stack1.pop());}}return stack2.pop();//stack2棧中有元素，直接調用方法}public int peek() {if(empty()) {return -1;}if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}