實(shí)現(xiàn)一個(gè)類，類中定義一個(gè)數(shù)組成員變量，為了滿足棧的特性，數(shù)組只允許尾插和尾刪：

大體框架如下：

public class MyStackByArray {public int[] elem;//棧public int capacity;//棧的容量public int usedSize;//棧的有效元素個(gè)數(shù)public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入棧public void push(int data) {}//出棧并返回出棧元素public int pop() {}//獲取棧頂元素public int peek() {}//獲取棧中的有效元素public int size() {}//檢測(cè)棧是否為空public boolean empty() {}
}

public int size()

返回成員變量usedSize即可

    //獲取棧中的有效元素public int size() {return this.usedSize;}

public boolean empty()

    //檢測(cè)棧是否為空public boolean empty() {return this.usedSize == 0;}

public void push(int data)

由于數(shù)組下標(biāo)從0開始，所以成員變量usedSize其實(shí)就是下一次入棧的下標(biāo)位置。入棧前，我們要判斷棧是否滿，滿了要擴(kuò)容，之后進(jìn)行入棧即可：

    //入棧public void push(int data) {//棧滿則擴(kuò)容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入棧this.elem[this.usedSize] = data;this.usedSize++;}

public int pop()

出棧前，我們判斷棧是否為空，當(dāng)為空時(shí)，我們選擇拋出一個(gè)自定義異常：StackIsException

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

如果不為空，執(zhí)行出棧，注意，出棧直接讓usedSize--即可，不需要特意將棧頂元素置成0，因?yàn)楫?dāng)下次入棧時(shí)會(huì)覆蓋掉此元素

    //出棧并返回出棧元素public int pop() {//判斷棧是否為空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}//出棧this.usedSize--;return this.elem[this.usedSize];}

public int peek()

獲取棧頂元素，判斷為空？為空拋出異常，否則返回

    //獲取棧頂元素public int peek() {//判斷棧是否為空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}return this.elem[this.usedSize - 1];}

完整代碼：

public class MyStackByArray {public int[] elem;public int capacity;public int usedSize;public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入棧public void push(int data) {//棧滿則擴(kuò)容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入棧this.elem[this.usedSize] = data;this.usedSize++;}//出棧并返回出棧元素public int pop() {//判斷棧是否為空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}//出棧this.usedSize--;return this.elem[this.usedSize];}//獲取棧頂元素public int peek() {//判斷棧是否為空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}return this.elem[this.usedSize - 1];}//獲取棧中的有效元素public int size() {return this.usedSize;}//檢測(cè)棧是否為空public boolean empty() {return this.usedSize == 0;}
}

【鏈表實(shí)現(xiàn)?！?/strong>

public class MyStackByLinkedList {//鏈表結(jié)點(diǎn)類static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//鏈表第一個(gè)結(jié)點(diǎn)的引用public ListNode head;//入棧public void push(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = newNode;return;}newNode.next = head;head = newNode;}//出棧并返回出棧元素public int pop() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}int ret = head.val;head = head.next;return ret;}//獲取棧頂元素public int peek() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 棧為空!");}return head.val;}//獲取棧中的有效元素public int size() {int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}//檢測(cè)棧是否為空public boolean empty() {return head == null;}
}

    public static void main(String[] args) {Stack<Integer> stack0 = new Stack<>();//StackLinkedList<Integer> stack1 = new LinkedList<>();//LinkedListArrayDeque<Integer> stack2 = new ArrayDeque<>();//ArrayDeque}

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");while(!s1.empty()) {System.out.print(s1.pop() + " ");}System.out.println();System.out.println("=====LinkedList=====");while(!s2.isEmpty()) {System.out.print(s2.pop() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");while(!s3.isEmpty()) {System.out.print(s3.pop() + " ");}System.out.println();}

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");Iterator<Integer> it1 = s1.iterator();while(it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("=====LinkedList=====");Iterator<Integer> it2 = s2.iterator();while(it2.hasNext()) {System.out.print(it2.next() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");Iterator<Integer> it3 = s3.iterator();while(it3.hasNext()) {System.out.print(it3.next() + " ");}System.out.println();}

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");for(Integer x : s1) {System.out.print(x + " ");}System.out.println();System.out.println("=====LinkedList=====");for(Integer x : s2) {System.out.print(x + " ");}System.out.println();System.out.println("=====ArrayDeque=====");for(Integer x : s3) {System.out.print(x + " ");}System.out.println();}

class Solution {public boolean isValid(String s) {//補(bǔ)充代碼}
}

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();int i = 0;for(i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {if(stack.empty()) {return false;}else {char top = stack.pop();switch(top) {case '(':if(ch != ')') {return false;}break;case '[':if(ch != ']') {return false;}break;case '{':if(ch != '}') {return false;}break;}}}}if(!stack.empty()) {return false;}return true;}
}

class Solution {public int evalRPN(String[] tokens) {//補(bǔ)充代碼}
}

class Solution {public int evalRPN(String[] tokens) {Stack<String> stack = new Stack<>();for(int i = 0; i < tokens.length; i++) {String s = tokens[i];if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {int op2 = Integer.valueOf(stack.pop());int op1 = Integer.valueOf(stack.pop());switch(s) {case "+":stack.push(String.valueOf(op1 + op2));break;case "-":stack.push(String.valueOf(op1 - op2));break;case "*":stack.push(String.valueOf(op1 * op2));break;case "/":stack.push(String.valueOf(op1 / op2));break;} }else {stack.push(s);}}return Integer.valueOf(stack.pop());}
}

public class Solution {/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型一維數(shù)組 * @param popV int整型一維數(shù)組 * @return bool布爾型*/public boolean IsPopOrder (int[] pushV, int[] popV) {//補(bǔ)充代碼}
}

    public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j < popV.length && !stack.isEmpty() && stack.peek() == popV[j]) {stack.pop();j++;}}return stack.isEmpty();}

class MinStack {public MinStack() {}public void push(int val) {}public void pop() {}public int top() {}public int getMin() {}
}

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.peek() >= val) {minStack.push(val);}}public void pop() {if(stack.empty()) {return;}if(stack.pop().equals(minStack.peek())) {minStack.pop();}}public int top() {if(stack.empty()) {return -1;}return stack.peek();}public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}
}

棧、虛擬機(jī)棧和棧幀是Java虛擬機(jī)（JVM）中的三個(gè)相關(guān)但不同的概念，它們?cè)?strong>定義功能、數(shù)據(jù)結(jié)構(gòu)以及生命周期等方面存在明顯的區(qū)別：

1. 定義功能
   • Java棧：通常指的是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)程序執(zhí)行過程中的臨時(shí)數(shù)據(jù)。例如，方法的局部變量和返回地址等。
   • 虛擬機(jī)棧：特指JVM為每個(gè)線程分配的獨(dú)立內(nèi)存區(qū)域，用于存放棧幀，即方法調(diào)用的信息。它與線程同時(shí)創(chuàng)建和銷毀，主要支持方法的調(diào)用和執(zhí)行。
   • 棧幀：是虛擬機(jī)棧中的一個(gè)元素，對(duì)應(yīng)于正在執(zhí)行的每個(gè)方法。每個(gè)方法執(zhí)行時(shí)都會(huì)創(chuàng)建一個(gè)對(duì)應(yīng)的棧幀，包含局部變量表、操作數(shù)棧、動(dòng)態(tài)鏈接以及方法出口等信息。
2. 數(shù)據(jù)結(jié)構(gòu)
   • Java棧：作為一種數(shù)據(jù)結(jié)構(gòu)，其實(shí)現(xiàn)可以基于數(shù)組或鏈表，主要用于算法中數(shù)據(jù)的臨時(shí)存儲(chǔ)。
   • 虛擬機(jī)棧：作為JVM內(nèi)部的一個(gè)運(yùn)行時(shí)數(shù)據(jù)區(qū)，其內(nèi)部由多個(gè)棧幀組成，每個(gè)棧幀對(duì)應(yīng)一個(gè)方法調(diào)用的相關(guān)信息。
   • 棧幀：具有固定的數(shù)據(jù)結(jié)構(gòu)，包括局部變量表、操作數(shù)棧等，這些組成部分在編譯期間就已經(jīng)確定大小。
3. 生命周期
   • Java棧：根據(jù)程序邏輯進(jìn)行入棧和出棧操作，使用完畢后即可銷毀。
   • 虛擬機(jī)棧：與線程綁定，線程結(jié)束時(shí)對(duì)應(yīng)的虛擬機(jī)棧也會(huì)被銷毀。
   • 棧幀：在方法調(diào)用時(shí)創(chuàng)建，方法執(zhí)行完畢或異常終止時(shí)銷毀。
4. 存儲(chǔ)內(nèi)容
   • Java棧：可用于存儲(chǔ)任何類型的對(duì)象，如基本類型、引用類型等。
   • 虛擬機(jī)棧：專門用于存儲(chǔ)方法調(diào)用的相關(guān)信息，如局部變量、操作數(shù)等。
   • 棧幀：具體存儲(chǔ)了方法的局部變量表、操作數(shù)棧、動(dòng)態(tài)鏈接以及方法的返回地址等信息。
5. 應(yīng)用場(chǎng)景
   • Java棧：廣泛應(yīng)用于各類算法中，如深度優(yōu)先搜索、遞歸計(jì)算等。
   • 虛擬機(jī)棧：在JVM的執(zhí)行引擎中應(yīng)用，用于支持方法的調(diào)用和執(zhí)行。
   • 棧幀：直接關(guān)聯(lián)到每個(gè)方法的具體執(zhí)行過程，記錄了方法執(zhí)行所需的全部信息。

總的來說，Java棧、虛擬機(jī)棧和棧幀各自承擔(dān)著不同的功能和角色。Java棧是一個(gè)通用的數(shù)據(jù)結(jié)構(gòu)，而虛擬機(jī)棧和棧幀則是JVM內(nèi)部專門設(shè)計(jì)的機(jī)制，用于支持方法的調(diào)用和執(zhí)行。這三者共同協(xié)作，確保了Java程序能夠高效、安全地運(yùn)行。

隊(duì)列

基本概念

隊(duì)列是只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，其特點(diǎn)概括為 “先進(jìn)先出”，就像現(xiàn)實(shí)生活中的排隊(duì)一樣，在最早排隊(duì)的總是先出隊(duì)。

隊(duì)頭：進(jìn)行刪除操作的一端；隊(duì)尾：進(jìn)行插入操作的一端

注意區(qū)分棧和隊(duì)列。

隊(duì)列的模擬實(shí)現(xiàn)

了解了隊(duì)列的基本概念后，思考怎樣實(shí)現(xiàn)一個(gè)隊(duì)列？使用數(shù)組還是鏈表？

假設(shè)使用數(shù)組，通常我們會(huì)定義一個(gè)隊(duì)頭變量和隊(duì)尾變量，以方便入隊(duì)和出隊(duì)操作，入隊(duì)操作使用尾插，那么出隊(duì)操作就必須是頭刪。當(dāng)隊(duì)列不為空，每次出隊(duì)，隊(duì)頭變量要不斷地向后移動(dòng)，最終會(huì)導(dǎo)致數(shù)組的前半部分空間都被浪費(fèi)了，且隊(duì)列容量越來越少，所以簡(jiǎn)單的數(shù)組實(shí)現(xiàn)隊(duì)列是不方便的，如果要使用數(shù)組，那么最好實(shí)現(xiàn)成循環(huán)隊(duì)列（后面會(huì)講）。

一般來說，隊(duì)列使用鏈表實(shí)現(xiàn)，問題是入隊(duì)和出隊(duì)操作怎么實(shí)現(xiàn)？對(duì)于單鏈表，定義兩個(gè)引用，分別指向隊(duì)頭和隊(duì)尾，如果出隊(duì)采用尾刪，那么我們就得遍歷鏈表找到倒數(shù)第二個(gè)結(jié)點(diǎn)，讓它的next為null，效率較低，所以出隊(duì)采用頭刪，相應(yīng)地，入隊(duì)采用尾插，從而達(dá)到"先進(jìn)先出"的特點(diǎn)，并且保證了入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度都是O(1)。

但如果是雙向鏈表，那么就不需要考慮上面的問題，入隊(duì)出隊(duì)操作都是O(1)，我們這里采用雙向鏈表模擬實(shí)現(xiàn)一個(gè)隊(duì)列：

實(shí)現(xiàn)如下（雙向鏈表的頭刪、尾插操作，較為簡(jiǎn)單）：

public class MyQueue {//鏈表結(jié)點(diǎn)類static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//隊(duì)頭引用public ListNode tail;//隊(duì)尾引用private int size;//隊(duì)列有效元素個(gè)數(shù)//入隊(duì)public void offer(int data) {ListNode newNode = new ListNode(data);if(tail == null) {head = newNode;tail = newNode;size++;return;}tail.next = newNode;newNode.prev = tail;tail = newNode;size++;}//出隊(duì)并返回出隊(duì)元素public int poll() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 隊(duì)列為空!");}int ret = head.val;if(head == tail) {head = null;tail = null;}else {head.next.prev = null;head = head.next;}size--;return ret;}//獲取隊(duì)頭元素public int peek() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 隊(duì)列為空!");}return this.head.val;}//獲取隊(duì)列中的有效元素個(gè)數(shù)public int size() {return this.size;}//判斷隊(duì)列是否為空public boolean isEmpty() {return this.head == null;}}

循環(huán)隊(duì)列

前面提到，單純的數(shù)組實(shí)現(xiàn)隊(duì)列會(huì)導(dǎo)致空間的浪費(fèi)以及隊(duì)列大小的縮減，這時(shí)候引出了循環(huán)隊(duì)列的概念：

循環(huán)隊(duì)列是一種優(yōu)化的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，旨在解決順序隊(duì)列中存在的“假溢出”問題。

循環(huán)隊(duì)列采用了頭尾相接的環(huán)狀存儲(chǔ)結(jié)構(gòu)，通過將順序隊(duì)列的數(shù)組視為一個(gè)循環(huán)結(jié)構(gòu)，使得當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用時(shí)，新元素可以繼續(xù)從第一個(gè)位置開始存儲(chǔ)，形成一個(gè)邏輯上的環(huán)。這種設(shè)計(jì)極大地提高了存儲(chǔ)空間的利用率。

接下來我們就講解一下循環(huán)隊(duì)列的思想，關(guān)于循環(huán)隊(duì)列，我們要解決兩大問題：

當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用時(shí)，新元素怎樣繼續(xù)從第一個(gè)位置開始存儲(chǔ)?

怎樣區(qū)分循環(huán)隊(duì)列的 空 和 滿 兩個(gè)狀態(tài)？

【問題一】

在實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，我們?nèi)匀粫?huì)定義兩個(gè)"指針"：rear(指向隊(duì)尾，這個(gè)隊(duì)尾實(shí)際上是下一次入隊(duì)的位置，而不是指隊(duì)尾元素)、front(指向隊(duì)頭，即隊(duì)頭元素)，于是就可能會(huì)出現(xiàn)下圖的情況：

此時(shí)，存儲(chǔ)空間的最后一個(gè)位置已被使用，rear指向了最后位置后面的一個(gè)位置（此位置不能入新元素了），而此時(shí)由于進(jìn)行過出隊(duì)操作，數(shù)組的前面還有剩余空間可以使用，我們就得想辦法讓空閑空間被利用到，即讓rear重新回到數(shù)組開始的位置，怎么辦？

傳統(tǒng)的rear += 1肯定不行，我們采用這樣的語句 rear = (rear + 1) % len，len就是數(shù)組長(zhǎng)度。對(duì)于上面的情況，我們代入公式：

rear = (8 + 1) % 9，得到0，此時(shí)rear就重新回到了數(shù)組0下標(biāo)位置，這個(gè)公式在任何位置都是可以的。有了這個(gè)公式，front和rear就可以循環(huán)起來了。

【問題二】

怎樣區(qū)分循環(huán)隊(duì)列的 空 和 滿 兩個(gè)狀態(tài)？ 我們看如下圖表示的情況，為了突出循環(huán)，我們將數(shù)組在視覺上改成環(huán)：

圖1表示隊(duì)列為空，圖2表示隊(duì)列已滿，但是兩種情況下都是rear == front，怎么區(qū)分呢？

我們有三種解決方案：

• 定義成員變量size表示隊(duì)列中的有效元素個(gè)數(shù)：當(dāng)size和數(shù)組長(zhǎng)度相等時(shí)，表示滿；為0時(shí)表示空
• 定義一個(gè)boolean類型的標(biāo)記：最開始為false，當(dāng)入隊(duì)新元素后變?yōu)?code>true，當(dāng)出隊(duì)元素后rear == front，說明最后一個(gè)元素出隊(duì)了，將其置為false。這樣，當(dāng)rear == front && 標(biāo)記為false時(shí)，表示空，當(dāng)rear == front && 標(biāo)記為true時(shí)，表示滿
• 浪費(fèi)一個(gè)空間：即留出一個(gè)空間不放元素，當(dāng)rear == front時(shí)，表示空；當(dāng)(rear + 1) % len == front(下一個(gè)位置是隊(duì)頭)時(shí)，表示滿

解決完上面的兩個(gè)問題，我們以第二種解決方案動(dòng)手實(shí)現(xiàn)一下，（分析與注意事項(xiàng)在代碼后面）：

public class CircularQueue {public int[] elem;//數(shù)組private boolean flag;//標(biāo)記public int rear;//隊(duì)尾指針public int front;//隊(duì)頭指針public CircularQueue() {elem = new int[10];}public void offer(int data) {if(rear == front && flag == true) {System.out.println("隊(duì)列已滿");return;}elem[rear] = data;rear = (rear + 1) % elem.length;flag = true;}public int poll() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 隊(duì)列為空!");}int ret = elem[front];front = (front + 1) % elem.length;if(rear == front) {flag = false;}return ret;}public int peek() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 隊(duì)列為空!");}return elem[front];}public int size() {if(rear > front) {return rear - front;}else if(rear < front) {return rear + (elem.length - front);}else {return flag == true ? elem.length : 0;}}public boolean isEmpty() {return rear == front && flag == false;}
}

• rear實(shí)際上指向下一次入隊(duì)的位置，而不是指向隊(duì)尾元素；而front是指向隊(duì)頭元素
• offer方法最后一定要將標(biāo)記置為true
• poll方法內(nèi)部在front因出隊(duì)改變后，要檢查是否要將標(biāo)記置為false，即檢查該次出隊(duì)的是否是隊(duì)列中最后一個(gè)元素
• size方法考慮的就比較多了，循環(huán)隊(duì)列的思想導(dǎo)致rear和front的相對(duì)位置會(huì)發(fā)生變化，如代碼：分為rear > front、rear < front以及rear == front，特別注意第三種相等的情況，可能是滿了，也可能是空，這要根據(jù)標(biāo)記判斷。

不妨做個(gè)練習(xí)，嘗試使用問題二中的其他方案設(shè)計(jì)循環(huán)隊(duì)列：

class MyCircularQueue {public MyCircularQueue(int k) {}public boolean enQueue(int value) {}public boolean deQueue() {}public int Front() {}public int Rear() {}public boolean isEmpty() {}public boolean isFull() {}
}

給出以浪費(fèi)一個(gè)空間方案完成該題目的代碼：

class MyCircularQueue {public int[] elem;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;}if(rear == 0) {return elem[elem.length - 1];}return elem[rear - 1];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear + 1) % elem.length == front;}
}

• 既然要浪費(fèi)一個(gè)空間，那么我們?cè)跇?gòu)造方法初始化數(shù)組時(shí)要?jiǎng)?chuàng)建一個(gè)比參數(shù)大1個(gè)空間的數(shù)組，保證一部分測(cè)試用例能夠順利通過。
• Rear方法要求返回隊(duì)尾元素，由于我們的rear是隊(duì)尾元素之后的一個(gè)位置，所以我們必須向前一個(gè)位置找，這里就有一個(gè)特殊情況，當(dāng)rear == 0，此時(shí)不能減一，前一個(gè)應(yīng)該是數(shù)組最后一個(gè)下標(biāo)的位置，所以有如上代碼。

原題鏈接：622. 設(shè)計(jì)循環(huán)隊(duì)列 - 力扣（LeetCode）

雙端隊(duì)列

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

在集合框架中，雙端隊(duì)列對(duì)應(yīng)Deque接口，在實(shí)際工程中，使用Deque接口是比較多的，棧和隊(duì)列均可以使用該接口。

實(shí)現(xiàn)雙端隊(duì)列可以用LinkedList（鏈?zhǔn)綄?shí)現(xiàn)）或ArrayDeque（線性實(shí)現(xiàn)）：

    public static void main(String[] args) {Deque<Integer> deque1 = new LinkedList<>();//鏈?zhǔn)綄?shí)現(xiàn)Deque<Integer> deque2 = new ArrayDeque<>();//線性實(shí)現(xiàn)}

所以，到這里我們發(fā)現(xiàn)：

LinkedList可以作為鏈表、棧、(普通)隊(duì)列、雙端隊(duì)列

ArrayList可以作為棧、(普通)隊(duì)列、雙端隊(duì)列

集合框架中的隊(duì)列

集合框架中的隊(duì)列是Queue接口，Deque接口繼承自它，LinkedList和ArrayDeque都實(shí)現(xiàn)了該接口。

隊(duì)列的創(chuàng)建

我們可以通過ArrayDeque或者LinkedList創(chuàng)建一個(gè)隊(duì)列：

    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();//鏈?zhǔn)疥?duì)列Queue<Integer> queue2 = new ArrayDeque<>();//線性隊(duì)列}

隊(duì)列的方法

隊(duì)列的遍歷

    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();queue1.offer(1);queue1.offer(2);queue1.offer(3);queue1.offer(4);queue1.offer(5);System.out.println("=====for-each=====");for(Integer x : queue1) {System.out.print(x + " ");}System.out.println();System.out.println("=====迭代器=====");Iterator<Integer> it = queue1.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("=====while=====");while(!queue1.isEmpty()) {System.out.print(queue1.poll() + " ");}System.out.println();}

隊(duì)列的應(yīng)用及相關(guān)練習(xí)

用隊(duì)列實(shí)現(xiàn)棧

請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

class MyStack {public MyStack() {}public void push(int x) {}public int pop() {}public int top() {}public boolean empty() {}
}

【思路】

以畫圖+文字介紹：

現(xiàn)在我們要模擬出棧，如圖向棧中依次加入21、56、23、11，此時(shí)棧頂元素應(yīng)為11，出棧時(shí)要彈出11。

我們只有兩個(gè)隊(duì)列，所以讓不為空的隊(duì)列中的元素出隊(duì)，直到只剩1個(gè)元素，這個(gè)元素就是"棧頂"元素，將它"彈出"；此時(shí)如果再次入隊(duì)

此時(shí)，如果再添加新元素，繼續(xù)向非空隊(duì)列添加，而它就是新的"棧頂元素"，如果接著"出棧"，就重復(fù)上面的工作：將元素出隊(duì)到空隊(duì)列，直到只剩一個(gè)元素，彈出。

所以有：

入棧： 向非空隊(duì)列中添加元素，初始都為空時(shí)隨意選擇

出棧： 非空隊(duì)列將元素出到空隊(duì)列中，直到只剩下一個(gè)元素，這個(gè)元素就是棧頂元素，彈出

class MyStack {public Queue<Integer> q1;public Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size - 1; i++) {q2.offer(q1.poll());}return q1.poll();}else{int size = q2.size();for(int i = 0; i < size - 1; i++) {q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q1.poll();q2.offer(ret);}return ret;}else{int size = q2.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q2.poll();q1.offer(ret);}return ret;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}

原題鏈接：225. 用隊(duì)列實(shí)現(xiàn)棧 - 力扣（LeetCode）

用棧實(shí)現(xiàn)隊(duì)列

請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）

class MyQueue {public MyQueue() {}public void push(int x) {}public int pop() {}public int peek() {}public boolean empty() {}
}

【思路】

如上圖，如果不再添加新元素，按照?qǐng)D解思路出隊(duì)，得到序列：[10, 44, 31, 12, 101, 88, 36]，滿足隊(duì)列的先進(jìn)先出。

class MyQueue {public Stack<Integer> sIn;public Stack<Integer> sOut;public MyQueue() {sIn = new Stack<>();sOut = new Stack<>();}public void push(int x) {sIn.push(x);}public int pop() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.pop();}public int peek() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.peek();}public boolean empty() {return sIn.empty() && sOut.empty();}
}

原題鏈接：232. 用棧實(shí)現(xiàn)隊(duì)列 - 力扣（LeetCode）

完