1、括號匹配問題

. - 力扣（LeetCode）

1.1 思路分析

根據棧的先進后出原則，我們可以這樣解決問題：

遍歷字符串，遇見左括號就將左括號push入棧；遇見右括號就pop出棧，將出棧的元素和該右括號比較是否匹配，若匹配則繼續遍歷并比較，若不匹配則直接返回false。細分為以下幾種情況：

1.匹配（左右括號數量相同且匹配）：字符串遍歷完，且棧為空（右括號與左括號數量相等，且均匹配），則說明括號匹配，返回true。

2.不匹配（括號不匹配）：遍歷到的右括號和出棧的左括號比較是否匹配，一旦不匹配，立即返回false。

3.不匹配（左括號數量多）：當字符串遍歷完后，發現棧還不為空，則說明左括號多，不匹配。

4.不匹配（右括號多）：遍歷遇見右括號需將棧頂的左括號出棧，若要出棧時棧為空，則說明右括號多，不匹配。

1.2 代碼

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 == '[') {stack.push(ch);}else {//遍歷到的為右括號 進入else//若棧為空 則說明右括號多 立即返回falseif(stack.isEmpty()) {return false;}//若棧不為空 則pop出棧 比較是否匹配 char ch2 = stack.pop();switch(ch) {//使用switch語句比較是否匹配 一旦不匹配 立即返回falsecase ')':if(ch2 != '(') {return false;}break;case ']':if(ch2 != '[') {return false;}break;case '}':if(ch2 != '{') {return false;}break;}}}//遍歷完成且棧為空 則說明匹配 if(!stack.isEmpty()) {return false;}return true;}

2、棧的彈出、壓入序列

2.1 思路分析

以i遍歷pushV,每次都將將i下標的元素入棧，再將棧頂元素和j下標元素比較，
若相等：則出棧，j++，i++
不相等：則i++，j保持原位

注意：j++后，j下標與棧頂元素可能依然相等，此時要連續出棧。即j變化后，要繼續和棧頂元素比較。

• i遍歷完成，且j也遍歷也完成（此時棧肯定為空），說明出棧序列匹配
• 若i遍歷完成后，j還沒有遍歷完成（棧不為空），則說明出棧序列不匹配
  因為只有棧頂元素和j下標元素相等時，才會出棧，j++

?2.2 代碼

public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {//每次循環都會將pushV中i下標的元素入棧stack.push(pushV[i]);//因為j++后，元素可能連續出棧，所以要while循環//出棧后，棧可能出現空的情況，!stack.isEmpty()，防止出現空指針異常while (!stack.isEmpty() && stack.peek() == popV[j]) {j++;//若j下標和棧頂元素相同，則出棧stack.pop();}}//i遍歷完成，若此時j也遍歷完成（j == popV.length）,則說明出棧序列匹配return j == popV.length;}

3、逆波蘭表達式（后綴表達式）求值

. - 力扣（LeetCode）

3.1 逆波蘭表達式的定義

逆波蘭表達式，也稱為后綴表達式，是一種表達式的表示方法，其中運算符位于操作數之后。

后綴表達式由中綴表達式轉化而來，可以實現表達式的求值和計算，提高了計算機內存訪問的效率。而中綴表達式就是我們平時做運算的表達式。

那么如何將中綴表達式轉換為后綴表達式？

1. 從左向右，以先乘除后加減的次序加括號
2. 將括號中的相鄰兩項的運算符拿到括號的后面
3. 去掉所有括號

?3.2 后綴表達式如何求值（思路分析）

我們拿到后綴表達式后，

1. 遍歷表達式，若是非操作符元素（數字元素），則入棧
2. 若遇到操作符元素，則出棧兩次，將第一次出棧的元素val2作為該操作符的右操作數，將第二次出棧的元素val1作為該操作符的左操作數，接著將所得結果入棧。
3. 繼續遍歷，并重復以上操作
4. 遍歷完成后，棧中只剩一個元素，該元素就是后綴表達式的值。

?3.3 代碼

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {String str = tokens[i];if (!isOperator(str)) {//如果不是是操作符//則元素入棧int val = Integer.parseInt(str);//將字符串轉化為整型stack.push(val);} else {//如果是操作符//則彈出棧頂兩個元素//計算結果，并將結果入棧int val2 = stack.pop();int val1 = stack.pop();if (str.equals("+")) {stack.push(val1 + val2);}if (str.equals("-")) {stack.push(val1 - val2);}if (str.equals("*")) {stack.push(val1 * val2);}if (str.equals("/")) {stack.push(val1 / val2);}}}//遍歷完成后，棧中還有一個元素//該元素就是后綴表達式的值return stack.pop();}//判斷該元素是否為操作符private boolean isOperator(String str) {if (str.equals("+") || str.equals("-")|| str.equals("*") || str.equals("/")) {return true;}return false;}
}

4、最小棧

. - 力扣（LeetCode）

4.1 思路分析

題目要求我們在O（1）內找到棧中的最小值，

而在Java已有的一個棧中我們只能通過遍歷找最小值，時間復雜度為為O（n）?。

所以，我們可以建立兩個棧，一個棧dataStack用來存儲元素，另一個棧minStack的棧頂存最小值。

1. minStack棧頂存儲最小值數據 每次dataStack添加新數據時，和minStack棧頂元素比較，若<= ，則push入棧（一定要 <= ，因為dataStack中可能有多個相同的最小值，保證pop一次后，minStack依然存儲著最小值）
2. 當minStack為空時，那么dataStack添加的元素（第一次入棧的元素）一定為最小值
3. 當dataStack彈出元素時，我們需要判斷這個元素是否為minStack的棧頂元素（最小值），若是，也需要彈出minStack的元素

也就是說，?minStack的棧頂元素，就是dataStack的最小值。

4.2 代碼

class MinStack {Stack<Integer> dataStack;//存儲所有數據Stack<Integer> minStack;// 棧頂存儲最小值數據 每次添加新數據時，和minStack棧頂元素比較，若<= ，則push進minStackpublic MinStack() {dataStack = new Stack<>();minStack = new Stack<>();}public void push(int val) {dataStack.push(val);if (minStack.isEmpty()) {// 當minStack為空時，直接push進minStackminStack.push(val);} else {// 一定要有else 否則，minStack空時，同一個元素會在minStack中push兩次if (val <= minStack.peek()) {// 一定要 <= ，因為dataStack中可能有多個相同的最小值，保證pop一次，minStack依然存儲著最小值minStack.push(val);}}}public void pop() {// 操作總是在 非空棧 上調用int val = dataStack.pop();// 當dataStack棧頂元素為最小值時，也要彈出minStack的棧頂元素if (val == minStack.peek()) {minStack.pop();}}public int top() {return dataStack.peek();}public int getMin() {// minStack的棧頂元素即為最小值return minStack.peek();}
}