算法专题：栈

目录

1. 删除字符串中的所有相邻重复项

1.1 算法原理

1.2 算法代码

2. 844. 比较含退格的字符串

2.1 算法原理

2.2 算法原理

3. 基本计算器 II

3.1 算法原理 

3.2 算法代码

4. 字符串解码 

 4.1 算法原理

 4.2 算法代码

5. 验证栈序列

5.1 算法原理

5.2 算法代码

---

1. 删除字符串中的所有相邻重复项

. - 力扣（LeetCode）

1.1 算法原理

解法: 使用栈模拟, 实现"消消乐"(使用字符串模拟栈)

满足以下任一条件入栈:

1. 栈为空
2. s[i]和栈顶元素不相同

满足以下条件出栈:

1. s[i]和栈顶元素相同

1.2 算法代码

class Solution {public String removeDuplicates(String s) {// 字符串模拟栈结构StringBuilder stack = new StringBuilder();for(int i = 0; i < s.length(); i++) {char ch = s.charAt(i);int len = stack.length();// 栈为空 || ch 和栈顶元素不相同 => 入栈if(len == 0 || stack.charAt(len - 1) != ch) stack.append(ch);// ch 和栈顶元素相同 => 出栈else stack.deleteCharAt(len - 1);}return stack.toString();}
}

---

2. 844. 比较含退格的字符串

. - 力扣（LeetCode）

2.1 算法原理

本题思路与第一题相同, 

1. 当 s[i] 为 '#' 时, 出栈
2. 当 s[i] 不为 '#' 时, 入栈
3. 最后比较经过退格处理后的两个字符串是否相同

2.2 算法原理

class Solution {public boolean backspaceCompare(String s, String t) {return strOpera(s).equals(strOpera(t));}public String strOpera(String s) {StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '#') {// 出栈if(stringBuilder.length() >= 1) stringBuilder.deleteCharAt(stringBuilder.length() - 1);}else {// 入栈stringBuilder.append(ch);}}return stringBuilder.toString();}
}

---

3. 基本计算器 II

. - 力扣（LeetCode）

3.1 算法原理 

解法: 利用栈模拟运算过程

分类讨论:

1. s[i] 是运算符 => op = s[i] (记录运算符)

2. s[i] 是数字字符 , 把数字提取出来: tmp += s[i] - '0' (可能s[i + 1]仍为数字字符, 需循环处理)

1. op == '+' => stack.push(tmp);
2. op == '-' => stack.push(-tmp);
3. op == '*' => stack.push(stack.pop() * tmp);
4. op == '/' => stack.push(stack.pop() / tmp); 

3. 最终, 返回栈中所有元素的和 

注意:
需要处理空格字符!!

3.2 算法代码

class Solution {public int calculate(String ss) {char[] s = ss.toCharArray();int n = s.length;char op = '+';int tmp = 0;Stack<Integer> stack = new Stack<>();int i = 0;while(i < n) {if(s[i] == ' ') {i++;}else if(isOperator(s[i])) {op = s[i++];}else {tmp = s[i] - '0';while(i + 1 < n && !isOperator(s[i + 1]) && s[i + 1] != ' ') {tmp *= 10;tmp += s[i + 1] - '0';i++;}if(op == '+') stack.push(tmp);else if(op == '-') stack.push(-tmp);else if(op == '*') stack.push(stack.pop() * tmp);else stack.push(stack.pop() / tmp);i++;}}int ret = 0;for(int x : stack)  ret += x;return ret;}public boolean isOperator(char ch) {if(ch == '+' || ch == '-' || ch == '*' ||ch == '/') return true;return false;}
}

---

4. 字符串解码 

 . - 力扣（LeetCode）

 4.1 算法原理

解法: 栈模拟

1. 遇见数字 => 放入"数字栈"
2. 遇见 '[' => 将 '[' 后的字母字符串提取出来, 放入 "字符串栈"
3. 遇见 ']' => 取 "字符串栈" 栈顶元素和 "数字栈" 栈顶元素进行解析,并拼接到 "字符串栈" 栈顶元素后
4. 遇见单独的字符串 => 拼接到 "字符串栈" 栈顶元素后

 4.2 算法代码

class Solution {public String decodeString(String ss) {char[] s = ss.toCharArray();int n = s.length;Stack<Integer> intStack = new Stack<>();Stack<String> stringStack = new Stack<>();// 预处理 => 当栈为空时stringStack.push("");int i = 0;while(i < n) {if(s[i] > '0' && s[i] < '9') {int tmp = 0;while(i < n && s[i] >= '0' && s[i] <= '9') {tmp = tmp * 10 + (s[i++] - '0');}intStack.push(tmp);}else if(s[i] == '[') {i++;StringBuilder sb = new StringBuilder();while(i < n && s[i] >= 'a' && s[i] <= 'z') sb.append(s[i++]);stringStack.push(sb.toString());}else if(s[i] == ']') {StringBuilder sb = new StringBuilder();int x = intStack.pop();String str = stringStack.pop();while(x-- != 0) {sb.append(str);}stringStack.push(stringStack.pop() + sb.toString());i++;}else {StringBuilder sb = new StringBuilder();while(i < n && s[i] >= 'a' && s[i] <= 'z') sb.append(s[i++]);stringStack.push(stringStack.pop() + sb.toString());               }}return stringStack.pop();}
}

---

5. 验证栈序列

. - 力扣（LeetCode）

5.1 算法原理

解法: 使用 栈 模拟.

• 一边进栈, 一边判断是否需要出栈.

对 pushed 中的元素进行进栈操作, 将栈顶元素和 popped[i] 比较, 若不相等则一直进栈, 若相等则出栈, 并判断是否需要循环出栈.

5.2 算法代码

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack<>();int i = 0, n = popped.length;for(int x : pushed) {stack.push(x);while(!stack.isEmpty() && stack.peek() == popped[i]) {stack.pop();i++;}}return i == n;}
}

---

END