算法中栈的应用

栈

练习1：删除字符串中的所有相邻重复项

练习2：比较含退格的字符串

练习3：基本计算器II

练习4：字符串解码

栈

栈是一种常见的数据结构，遵循先进后出（LIFO）的原则（最后进入栈的元素将被最先移出）

栈有两种基本操作：压栈（push）和出栈（pop）

压栈：将元素放入栈顶，同时栈顶指针向上移动。

出栈：将栈顶元素移出，并将栈顶指针向下移动。

栈在算法题目中的应用非常广泛，能够简化问题的处理过程，提高算法的效率，在解决算法题目时，合理使用栈能够帮助我们更好的解决问题

接下来，我们通过几道练习来进一步体会栈在算法中的应用

练习1：删除字符串中的所有相邻重复项

题目链接：

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题目描述：

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

思路分析：当出现两个相邻且相同的字母时，需要将其删除。接下来，我们模拟删除字符串中所有相邻重复项的过程：

若当前字母与与前一位字母相同时，需要将当前字母和前一位字母都删掉，然后再继续遍历下一个字母，若我们使用容器来存储符合条件的字母：

此时，我们可以发现：每次放入元素之前，先与最后一个元素相比较，若相同，则放入；若不同，则不放入，且删除最后一个元素。此时，后放入的元素先拿出，满足后进先出，因此，我们可以使用栈来帮助我们实现相邻重复项的删除

我们可以直接使用 Java 提供的 Stack 类，但由于这道题较为简单，因此，我们可以直接使用数组来模拟实现栈：

若栈为空，直接入栈

若栈不为空，比较当前元素和栈顶元素，若相同，弹出栈顶元素；若不同，将当前元素放入栈中

代码实现：

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer ret = new StringBuffer();//用数组来模拟栈结构
        char[] chs = s.toCharArray();
        for(char ch: chs){//遍历数组
            if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1)){
                ret.deleteCharAt(ret.length() - 1);//出栈
            }else {
                ret.append(ch);//进栈
            }
        }
        return ret.toString();
    }
}

练习2：比较含退格的字符串

题目链接：

844. 比较含退格的字符串 - 力扣（LeetCode）

题目描述：

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'

思路分析：

# 代表退格符，当出现 # 时，删除 # 前的字符。因此，我们同样可以使用栈来帮助我们删除字符。我们可以将给定的字符串中的退格符和需要删除的字符都删除，得到字符串的最终结果，然后再比较两字符串得到的结果是否相同，同样的，我们也可以使用数组来实现栈

我们遍历字符串：

若当前字符是退格符，且栈不为空，弹出栈顶元素

若当前字符是普通字符，将当前字符入栈

代码实现：

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return changeStr(s).equals(t);//比较两字符串删除退格和相应字符后是否相同
    }
    
    public String changeStr(String s){
        StringBuffer ret = new StringBuffer();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch != '#'){//普通字符，入栈
                ret.append(ch);
            }else{
                if(ret.length() > 0){//若栈不为空，出栈
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }
}

练习3：基本计算器II

题目链接：

227. 基本计算器 II - 力扣（LeetCode）

题目描述：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

思路分析：

由于乘除运算优于加减运算，因此要先计算表达式中的乘除运算。因此，我们可以先计算表达式中的乘除，然后将得到的结果放回原位置，最后进行加减运算，即可得出结果：

因此，我们可以使用一个栈来保存进行乘除运算后的值：

当运算符为加号时，直接将加号后的元素num放入栈中

当运算符是减号时，我们将减号后的元素num的相反数放入栈中（放入 -num），这样，当我们在最后进行加减运算时，只需要进行加法运算，就可以得出结果

当运算符是乘号时，我们将栈顶元素弹出，并与乘号后元素num相乘，然后再将结果放入栈中

当运算符是除号时，我们将栈顶元素弹出，与除号后元素num相除，然后再将结果放入栈中

由于 s是一个有效表达式，因此，我们不用考虑当运算符为乘除时，栈为空的情况

但由于第一个元素前无运算符，因此，我们可以将其之前的运算符设置为 +，这样，就可将其直接放入栈中

在提取运算符之后的数字时，若数字为 123 或 45 等多位数，我们需要将数字全部提取出来，此时应该如何提取呢？

我们将num初始化为0，然后向后遍历，每遍历到一个数字k，让num * 10 + k，这样，就可以提取出每一位数字（例如：需要提取 123，当遍历到1时，num = 0*10 + 1，遍历到2时，num = 1*10 + 2，遍历到3时，num = 12*10 + 3）

因此，我们使用变量op来记录每个数字之前的运算符，op初始化为 + （让第一个数字直接入栈），然后遍历字符串：

若op为 + ：数字入栈

若op为 - ：数字的相反数入栈

若op为 * 或 /：弹出栈顶元素，并与数字进行计算，然后将计算结果压入栈中

注意：由于提示中告诉我们表达式中存在空格，因此，我们要注意处理空格

代码实现：

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        char op = '+';
        int n = s.length(), i = 0;
        while(i < n){//遍历字符串
            if(s.charAt(i) == ' '){//若当前字符为空格，继续向后遍历
                i++;
            }else if(Character.isDigit(s.charAt(i))){//若当前字符为数字，提取数字
                int num = 0;
                while(i < n && Character.isDigit(s.charAt(i))){
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                //根据op进行操作
                if(op == '+') stack.push(num);
                else if(op == '-') stack.push(-num);
                else if(op == '*') stack.push(stack.pop() * num);
                else stack.push(stack.pop() / num);
            }else{//若当前字符为运算符，更新op
                op = s.charAt(i);
                i++;
            }
        }
        int ret = 0;
        //将所有元素弹出，相加，计算最终结果
        while (!stack.isEmpty()) {
            ret += stack.pop();
        }
        return ret;
    }
}

练习4：字符串解码

题目链接：

394. 字符串解码 - 力扣（LeetCode）

题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

思路分析：题目要求我们出现 k[str]时，将[]中的字符串str重复k次，因此：

当出现数字时，需要提取数字

当出现 [ 时，需要提取 [ 后的字符串

当出现 ] 时，需要将 [] 中的字符串重复k次

因此，我们可以使用 两个栈 来分别保存数字和字符串：

当出现数字时，提取数字，放入保存数字的栈nums中（提取方法与练习3：基本计算器II 中提取数字相同）

当出现 [ 时，将[ 后的字符串放入保存字符串的栈stack中

当出现 ] 时，将 stack 的栈顶元素和 nums 栈顶元素弹出，进行复制，然后再将复制结果放入stack中

但字符串中可能出现嵌套的情况（如：3[a2[c]]）或普通字符（即不用进行重复操作的字符，如：ab2[c]中的ab）

如何处理嵌套呢？

以3[a2[c]]为例，若当前字符为[，我们提取 [ 后的字符串a，放入stack中，继续遍历，

此时出现数字，提取数字3，放入nums中，

然后又遇到 [，此时提取字符串c，放入stack 中，

当遇到 ] 时，我们将stack栈顶元素c弹出、nums栈顶元素2弹出，将c重复2次，然后将其拼接到此时的栈顶元素a后，即将 cc 拼接到 a 后，然后将 acc 放入栈中，

当遇到 ] 时，将stack栈顶元素acc弹出、nums栈顶元素3弹出，将acc重复3次，此时stack为空，直接将其压入stack中

同理，我们以类似的思路来处理普通字符，当出现普通字符时，若stack为空，我们直接将其放入栈中；若栈不为空，我们将其拼接到栈顶元素后

由于我们在每次将字符串进行复制后进行拼接，或拼接普通字符时都有判断stack是否为空，因此，我们可以先在栈stack中存放一个空串，这样，就不需要每次都判断字符串是否为空了

代码实现：

class Solution {
    public String decodeString(String s) {
        char[] chs = s.toCharArray();
        Stack<StringBuffer> stack = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        int i = 0, n = chs.length;
        stack.push(new StringBuffer());
        while(i < n){
            if(chs[i] >= '0' && chs[i] <= '9'){//当前字符为数字，提取数字，并将其放入栈nums中
                int num = 0;
                while(i < n && (chs[i] >= '0' && chs[i] <= '9')){
                    num = num * 10 + (chs[i] - '0');
                    i++;
                }
                nums.push(num);
            }else if(chs[i] == '['){//当前字符为[,提取字符串，并将其放入栈stack中
                i++;
                StringBuffer tmp = new StringBuffer();
                while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                    tmp.append(chs[i]);
                    i++;
                }
                stack.push(tmp);
            }else if(chs[i] == ']'){//当前字符为 ] 将k个该字符串拼接到栈顶元素后
                StringBuffer tmp = stack.pop();
                int k = nums.pop();
                while(k-- > 0){
                    stack.peek().append(tmp);
                }
                i++;
            }else{//当前字符为普通字符，将所有普通字符拼接到stack栈顶元素后
                StringBuffer tmp = new StringBuffer();
                while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                    tmp.append(chs[i]);
                    i++;
                }
                stack.peek().append(tmp);
            }
        }
        return stack.peek().toString();
    }
}