提示：多練才是王道,加油?(?????)?

---

1. 棧

棧是一種特殊的線性表,其只允許在固定的一端進行插入和刪除操作.進行數據插入和刪除的一端被稱為棧頂,另一端稱為棧底.棧中的元素遵循先進后出的原則.棧的三大核心操作:

1. push(E item):將元素壓入棧頂
2. pop():彈出并返回棧頂元素.如果棧為空,則拋出異常
3. peek():查看棧頂元素但不彈出.如果棧為空,則拋出異常

如圖所示,在棧頂進行入棧和出棧操作.

2. Java中棧的其中兩種實現方式

2.1 Stack類

java.util.Stack類,是Java最早提供的棧實現,官方已經不推薦使用了,但是在很多編程算法題中,Stack仍然被廣泛使用.

為什么不推薦?

Stack繼承自Vector:

• 性能差:Vector是線程安全的,所有方法都用synchronized關鍵字修飾,即使在單線程環境下也會帶來不必要的開銷.
• 設計缺陷:它繼承制Vector,導致它擁有了許多緋斬操作(如get(int index),insertElementAt),這破壞了棧的封裝性和"后進先出"的原則.

既然不推薦,為什么很多刷題平臺還是廣泛使用呢?

• 歷史關心 & 教學傳統:很多算法教程、大學課程和早期的編程書籍都是基于Stack類來講解棧概念的。這些教學材料有很強的延續性，導致一代代的程序員在學習階段就習慣了使用Stack。
• 要求不同:在算法題中,通常只關心核心邏輯的正確性,而不是生產級別的代碼質量.Stack的線程安全開銷和設計缺陷在算法題的輸入規模下幾乎可以忽略不計,不會導致超時.
• 功能足夠:對于求解一道算法題Stack提供的 push, pop, peek, empty 方法已經完全夠用了。雖然它有多余的方法，但只要你不去用它們，就不會造成問題。

好了言歸正傳,現在我們來看一下這個Stack:

通過源碼可以看到,Stack的核心方法就以下幾種:

也就是:

方法	功能
Stack()	構造一個空的棧
E push(E e)	將e入棧,并返回e
E pop()	將棧頂元素出棧并返回(刪除)
E peek()	獲取棧頂元素(瞄一眼,不刪除)
int size()	獲取棧中有效元素個數
boolean empty()	檢測棧是否為空

2.1.1 Stack的模擬實現

public class MyStack {//底層使用整形數組elem啦存儲元素public int[] elem;//usedSize兩個作用:①表示當前棧中元素個數②始終指向棧頂元素的下一個位置,下一個入棧元素的下標public int usedSize;//構造方法將數組初始化為大小為10的整型數組public MyStack() {this.elem=new int[10];}//壓棧操作public void push(int val) {if(isFull()) {//擴容,使用Arrays.copyOf方法,將新數組長度擴容為原來的2倍elem= Arrays.copyOf(elem,2*elem.length);}elem[usedSize++]=val;}public boolean isFull() {return usedSize==elem.length;}//出棧操作public int pop() {if(empty()) {return -1;//這里更合適做法是拋出一個異常}int toPop=elem[usedSize-1];//保留棧頂元素usedSize--;//邏輯刪除return toPop;//最后返回棧頂元素}public boolean empty() {return usedSize==0;}//查看棧頂元素,邏輯與pop一致,除了不用usedSize--public int peek() {if(empty()) {return -1;//這里更合適做法是拋出一個異常}int toPeek=elem[usedSize-1];return toPeek;}
}

2.2 LinkedList類

上面Stack類的底層是動態數組,所以也叫順序棧,用鏈表能實現棧嗎?—可以.

LinkedList是雙向鏈表,天然實現了棧所需的所有操作,并且效率很高.因此完全可以基于LinkedList實現棧.

順著push和pop方法點過去可以看到兩者的源碼:

可以看到,push調用的是addFirst方法,即頭插;pop調用的是removeFirst方法,即頭刪,因此用LinkedList實現的棧棧頂在鏈表的頭,不是尾.

對比使用Stack類(在數組尾部進行入棧出棧,時間復雜度為O(1)):

• 這樣入棧出棧操作也很高效,只涉及改變幾個指針的指向,時間復雜度同為O(1).
• 然而數組滿后需要昂貴的擴容操作(申請新數組,復制所有元素),雙向鏈表無擴容開銷,且不會造成內存浪費.

3. 典型習題講解

3.1 逆波蘭表達式求值

150. 逆波蘭表達式求值 - 力扣（LeetCode）

這是一個棧的典型使用場景之一.求解這道題需要先弄明白逆波蘭表達式的計算原理.

首先,什么是逆波蘭表達式?

也叫后綴表達式,核心特點是運算符位于其對應的兩個操作數之后.我們日常接觸的都是中綴表達式,比如:a+b*c+(d*e+f)*g,其對應的后綴表達式為:abc*+de*f+g*+.

這是怎么轉化的?有人總結出了以下步驟:

1. 先將中綴表達式的每個運算周圍用括號括起來:a+b*c+(d*e+f)*g->((a+(b*c))+(((d*e)+f)*g))
2. 然后將每個運算符都向右移到包裹它的括號右邊:((a+(b*c))+(((d*e)+f)*g))->((a(bc)*)+(((de)*f)+g)*)+
3. 最后將括號全部去掉:((a(bc)*)+(((de)*f)+g)*)+->abc*+de*f+g*+

可以明顯看到后綴表達式的一個特征:沒有括號,第3步將括號全部去掉了.

那為什么需要后綴表達式?

中綴表達式對人類很友好,但是對于計算機卻很麻煩:需要處理運算符優先級(如乘除優先于加減)和加括號來確定運算順序,這個過程比較復雜.

后綴表達式完美地解決了這個問題:

• 無需括號
• 無需優先級規則
• 只需要一個棧即可輕松完成計算.

那它的計算原理是什么?

1. 首先創建一個棧,準備將后綴表達式按照一定規律從左向右依次壓入:
   • 若遇到數字,壓入棧中,一直是數字就一直壓
   • 若遇到的是運算符(+ - * /),則出棧兩次,第一次的是右操作數,第二次是左操作數,運算過后,將結果繼續壓入棧中
   • 循環上述兩個步驟,直至后綴表達式被掃描完
2. 掃描完后,棧中剩下的即為整個表達式的運算結果

然后思路就很清晰啦:

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for(int i=0;i<tokens.length;i++) {String tmp=tokens[i];if(isOperation(tmp)) {int num2=stack.pop();//右操作數int num1=stack.pop();//左操作數switch(tmp) {case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}else {Integer num=Integer.valueOf(tmp);//將字符轉為整型stack.push(num);}}return stack.pop();//遍歷完數組,棧中剩下的就是運算結果}//判斷是否是表達式public boolean isOperation(String s) {//引用類型進行比較要用equals,不能用==if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;}else {return false;}}
}

3.2 匹配括號

20. 有效的括號 - 力扣（LeetCode）

該題目要求第一次出現的右括號必須與它的前一個括號匹配,形狀相同,朝向相反.

解題思路:創建一個棧,將字符串從左到右依次便利:

• 若是左括號,就痛快入棧;
• 若是右括號,彈出棧頂元素與其匹配:
  • 匹配的話(形狀相同,朝向相反),就麻溜"出棧走人",然后下一位;
  • 不匹配的話,直接返回false
• 遍歷完了就只用看下棧空不空,空了說明全部都匹配上了,返回true;非空返回false.

思路清晰,coding~

class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();for(int i=0;i<s.length();i++) {char ch=s.charAt(i);if(ch=='{' || ch=='[' || ch=='(') {//ch為左括號,入棧stack.push(ch);}else {//ch為右括號if(stack.empty()) {return false;//若是遇到了落單的右括號,直接false}else {char tmp=stack.peek();if(tmp=='{' && ch=='}' ||tmp=='[' && ch==']'|| tmp=='(' && ch==')' ) {stack.pop();}else {return false;}}}}return stack.empty();}
}

注意:判斷Stack是否為空有兩個方法isEmpty()和empty()(empty是Stack自己聲明的,isEmpty則是Sytack從其父類Vector繼承而來的),在idea上兩者都能用,但是在力扣上用isEmpty()會報錯,這可能是因為力扣的版本或環境問題,也可能是提供的Stack類是一個預定義的,模擬的類,就像2.1.1的模擬實現一樣.

3.3 合理彈出序列

棧的壓入、彈出序列_牛客題霸_牛客網

這種題型在選擇題中常見,但是若是要將寫選擇題那種有點"只可意會不可言傳"的感覺轉為代碼,還是有點差距的~

這題的思路是:定義兩個下標,分別遍歷入棧和出棧序列,假設i遍歷入棧序列,j遍歷出棧序列;

• 定義一個棧,將i對一個元素入棧,然后將i與j下標對應的值進行比較,若不相等,i++,j不動
• i一直++,直到i,j對應值相等,此時,將i對應元素出棧,j++
• 若是棧頂元素與j對應元素一直相等,則一直出棧,j也一直++;不相等了,再重復上一步操作
• 最后i和j都會遍歷完,若此時棧為空,則說明該出棧序列是合理的,反之不合理.

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

3.4 最小棧

155. 最小棧 - 力扣（LeetCode）

題目明確要求在常數時間內檢索到最小元素,若只定義一個棧,那么尋找最小元素勢必要遍歷一遍stack,時間復雜度為O(n),不符合要求,因此,此題要建立兩個棧:

1. 一個普通棧,正常壓入彈出元素,每次使用push,pop,top這三個方法時均要對這個普通棧進行操作.
2. 還有一個存放最小元素的棧,該棧的壓入彈出不能那么隨心所欲了:
   • 元素push時要先與該棧棧頂元素比較,只有不大于棧頂元素才能壓入棧中,否則便不能;
   • pop時要將棧頂元素與普通棧pop掉的元素比較,若相等,才能pop掉
   • top不能操作該棧
   • getMin只能操作該棧,用于peek該棧的棧頂元素

coding~

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