【C++】STL——stack OJ练习

这篇文章我们来做几道stack相关的OJ题，练习一下stack的使用。

1. 最小栈

先来看第一道题——：最小栈

在这里插入图片描述

题目要求我们设计一个MinStack 类:

在这里插入图片描述

除了提供常见的几个接口之外，还要搞一个int getMin()，使得我们能够在常数时间O(1)内获取到栈中最小的元素。

思路分析

那要怎么做呢？

大家想这样行不行： 我们定义一个变量min来保存最小值，向栈里面入第一个元素时，就让min等于第一个元素，后续入栈新元素时，就和min比较判断是否需要更新min，小于就更新，大于就不动。 最终min的值就是最小元素。 听起来好像可以，但是： 别忘了，元素可以入栈，也可以出栈啊

在这里插入图片描述

比如现在栈里面入了这样几个元素，现在min的值更新为1，确实是当前栈中所有元素的最小值。 但是如果我们进行了pop呢？ 如果先把8pop掉了：

在这里插入图片描述

此时min的值还是1没问题，那继续pop呢？

在这里插入图片描述

1也被pop掉了，那min还能等于1 吗？ 所以这样不行。

那我们提供这样一种思路：

我们这样做： 实现的MinStack 类里有两个成员：

在这里插入图片描述

st就是我们正常定义的要使用的栈，min_st是一个辅助栈，用来帮助我们获取最小值。

那对于这两个栈，我们怎么操作呢？

举个栗子： 当第一个元素入栈的时候，比如入了一个5，那我们让两个栈都push一个5：

在这里插入图片描述

那此时栈中的最小值就是5。 然后再入一个4，最小值要更新，那min_st和st都push一个4（其实就是保证min_st栈顶的元素一定是最小值，最终我们就可以直接获取）：

在这里插入图片描述

然后如果再入一个6，那最小值不需要更新：

在这里插入图片描述

那min_st要push入元素吗？ 🆗，可以入也可以不入，但入得话一定不入6，因为入6的话栈顶元素就不是最小值了，所以如果选择入的话再入一个4：

在这里插入图片描述

那这样min_st栈顶的元素还是最小的。 再入的话一样的操作：

在这里插入图片描述

那我们在这里选择不入：

那就是这样：

在这里插入图片描述

当入栈的新元素小于等于min_st.top()（或第一次min_st为空）时 min_st才入栈这个元素。

那pop的时候怎么处理？

🆗，是不是pop的元素等于当前栈中的最小值即min_st.top()，min_st才进行pop，否则min_st就不pop。

AC代码

我们来写一下代码：

在这里插入图片描述

这是题目的初始代码模板。

首先问大家一个问题：

在这里插入图片描述

这是我们的成员变量嘛。 我们看到题目给的代码模板里面给了构造函数的接口：

在这里插入图片描述

但是，对于我们这种方法，还需要些构造函数吗？ 其实是不是根本都不需要构造函数啊，因为我们不写编译器默认生成，默认生成的构造函数什么特性： 编译器自动生成的构造函数不会对内置类型成员进行处理，而对于我们这里的stack（自定义类型）会怎么处理？ 是不是会去调用stack对应的默认构造函数。 所以这里完全不需要构造函数，另外对于什么拷贝构造、赋值重载是不是一样啊。 但是呢这里给了构造函数的接口，那编译器就不会默认生成了，那如果我们对于这个构造函数啥也不写，就留在这里，会不会出问题？ 🆗，是不是也没问题啊，因为它会走初始化列表，对于自定义类型也会去调它的默认构造

那剩下的接口就很好实现了，我们上面已经分析过了，这里就直接上代码了：

class MinStack {
public:
    // 不需要处理走初始化列表就可以搞定，
    // 直接删掉也可以，因为默认生成的就可以搞定
    MinStack() {
    }
    
    void push(int val) {
        st.push(val);
        if(min_st.empty()||val<=min_st.top())
            min_st.push(val);
    }
    
    void pop() {
        if(st.top()==min_st.top())
            min_st.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
private:
    stack<int> st;
    stack<int> min_st;

};

在这里插入图片描述

可以给大家看一下，直接删掉构造也可以：

在这里插入图片描述

拓展思维

现在给大家一个问题，还是上面那道题目：

在这里插入图片描述

如果是这种情况，那st有多少元素，minst也得有多少元素。 那能不能想个办法优化一下呢？ 🆗，我们可以考虑这样做： 我们的minst里面呢不在存最小值，而去存它的值和个数：

在这里插入图片描述

这样需要minst进行pop的话，把对应的个数- -就行了，怎么存个数呢，可以定义一个结构体：

在这里插入图片描述

那这样如果重复值比较多的话，可以节省一点空间。 就是这样一个思路，那代码我就不写了，大家有兴趣可以尝试写一下。

2. 栈的压入、弹出序列

链接: link

在这里插入图片描述

这道题其实就是给我们一个入栈序列，和一个出栈序列，让我们判断该出栈序列是否是可行的。

思路讲解

那怎么判断呢？

🆗，这道题比较简单的一种方法其实就是去模拟这个入栈出栈的过程。 举个栗子，就看题目给的这个测试用例：

在这里插入图片描述

入栈序列是1 2 3 4 5，出栈顺序是4 3 5 1 2。 那我们就模拟这个过程去判断啊： 首先上来第一步肯定先入一个数据，根据入栈序列第一个入栈的是1，那1入完之后有没有可能直接出栈啊，当然是有可能的，不过我们要看对应的出栈序列，那我们看到第一个出栈的应该是4，所以怎么办？

在这里插入图片描述

我们需要继续入栈数据，接着入栈2 3 4。

在这里插入图片描述

这是栈顶的元素和出栈序列第一个元素相等，所以出栈，4，3都顺利的出了

在这里插入图片描述

下一个要出栈的是5，但是5还没入栈，所以让5入栈，然后5直接出栈

在这里插入图片描述

然后现在栈里只剩1 2了，但是出栈序列是1 2，这显然不能办到，所以应该返回false（最终栈不为空)

在这里插入图片描述

当然如果是4 3 5 2 1，这样最终2 1也能顺利出栈，那就应该是true（最终栈为空)

AC代码

那对应的代码怎么写呢，我们来一起写一下：

在这里插入图片描述

给了我们两个vector，存储入栈pushV和出栈popV的序列。 那我们要模拟入栈出栈的过程，所以我们定义一个栈

在这里插入图片描述

然后我们要根据入栈序列去push数据，根据出栈序列去pop数据，所以我们要去遍历两个vector。

在这里插入图片描述

从下标0开始。 首先上来第一步肯定先入一个数据：

在这里插入图片描述

然后pushi++，下一次入第二个数据。 那第一个元素入了之后我们就要判断它是否需要出栈了，怎么判断？ 如果当前入栈的元素等于popV[popi]，是不是就要出栈。 但是每次出栈是不是有可能连续出多个元素啊，所以这应该是一个循环：

在这里插入图片描述

但是，我们这里上来直接获取栈顶元素去判断st.top()==popV[popi]，如果栈空了再去st.top()是不是就出问题了啊，所以，循环结束的条件是不相等或者栈出空了：

在这里插入图片描述

内层while循环结束之后如果后面还有元素未入栈，那就继续入栈，继续判断，当外层while循环结束是不是所有数据都判断完了啊。 那此时如果栈为空是不是就表明出栈序列是匹配的，全部出完了，如果不为空，就证明不匹配：

在这里插入图片描述

就写完了。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int pushi=0;
        int popi=0;
        while(pushi<pushV.size())
        {
            st.push(pushV[pushi++]);
            while(!st.empty()&&st.top()==popV[popi])
            {
                st.pop();
                popi++;
            }
        }
        return st.empty();
    }
};

在这里插入图片描述

3. 逆波兰表达式求值

链接: link

在这里插入图片描述

这道题目叫做逆波兰表达式求值，那什么是逆波兰表达式呢？ 我们可以一起来了解一下：

在这里插入图片描述

结合题目中给的测试用例给大家解释一下：

在这里插入图片描述

我们正常写的表达式，就比如题目中的这个：(2 + 1) * 3 这种写法叫做中缀算术表达式，即运算符写在操作数的中间，但是这种写法计算机是不能直接计算的，因为涉及运算符优先级的问题，比如1+2*3，应该先算*。 所以呢，这里就需要我们做一件事情，就是把它变成后缀表达式，其实就是根据优先级对表达式中的运算符排一个序，并且放到对应的操作数后面。 就比如题目中给的这个示例：((2 + 1) * 3)这个表达式对应的后缀表达式就是["2","1","+","3","*"]（题中是把它放到一个字符串数组中了）。 即1和2先进行后面的+，得到的结果再和3进行后面的*，得到最终结果。这样就直接从前往后算，不用考虑优先级的问题了。

那现在大家对逆波兰表达式应该有一个大致的了解了。

思路讲解

但是呢，单要解这道题目的话，其实很好搞：

我们只需要借助一个栈就搞定了。 具体怎么做呢？ 我们去遍历给的逆波兰表达式对应的字符串数组，如果对应的元素是数字，我们就让该操作数入栈，如果遇到操作符，我们就去取栈顶的前两个元素（并pop掉）进行对应的运算，然后将结果入栈，后续重复上述操作，最终栈里面唯一的那个元素就是要求的结果。 举个栗子：

在这里插入图片描述

遍历tokens，2 1入栈，接着遇到+，取出 1 2相加，得到结果3入栈，后面又是一个3入栈，接着遇到* ，取出3 3相乘，结果9入栈。 最终栈里面唯一的元素9就是结果。

AC代码

在这里插入图片描述

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str:tokens)
        {
            if(str=="+"||str=="-"||str=="*"||str=="/")
            {
                int right=st.top();
                st.pop();
                int left=st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

在这里插入图片描述

拓展：中缀表达式如何转后缀

那现在大家再来思考一个问题： 如果给我们一个中缀表达式，我们如何把它转换成对应的后缀表达式？

那中缀转后缀呢，也是需要借助一个栈，具体怎么做呢？ 比如现在有这样一个中缀表达式1+2*3-4 怎么把它转成后缀呢？ 🆗，我们还是从头去遍历这个表达式，如果遇到的是操作数，就输出；

在这里插入图片描述

如果遇到的是的是操作符，那这时要分情况进行分析： 如果此时栈为空，就让该操作符进栈；

在这里插入图片描述

在这里插入图片描述

如果遇到的是操作符，且此时栈不为空，则取栈顶的操作符与当前操作符比较，比较啥呢——优先级： 如果比栈顶操作符优先级高，就让该操作符进栈，为什么是进栈而不是拿它进行运算呢？ 因为后面有可能还有优先级更高的，所以先进栈。

在这里插入图片描述

那进栈之后呢？继续取下一个进行判断是操作数还是操作符。

在这里插入图片描述

如果比栈顶操作符优先级低或者相等，则出栈顶的操作符输出（即此时栈顶的这个操作符可以进行运算了）

在这里插入图片描述

然后再去判断栈是否为空，不为空再拿当前操作符和栈顶操作符比较，进行相应操作，为空就入栈。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

遍历结束后，如果栈不为空，将剩余操作符输出。

在这里插入图片描述

此时，就得到对应的后缀表达式了。

在这里插入图片描述

但是，如果是带括号的情况呢？

比如1+2*(4-5)+6/7，怎么处理？ 🆗，那如果按照上面的分析，1输出，+入栈，2输出，*的优先级比栈顶的+高，*也入栈，接着遇到了括号，怎么办？

在这里插入图片描述

如果不加括号的话，后面-比*优先级低，那应该让*先出栈运算，但是现在-在括号里面，所以-应该先运算，所以要认为-的优先级更高。 那我们可以怎么处理呢？当然这里的方法可能不止一种，我们可以这样做： 遇到(，我们认为它的优先级很低，但是我们不拿(做比较，直接让它入栈

在这里插入图片描述

然后遇到括号里的-，栈不为空，比较，因为我们说了认为(的优先级很低，所以-也入栈

在这里插入图片描述

那继续往后走遇到)怎么办？ 🆗，)呢我们也认为它的优先级很低，但是)我们要拿它去比较，因为我们认为)优先级很低，所以此时栈顶的-是不是就被成功弹出了。

在这里插入图片描述

然后栈不为空继续跟栈顶比，那此时) 就遇到 (了，拿这时怎么做呢？ 这时直接把(pop掉，不输出，然后跳过) 继续看下一个，因为后缀表达式优先级都排好了就不需要括号了。

在这里插入图片描述

拿继续往后走遇到+，栈不为空，跟栈顶比，比栈顶优先级低，栈顶操作符*输出，继续栈还不为空，继续比，优先级相等，出栈顶操作符+

在这里插入图片描述

然后栈空了，+入栈

在这里插入图片描述

然后遇到6入栈，遇到/优先级比+高，入栈，然后7输出

在这里插入图片描述

就遍历完了，再把剩余操作符输出

在这里插入图片描述

就得出结果后缀表达式了，大家可以验证一下。

在这里插入图片描述

当然处理括号可能有很多种方法，我们这里提供的只是其中一种，而且我们这种方法如果遇到有些极端的情况可能也不一定处理的了，可能还需要加一些特殊处理。 另外我们会发现就是遇到(是不是好像去开了一个新栈，在这个新栈里去处理括号里的这个子表达式，所以如果这样的问题也可以考虑递归去搞，每次遇到(就递归去处理这个子表达式，处理完回去递归调用的地方继续处理后面的。

这个问题大家了解一下。