【數據結構】棧(Stack)、隊列(Queue)、雙端隊列(Deque) —

棧和隊列

1. 棧（Stack）

1.1 概念

1.2 棧的使用（原始方法）

1.3 棧的模擬實現

【小結】

2. 棧的應用場景

1、改變元素的序列

2、將遞歸轉化為循環

3、逆波蘭表達式求值

4、括號匹配

5、出棧入棧次序匹配

6、最小棧

【概念區分】棧、虛擬機棧、棧幀有什么區別呢？

3. 隊列（Queue）

3.1 概念

3.2 隊列的使用（原生方法）

3.3?隊列的模擬實現

3.4 循環隊列

4. 雙端隊列 (Deque)

【面試題】

1、用隊列模擬實現棧（普通隊列和普通棧）

2、用棧模擬實現隊列（普通棧和普通隊列）

【總結】

棧和隊列

Vector基本上過時了，這里我們不進行講解。

LinkedList 不僅能當做鏈表(用List接口引用)，也能當做隊列(用Deque接口和Queue接口引用)
主要看你用哪種接口調用LinkedList(一定是LinkedList實現的接口)，LinkedList 就表現哪種形式。在使用方法的時候必須滿足接口中組織數據的形式。
主要看用哪種方式維護LinkedList的

1. 棧（Stack）

棧是一種數據結構，實體類，特點先進后出。如果數據要支持先進后出這種特點，就要選用數據結構棧這種方式來存儲或組織數據。

數據結構中，結構就是來描述組織數據的方式的，之所以會有很多數據結構，是因為我們有不同的需求，組織的數據方式不同，有了很多種存儲或組織數據的方式，所以就有了很多的數據結構。
棧只是一種數據結構，我們可以用數組（順序表），單鏈表，雙鏈表來實現棧（維護棧），但是在使用方法的時候必須滿足先進后出的形式。
棧的底層本來就是一個數組，因為stack類繼承了Vector類，而Vector類底層就是一個數組在存儲數據。

1.1 概念

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。

進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據在棧頂。

棧在現實生活中的例子：

子彈壓彈以及發射。羽毛球放入桶中以及拿出來。

1.2 棧的使用（原始方法）

Stack類中的方法原生方法比較少。size方法繼承于父類

方法	功能
Stack()	構造一個空的棧
E push(E e)	將e入棧，并返回e （入棧）
E pop()	將棧頂元素出棧并返回? （出棧）
E peek()	獲取棧頂元素? （查看棧頂元素）
int size()	獲取棧中有效元素個數
boolean empty()	檢測棧是否為空

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 獲取棧中有效元素個數---> 4System.out.println(s.peek()); // 獲取棧頂元素---> 4s.pop(); // 4出棧，棧中剩余1 2 3，棧頂元素為3System.out.println(s.pop()); // 3出棧，棧中剩余1 2 棧頂元素為2if(s.empty()){System.out.println("棧空");}else{System.out.println(s.size());}
}

1.3 棧的模擬實現

棧的底層本就是一個數組，可以用數組(順序表)，單鏈表，雙鏈表模擬實現棧，但是在使用方法的時候必須滿足先進后出的形式。

從上圖中可以看到，Stack繼承了Vector，Vector和ArrayList類似都是動態的順序表，不同的是Vector是線程安全的。

1、順序棧（用數組實現棧）

里面的數據是拿數組（順序表，動態擴容的數組）來組織實現的。
棧的底層其實就是一個數組，但是我們提供的方法必須滿足先進后出的形式。

?數組長度與數組中有效元素個數一定要分清楚。

這里usedSize，不僅可以記錄有效元素個數，還能標記當前存儲數據元素下標。

public class MyStack implements IStack {private int[] elem;private int usedSize;//1. 記錄有效元素個數//2. 存儲數據元素下標private static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new int[DEFAULT_CAPACITY];}//入棧@Overridepublic void push(int x) {if (full()) {elem = Arrays.copyOf(elem, elem.length * 2);}this.elem[usedSize] = x;usedSize++;}//出棧@Overridepublic int pop() throws StackEmptyException {if (empty()) {throw new StackEmptyException("棧為空！");}int old = elem[usedSize - 1];usedSize--;//相當于是刪除// 如果里面為引用類型// elem[usedSize] = null;return old;}//獲取棧頂元素，只查看不刪除@Overridepublic int peek() {if (empty()) {throw new StackEmptyException("棧為空！");}return this.elem[usedSize -1];}//棧中有效元素個數@Overridepublic int size() {return this.usedSize;}//棧是否為空@Overridepublic boolean empty() {return usedSize == 0;}//棧中元素是否滿了@Overridepublic boolean full() {return usedSize == elem.length;}//遍歷打印//注意：該方法并不是棧中的方法，為了方便看測試結果給出的public void display() {for (int i = 0; i < usedSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

棧為空異常類：

public class StackEmptyException extends RuntimeException{public StackEmptyException(String message) {super(message);}
}

2、用鏈表實現棧（鏈式棧）

用單向鏈表實現棧：其中入棧用頭插，出棧也是在頭部，時間復雜度為O(1)
用雙向鏈表實現棧：頭尾都可以作為出棧和入棧。時間復雜度為O(1)

【小結】

數組維護（實現）棧

棧的底層本質就是數組（動態擴容的數組）
出棧和入棧時間復雜度都是為O(1)

鏈表實現棧 (鏈式棧)：

單鏈表維護棧

需要滿足時間復雜度為O(1)，所以從頭部插入（入棧），從頭部刪除（出棧）
如果從尾部插入和刪除，非常的麻煩（插入的時候需要找尾節點，刪除的時候還需要找尾結點）時間復雜度都為O(n)

雙向鏈表維護棧

從頭部插入（入棧），從頭部刪除（出棧）
從尾部插入（入棧），從尾部刪除（出棧）
不管從哪里入棧和出棧時間復雜度都是O(1)

棧的底層本就是一個數組，可以用數組（順序表），單鏈表，雙鏈表模擬實現棧，但是在使用方法的時候必須滿足先進后出的形式。

2. 棧的應用場景

1、改變元素的序列

2、將遞歸轉化為循環

比如：逆序打印鏈表

用遞歸方法實現逆序打印鏈表

遞歸找兩個條件：1、終止條件。2、找自己本身

//遞歸打印鏈表
public void display3(LinkedList pHead) {if (pHead == null) {return;}if (head.next == null) {System.out.println(pHead.val + " ");}display3(pHead.next);System.out.println(pHead.val + " ");
}

遞歸其實就是棧的形式，每次遞歸都要在棧上開辟棧幀，用棧模擬遞歸的形式。

利用棧（鏈式棧，用鏈表實現棧）去打印逆序鏈表

思路：棧是先進后出的，所以把鏈表中的節點放進棧中，然后出棧打印，就能逆序打印出鏈表了

//循環方法 利用棧
public void display4() {Stack<ListNode> stack = new Stack<>();ListNode cur = head;//將鏈表中的節點保存到棧中while (cur != null) {stack.push(cur);cur = cur.next;}//遍歷棧while (!stack.empty()) {System.out.print(stack.pop() + " ");}System.out.println();
}

3、逆波蘭表達式求值

給你一個字符串數組?tokens?，表示一個根據?逆波蘭表示法?表示的算術表達式。

請你計算該表達式。返回一個表示表達式值的整數。OJ鏈接

什么是逆波蘭表達式：

將中綴表達式" 1 + ( ( 2 + 3 ) * 4 ) - 5 "轉換為后綴表達式（逆波蘭表達式）為：" 1 2 3 + 4 * + 5 - "
計算器怎么知道字符（ + - * / ）的優先級的高低呢（怎么識別括號的），一般在計算器中運算會把中綴表達式轉換為后綴表達式，再通過后綴表達式計算這個表達式的值。
中綴表達式轉換為后綴表達式(逆波蘭表達式)步驟，選擇題或填空題小技巧

第一步：從左到右，先乘除后加減，都填上括號

第二步：對應的運算符，挪倒右邊括號的外面，只挪一次

第三步：把所有的括號都去掉，就得到了后綴表達式（逆波蘭表達式）

拿到后綴表達式了，怎么去計算這個后綴表達式結果呢？

思路：

遍歷后綴表達式，把后綴表達式中的元素依次放進棧中，如果遇到了運算符，則彈出棧頂的兩個元素，
第一個元素作為運算符的右操作數，第二個元素作為運算符的左操作數，進行計算，只要遇到運算符就彈出棧頂兩個元素進行運算，運算后的結果再次入棧，
然后接著讓后綴表達式中的元素入棧，直到后綴表達式的元素全部計算完。

遍歷后綴表達式，只要是數字就入棧，是字符就彈出棧頂的兩個元素，參與運算，最后把運算之后的結果，再次入棧。

這里給了字符串數組，避免二位數的數字被拆分開。

public int evalRPN(String[] tokens) {//創建一個棧Stack<Integer> stack = new Stack<>();//遍歷后綴表達式for (String x : tokens) {//如果是操作數，放到棧中if (!isOperation(x)) {//這里將String類類型拆行為int基本類型并壓棧//壓棧時自動裝箱stack.push(Integer.parseInt(x));} else {//如果是運算符則需要彈出棧頂兩個元素，作為操作數進行運算//第一個為右邊操作數，第二個左邊操作數int num2 = stack.pop();int num1 = stack.pop();/*if (x.equals("+")) {stack.push(num1 + num2);}if (x.equals("-")) {stack.push(num1 - num2);}if (x.equals("*")) {stack.push(num1 * num2);}if (x.equals("/")) {stack.push(num1 / num2);}*///這里用switch語句更簡潔，如果用if語句形式太多太復雜//判斷是哪種運算符，并進行運行switch (x) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;}}}//走完for循環，棧內就剩一個元素了 即計算后的結果，直接返回return stack.pop();
}//判斷是否是運算符
private boolean isOperation(String s) {if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;} else {return false;}
}

4、括號匹配

給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判斷字符串是否有效。OJ鏈接

有效字符串需滿足：左括號必須用相同類型的右括號閉合。左括號必須以正確的順序閉合。每個右括號都有一個對應的相同類型的左括號。

分為幾種情況：

匹配。字符串遍歷完成且棧為空。
不匹配。
一部分匹配：
左括號多：字符串遍歷完成，棧不空
右括號多：字符串沒有遍歷完，棧空了

思路：

遍歷字符串，讓左括號入棧，遇到右括號從棧中彈出元素，
看該元素是否是與右括號匹配的左括號（如果是有效的字符串，則一定是第一個右括號與最后一個左括號先匹配），
字符串遍歷完了同時棧也空了，說明匹配的。

//括號匹配
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//1.遍歷字符串for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//2.判斷是否是左括號if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch);} else {//3.遇到了右括號//判斷是否是第一次遇見右括號 同時判斷了字符串沒有遍歷完，棧就為空的情況if (stack.empty()) {return false;}char ch2 = stack.peek();//ch2是左括號，獲取棧頂元素不刪除 此時ch是右括號//出棧的左括號是否跟此時右括號匹配if ((ch2 == '(' && ch == ')') || (ch2 == '{' && ch == '}') || (ch2 == '[' && ch == ']')) {stack.pop();} else {return false;}}}if(!stack.empty()) {return false;}return true;
}

5、出棧入棧次序匹配

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設壓入棧的所有數字均不相等。OJ鏈接

例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

思路：

遍歷第一個序列進行壓棧，每次壓棧后棧頂的元素與第二個序列中的元素進行匹配，
如果一樣，第二個序列 j 往后走繼續比較，如果不同，第一個序列繼續壓棧然后再比較，直到第一個序列遍歷完，
如果棧中沒有元素，則出棧入棧次序匹配，如果棧中還有元素沒有匹配，則出棧入棧次序不匹配。

//出棧入棧次序匹配
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;//遍歷第一個序列并壓棧for (int i = 0; i < popV.length; i++) {stack.push(pushV[i]);//判斷棧頂元素是否與第二序列j位置的元素是否相同while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}//棧中是否還有元素return stack.empty();/*if (!stack.empty()) {return false;}return true;*/
}

這里注意stack.peek() == popV[j] ，我們需要對stack是否為空和popV[j]是否越界進行判斷。
有可能棧空了，j 還沒走完
有可能 j 走完了，棧還沒為空
還有一點：stack.peek() == popV[j] 比較的時候盡量用 equals 進行比較。
Integer的取值范圍是 [-128,127]之間，如果彈出的元素在這個范圍之內用 == 比較沒問題，如果超過了這個范圍這個語句表達的結果就是false

6、最小棧

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。即時間復雜度為O(1)?OJ鏈接

實現 MinStack 類:

MinStack() 初始化堆棧對象。

void push(int val) 將元素val推入堆棧。

void pop() 刪除堆棧頂部的元素。

int top() 獲取堆棧頂部的元素。

int getMin() 獲取堆棧中的最小元素。

pop、top?和?getMin?操作總是在?非空棧?上調用。

問題分析：

如果只有一個棧，把元素全部壓進去，而最小的元素在棧底，那我們必須把棧底上面的元素都出棧，才能得到這個最小的元素，
如果有n個元素，那么檢索到最小元素就不是常數時間了（即要在O(1)的時間內拿到最小值）。且在出棧的過程中最小值是在變化的。

思路：

所以必須有兩個棧，一個普通棧Stack，一個最小棧minStack。 在第一次往Stack中壓棧的時候，無論放值多大或多小，我們都要維護這個值，把它壓入minStack棧中，
再次往Stack中壓棧時，壓棧的元素要與minStack棧頂元素比較，如果小于或等于minStack棧頂元素，我們也要維護這個元素，在Stack中壓棧的同時也要把該元素壓入minStack棧中，如果大于只在Stack中壓棧，
當壓棧序列遍歷完后，最小棧minStack棧頂元素就是這個壓棧序列的最小元素了，能在常數時間內檢索到最小元素的棧。
出任何元素的時候如果這個元素在最小棧minStack中有維護的話，minStack棧中也需要出棧。且在出棧的過程中最小值是在變化的。

應題目要求，pop，top和getMin?操作總是在 非空棧?上調用，所以這些方法不用再判斷棧是否為空。

import java.util.Stack;
class MinStack {public Stack<Integer> stack;public Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}//入棧public void push(int val) {stack.push(val);if (minStack.empty()) {minStack.push(val);return;}int peekVal = minStack.peek();//-1 < 3if (val <= peekVal) {minStack.push(val);}}//出棧public void pop() {int val = stack.pop();if (val == minStack.peek()) {minStack.pop();}}// peek 獲得當前普通棧的棧頂元素，不刪除public int top() {return stack.peek();}//最小棧的peek，每次通過這個方法獲取 最小值public int getMin() {return minStack.peek();}
}

當寫的代碼出錯了，一定記得調試：

看哪個測試用例錯了
拿著這個測試用例去調試畫圖
一定記住不能光看代碼！！！看代碼是看不出來的
如果通過肉眼就能看到代碼的問題那為什么我們要有編譯器呢？直接記事本寫代碼不就好了。

【概念區分】棧、虛擬機棧、棧幀有什么區別呢？

棧是一種先進后出的數據結構；
虛擬機棧是JVM劃分的一塊內存；
棧幀：運行程序調用方法時會在虛擬機當中，給這個方法開辟一塊內存(空間)，開辟的空間就叫作棧幀。

每個函數(方法)在運行時，jvm都會創建一個棧幀，然后將棧幀壓入到虛擬機棧中，當函數調用結束時，該函數對應的棧幀會從虛擬機棧中出棧。

注意：每個方法在棧幀中結構都是一樣，大小可能不同，棧幀的大小在程序編譯時已經確定好的。

3. 隊列（Queue）

3.1 概念

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(FirstIn First Out)

入隊列：進行插入操作的一端稱為隊尾（Tail/Rear）
出隊列：進行刪除操作的一端稱為隊頭（Head/Front）

3.2 隊列的使用（原生方法）

在Java中，Queue是個接口，底層是通過鏈表實現的。

Queue接口里有兩組方法，即add，remove，element與offer，poll，peek是對應的，但它們是有區別的，下面會講。常用的為后者。size和isEmpty方法是繼承父類的。

方法	功能
boolean offer(E e)	入隊列
E poll()	出隊列
peek()	獲取隊頭元素（查看元素，不刪除）
int size()	獲取隊列中有效元素個數
boolean isEmpty()	檢測隊列是否為空

注意：Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現了Queue接口。

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 從隊尾入隊列System.out.println(q.size());System.out.println(q.peek()); // 獲取隊頭元素q.poll();System.out.println(q.poll()); // 從隊頭出隊列，并將刪除的元素返回if(q.isEmpty()){System.out.println("隊列空");}else{System.out.println(q.size());}
}
//執行結果
5
1
2
3

3.3?隊列的模擬實現

隊列中既然可以存儲元素，那底層肯定要有能夠保存元素的空間，通過前面線性表的學習了解到常見的空間類型有兩種：順序結構和鏈式結構。同學們思考下：隊列的實現使用順序結構還是鏈式結構好？鏈式實現(使用較多)，數組(順序表)實現。

隊列的底層本就是一個雙向鏈表，可以用數組(順序表)，單鏈表，雙鏈表模擬實現隊列，但是在使用方法的時候必須滿足先進先出的形式。

1、用鏈式實現隊列（鏈式隊列）

單鏈表實現隊列：

入：頭插法 -> O(1)? ? ?出：刪除鏈表最后一個（需要找尾巴） O(n)
入：尾插法 -> O(N)(需要找尾巴)? ? 出：刪除鏈表第一個 O(n)
需要滿足時間復雜度為O(1)，隊列的特性。

雙鏈表實現隊列（用的最多）

入：頭插法 -> O(1)? ? 出：刪除鏈表最后一個 O(1)
入：尾插法 -> O(1)? ? 出：刪除鏈表第一個 O(1)

單鏈表實現隊列哪種形式時間復雜度都是O(n)，有局限性；而雙鏈表實現隊列哪種形式時間復雜度都是O(1)，而且隊列的底層本來就是雙鏈表實現的，所以使用雙鏈表實現較多。

雙向鏈表模擬實現隊列：

//雙向鏈表模擬實現隊列
public class MyLinkedListQueue {//節點，內部類public static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//入隊列,尾插public boolean offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.prev.next = node;node.prev = last;last = node;}usedSize++;return true;}//出隊列，頭刪public int poll() throws QueueEmptyException {if (head == null)  {throw new QueueEmptyException("隊列為空！");}int retVal =  head.val;if (head.next == null) {head = null;last = null;} else {head = head.next;head.prev = null;}usedSize--;return retVal;}//獲取隊頭元素，不刪除public int peek() throws QueueEmptyException {if (head == null) {throw new QueueEmptyException("隊列為空！");}return head.val;}public int size() {return usedSize;}public boolean empty() {return head == null;}
}

隊列為空的自定義異常類

public class QueueEmptyException extends RuntimeException {public QueueEmptyException(String message) {super(message);}
}

單向鏈表模擬實現隊列：

這里我們為了更方便模擬實現，在單鏈表中定義了head指向頭節點，last 指向尾節點，usedSize記錄節點個數。
需要滿足時間復雜度為O(1)，隊列的特性。只能從尾入，從頭刪，時間復雜度就都是O(1)了；如果從頭進，從尾刪，時間復雜度仍為O(n)，因為尾結點刪除你找不到上一個節點是誰了（單向的）。
如果是雙向鏈表實現就沒有局限，所以雙向鏈表才是最通用的鏈表。

//單向鏈表模擬實現隊列
public class MySingleListQueue {//節點，內部類public static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//入隊列,尾插public boolean offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.next = node;last = node;}usedSize++;return true;}//出隊列，頭刪public int poll() throws QueueEmptyException {if (head == null)  {throw new QueueEmptyException("隊列為空！");}int retVal =  head.val;if (head.next == null) {head = null;last = null;} else {head = head.next;}usedSize--;return retVal;}//獲取隊頭元素，不刪除public int peek() throws QueueEmptyException {if (head == null) {throw new QueueEmptyException("隊列為空！");}return head.val;}public int size() {return usedSize;}public boolean empty() {return head == null;}
}

2、用數組實現隊列（順序隊列）

數組（順序表）實現隊列會出現下面情況，從reat位置入(隊尾)，從front位置出(隊頭)，如果數組后面已經滿了，而前面因為刪除了元素空出了，怎么才能利用起來前面的空間呢，

rear是當前可以存放數據元素下標。

如果說讓元素整體往前挪，也需要消耗時間；我們能不能讓reat再回去，所以我們引出了環形隊列(循環隊列)。

下面的循環隊列，就是用數組(順序表)模擬實現的隊列。

3.4 循環隊列

實際中我們有時還會使用一種隊列叫循環隊列。如操作系統課程講解生產者消費者模型時可以就會使用循環隊列。環形隊列通常使用數組實現。

rear是當前可以存放數據元素的下標，與數組模擬實現棧中useSize異曲同工之妙。

rear可能放元素放滿了，與front相遇；或者front出元素數組為空了，與rear相遇。

問題1、rear和front相遇了，如何區分空與滿

解決空還是滿，有很多種方案：

使用usedSize進行記錄
浪費一個空間來表示滿
使用標記

這里我們主要講解第二種方案：

例如：這里要放89我們可以先讓rear判斷下一個是否是front，如果下一個是front證明滿了不能放了。否則沒滿。即每次放元素之先rear判斷一下。

如果front與rear相遇，就認為是空的。
如果reat下一個是front，就認為是滿的。

問題2、rear怎么從7下標，來到0下標

rear從7下標到0下標，同時兼顧1下標到2下標這種普通情況。
rear = (rear + 1) % len
front = (front + 1) % len

設計一個循環隊列。OJ鏈接

class MyCircularQueue {public int[] elem;//public int usedSize;public int front;//表示隊頭public int rear;//表示隊尾public MyCircularQueue(int k) {elem = new int[k + 1];}//入隊列,數組尾入public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}//出隊列，數組頭出public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}//從隊首獲取元素public int Front() {if (isEmpty()) {return -1;//或拋出自定義異常}return elem[front];}//獲取隊尾元素public int Rear() {if (isEmpty()) {return -1;//或拋出自定義異常}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}//檢查循環隊列是否為空public boolean isEmpty() {return front == rear;}//檢查循環隊列是否已滿public boolean isFull() {return (rear + 1) % elem.length == front;}
}

這里有兩點要注意的：

???rear是當前可以存放數據元素的下標，獲取隊尾元素時會有一種極端情況，如果此時rear是0下標位置，找隊尾下標就是下標為7的位置，不能直接通過rear-1 來獲得隊尾下標。
傳入參數k空間容量大小，但是我們是通過浪費一個空間來表示滿的情況，需要數組多申請一個，即new? k+1個空間的數組。或者定義usedSize，通過數據的個數來表示front與rear相遇時是滿的還是空的情況，就不存在浪費空間的說法了。

4. 雙端隊列 (Deque)

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

Deque是一個接口，使用時必須創建LinkedList的對象。底層是雙向鏈表實現的。

我們發現，Deque中包含了很多方法：

Deque底層有 offer()，poll()，peek()? 和 add()，remove()，element()?
Queue底層也有 offer()，poll()，peek()? 和 add()，remove()，element()?
它們屬于兩組方法，功能互相對應。
區別：底層代碼注解為，add 插不了元素會拋異常，對于offer 來說不會拋異常，認為offer 方法優于add

在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口：

Deque<Integer> stack = new ArrayDeque<>();//雙端隊列的線性實現
Deque<Integer> queue/deque = new LinkedList<>();//雙端隊列的鏈式實現
?不僅可以當做隊列，也可以當做棧。
雙端隊列線性實現 -》常用當做棧使用，因為棧底層本身就是數組。
雙端隊列鏈式實現 -》常用當做隊列或雙端隊列使用，因為隊列或雙端隊列底層本身就是鏈表(雙向鏈表)

【面試題】

他實現了我：必須是他類中的方法，遵循我的形式，來模擬實現我的形式。

1、用隊列模擬實現棧（普通隊列和普通棧）

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。OJ鏈接

問題分析：

隊列是先進先出的，棧是先進后出的，這兩個矛盾的，所以要用隊列實現棧，一個隊列是無法實現棧的。需要兩個隊列實現棧。
用隊列實現棧，那拿什么實現隊列呢，用Linkedlist（雙向鏈表）實現隊列。
為什么不用ArrayDeque （數組）實現鏈表呢，這就把問題拉回到了用數組和鏈表區別的問題了。因為數組實現隊列有一個缺點就是擴容問題，可能會浪費空間；用Linkedlist實現隊列比較多。
用鏈表也可以實現棧，用數組也可以實現棧，但是用數組實現的比較多，用鏈表實現棧每次需要維護它的指向，所以具體使用看場景。

思路：

一個隊列是無法實現棧的，需要兩個隊列實現棧。實例化兩個隊列，一個為qu1，一個為qu2。
”入棧“操作讓元素進入非空的隊列，如果非空的隊列為qu1 ，則讓元素入隊列(qu1)，就是用隊列實現了"入棧"的操作，此時”出棧“操作則是讓qu1中的size-1個元素出隊列，然后依次人隊列(qu2)中，此時qu1中還剩一個元素，出隊列，就是用隊列實現了"出棧"的操作；
如果非空的隊列為qu2，則讓元素入隊列(qu2)，就是用隊列實現了"入棧"的操作，此時”出棧“操作則是讓qu2中的size-1個元素出隊列，然后依次人隊列(qu1)中，此時qu2中還剩一個元素，出隊列，就是用隊列實現了"出棧"的操作；
如果兩個隊列都是空的話，則讓元素入隊列(qu1)，就是用隊列實現了"入棧"的操作。

”入棧“：元素放到不為空的隊列中，如果兩個隊列都為空那么就放到第一個隊列當中。
”出棧“：元素不為空的隊列，出size-1個元素到另一個隊列當中
當兩個隊列都為空的時候，那么說明模擬的棧是空的

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//隊列中模擬實現棧的入棧操作public void push(int x) {//哪個隊列不為空入哪個隊列if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()){qu2.offer(x);} else {//兩個隊列都為空的 指定存放到第一個隊列當中qu1.offer(x);}}//隊列中模擬實現棧的出棧操作public int pop() {//兩個隊列都為空if (empty()) {return -1;//或者拋出自定義異常}//判斷哪個隊列不為空//出size - 1個元素到另一隊列中if (!qu1.isEmpty()) {int size = qu1.size();//進來后，que1隊列出size - 1個元素到qu2中for (int i = 0; i < size - 1; i++) {//for (int i = 0; i < qu1.size()-1; i++) {//這里的for循環不能這樣寫，因為qu1中的size一直在變，//每次qu1中元素出棧后底層的size就會減減，會導致循環次數減少int x = qu1.poll();qu2.offer(x);}return qu1.poll();} else {int size = qu2.size();//進來后，que2隊列出size - 1個元素到qu1中for (int i = 0; i < size - 1; i++) {int x = qu2.poll();qu1.offer(x);}return qu2.poll();}}//隊列中模擬實現棧的獲得棧頂元素操作public int top() {//兩個隊列都為空if (empty()) {return -1;//或者拋出自定義異常}//判斷哪個隊列不為空//出size個元素到另一隊列中if (!qu1.isEmpty()) {int size = qu1.size();int x = -1;//進來后，que1隊列出size個元素到qu2中for (int i = 0; i < size; i++) {x = qu1.poll();qu2.offer(x);}return x;} else {int size = qu2.size();int x = -1;//進來后，que2隊列出size個元素到qu1中for (int i = 0; i < size; i++) {x = qu2.poll();qu1.offer(x);}return x;}}//隊列中模擬實現棧的是否為空操作public boolean empty() {//兩個隊列同時為空時，說明模擬實現的棧是空的return qu1.isEmpty() && qu2.isEmpty();}
}

這里代碼要注意兩點：

隊列中模擬實現棧的出棧操作和獲得棧頂元素時，for遍歷一個隊列size - 1個元素出隊列到另一隊列時，size() - 1 不能作為for循環的判斷條件。因為每次元素從該隊列出去，size()在不斷減少(變化)，會導致循環次數減少。定義一個變量記錄一下size()的值。
隊列中模擬實現棧的獲得棧頂元素操作時，我們需要一個隊列中的size個元素全部到另一個隊列中，定義一個變量，每次出隊列到另一個隊列的元素都記錄一下，最后一次記錄的就是需要的元素。

2、用棧模擬實現隊列（普通棧和普通隊列）

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）?OJ鏈接

思路：

一個棧是無法實現隊列的，需要兩個棧實現隊列。實例化兩個棧，一個是s1，一個是s2。
“入隊列”操作讓元素進入s1棧中，就是用棧實現了“入隊列”操作。
“出隊列”操作讓 s1棧中的元素全部(size()個）依次出棧，然后進入s2棧中，此時s2棧中的元素順序與之前s1棧中的元素順序是相反的，然后出s2棧棧頂的元素，就用棧實現了“出隊列”的操作。

“入隊”：入到s1中
“出隊”：s2棧為空，s1中的元素，一個一個全部倒放到第二個隊列當中。

//用棧模擬實現隊列（普通棧和普通隊列）
class MyQueue {private Deque<Integer> s1;private Deque<Integer> s2;public MyQueue() {s1 = new ArrayDeque<>();s2 = new ArrayDeque<>();}//棧中模擬實現隊列的入隊列操作public void push(int x) {s1.push(x);}//棧中模擬實現隊列的出隊列操作public int pop() {if (empty()) {return -1;//或拋出自定義異常，但力扣上認為-1是正確的}if (s2.isEmpty()) {int size = s1.size();for (int i = 0; i < size; i++) {int x = s1.pop();s2.push(x);}}return s2.pop();}//棧中模擬實現隊列的獲得隊頭元素操作public int peek() {if (empty()) {return -1;//或拋出自定義異常，但力扣上認為-1是正確的}if (s2.isEmpty()) {int size = s1.size();for (int i = 0; i < size; i++) {int x = s1.pop();s2.push(x);}}return s2.peek();}//棧中模擬實現隊列的是否為空操作public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}

這里同樣也要注意：棧中模擬實現隊列的出棧操作和獲得隊頭元素時，for遍歷一個棧size個元素出棧到另一棧時，size()不能作為for循環的判斷條件。因為每次元素從該棧出去，size()在不斷減少(變化)，會導致循環次數減少。定義一個變量記錄一下size()的值。

【總結】

分清楚一點

棧(Stack)是普通類先進后出

棧可以實例化，可以被數組（順序表）、單鏈表、雙鏈表實現；棧繼承了Vector類，而Vector類底層就是一個數組在存儲數據，所以棧的底層其實就是數組(順序表)。
通過數組（順序表）、單鏈表、雙鏈表實現的棧調用方法必須遵先進后出的形式。拿數組（順序表）實現的棧最常用。

用Stack 去引用自己的對象其實不常用。Stack<Integer> stack = new Stack<>(); 不常用
用ArrayDeque雙端隊列的線性實現，來代替實現棧。Deque<Integer> stack = new ArrayDeque<>(); 常用
ArrayDeque類底層也是數組（順序表結構）

隊列(Queue)是一個接口先進先出

隊列不能實例化，但可以被數組（順序表）、單鏈表、雙鏈表實現；隊列的底層是被LinkedList類實現的，LinkedList底層又是雙向鏈表，所以隊列的底層其實就是雙向鏈表。
通過數組（順序表）、單鏈表、雙鏈表實現的隊列調用方法必須遵循先進先出的形式。
拿LinkedList（雙向鏈表）來實現隊列最常用。Queue<Integer> queue = new LinkedList<>();

雙端隊列(Deque)是一個接口雙端進出都可以

雙端隊列不能實例化，但可以被數組（順序表）、單鏈表、雙鏈表實現；雙端隊列的底層是被LinkedList類實現的，LinkedList底層又是雙向鏈表，所以雙端隊列的底層其實就是雙向鏈表。
通過數組（順序表）、單鏈表、雙鏈表實現的隊列調用方法必須遵循的雙端進出都可以形式。
拿LinkedList（雙向鏈表）來實現雙端隊列最常用。Deque<Integer> deque/queue?= new LinkedList<>();

拿接口去引用對象與拿對象本身來引用自己對象有什么區別？