栈的三道oj【C++】

这里就挑了三道题用来熟悉栈

最小栈

力扣链接

咱们已经是高贵的C++使用者了，不用像C语言一样从头开始造轮子了

这里我们调用了stack后，就会发现这道题主要的问题就是getMin的功能。

思路

按照一般人的思路可能会想在成员变量中添加一个最小值的成员：min
每次进栈和出栈来比较是否与值相同，进行更新。

但是在实现的过程中就会发现这个思路并不可行
因为：
**
当最小值出栈后，那第二个最小值不知道填什么
这个问题的最主要原因是栈无法遍历**

所以这里就要用新的思路了：

双栈：
创建一个用来放最小值的栈

1.每次插入都进行比较，看看是否是比栈顶小，这样就可以保证栈顶一直是最小值

2.注意这里相同大小的最小值也要进行放入，防止有相同的重复最小值

3.出栈时：与最小栈的栈顶进行比较，看看是否等于，如果一样就出最小栈的栈顶

思路大致是这样，实现就直接放在下面了。

解决代码

class MinStack {
public:
    void push(int val) {
        _stack.push(val);
        if(_stack_min.empty()||val<=_stack_min.top())
        {
            _stack_min.push(val);
        }
    }
    void pop() {
        if(_stack.top()==_stack_min.top())
            _stack_min.pop();
        _stack.pop();
    }
    
    int top() {
        return _stack.top();
    }
    
    int getMin(){
        return _stack_min.top();
    }
    
    private:
    stack<int> _stack;
    stack<int> _stack_min;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

栈的压入弹出序列

力扣链接

思路

这道题主要就是考：如何判断出栈的顺序的可行性的判断。

这里我们随便来串数字进行判断

那我们来看一下我们的判断方法：

经过上图我们知道了我们判断一个出栈顺序，是否符合入栈顺序的基本过程

总结来说就是模拟入栈和出栈

所以这边我们可以把过程给归纳一下了：
1.不停入栈，直到和出栈顺序的元素相同
2.然后将出栈元素出栈，之后继续不停入栈，再知道和出栈队列元素相同
3.判断入栈元素是否无了，跳出循环
4.判断栈是否为空，如果为空栈，这样的话证明结论是是可行的，反之则不行。

解决代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        // write code here
        stack<int> _st;
        int push=0;
        int pop=0;
        
        while(push<pushV.size())
        {
            
            _st.push(pushV[push++]);
            
                while(!_st.empty()&&_st.top()==popV[pop])
                {
                _st.pop();
                pop++;
                }
                
        }
        return _st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

逆波兰表达式

力扣链接

这里首先来解释一下为什么会有这个表达式的出现：

对于计算机来说，用中缀的表达式十分不友好。
因为如果读取两个数和一个符号后，还不能马上进行计算

因为你无法确定后面有没有更高优先级的运算符。

思路：

这里其实我们看到思路也很简单其实，没有什么复杂的。

这里就拿这个队列来举例子。

接下来就是重复就行了。。

思路还是很明确的。

解决代码

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

            }
        }
        return _st.top();
    }
private:
    stack<int> _st;

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61