栈OJ(C++)

1.栈OJ(C++)

1.1 最小栈

155. 最小栈

不是原生地去实现一个栈，而是自己去封装实现。但是它有额外的要求，提供一个getMin的函数，且这个getMin要求在常数时间完成。

很多同学的想法是设计一个最小值来记录最小值。这个想法其实是不合理的。

入栈的时候记录最小值，最小值出栈再遍历找最小。大家想想，如果这样设计的问题在哪？最大的问题在于我要是pop一下呢？最小值pop后再遍历找最小。问题是栈不支持遍历，有同学又说那我用一个vector存储数据，但是这样时间复杂度就变成O(n)了呀。

这里真正的实现方案是这样：不要用min来存储最小值，而是用两个栈。一个是正常存储数据的栈，一个是存最小值的栈。

st正常push数据，对于minst如果最小值更新，就push更新后的最小值，如果没有更新则push之前的最小值。删除就依次删除，就达到了O(1)的要求，以空间换时间。

大家想想当前设计的方案还有没有什么缺陷？或者说有没有优化的空间？

大家有没有发现这样重复存了好多5。那我们这里优化一下，不重复进，不用更新最小值我们都不进。那我们这里就不是你删除一个我删除一个了，st删除最小值时minst才删。但是这种写法要注意连续重复的最小值。所以对于minst，<=栈顶值的时候进数据。

代码实现：

class MinStack {
public:
    //自定义类型不需要我们写构造函数
    MinStack() {

    }
    
    void push(int val) {
		_st.push(val);
        // 最小栈进数据
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
		if(_st.top() == _minst.top())
            _minst.pop();
        
        _st.pop();
    }
    
    int top() {
		return _st.top();
    }
    
    int getMin() {
		return _minst.top();
    }
    
private:
    stack _st;
    stack _minst;
};
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

1.2栈的压入、弹出序列

JZ31栈的压入、弹出序列

这道题题意还是很简单的，它说给你一个入栈序列和一个出栈序列，看对不对得上。

我们知道出栈的顺序是有很多种的，所以这道题还是有点麻烦。

这道题其实没有什么好的解法，我们用一个栈来模拟：我这个入栈序列是不是能模拟出出栈顺序，能就符合true，模拟不出来就符合false。

模拟出栈顺序：

1、入栈序列先入栈。每次入栈后，栈顶和出栈序列比较。

a、如果能匹配，出栈序列往后出栈。

b、不能匹配：(1)说明这个数据可能还没入栈，继续入栈。

(2)入栈序列已经走到尾了，说明数据一定在栈中，只是顺序不对，出栈序列非法。

class Solution {
public:
    bool IsPopOrder(vector pushV,vector popV) {
        stack st;
        size_t popi = 0;
        for(auto e : pushV)
        {
            st.push(e);
            while(!st.empty() && st.top() == popV[pop1])
            {
                ++popi;
                st.pop();
            }
        }
        //return popi == popV.size();
        return st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3 逆波兰表达式求值

150. 逆波兰表达式求值

逆波兰表达式又叫后缀表达式，与之对应的还有中缀表达式，没有前缀表达式。

中缀就是运算符在两个数字或者表达式中间，但是中缀计算机没法计算，因为计算机是一个一个读取表达式的数据，要涉及优先级。

所以这个时候就会先转换为后缀表达式再进行计算，操作数的顺序还是不变，运算符要按照优先级排序。

但是这道题的难度没那么大，因为它直接就是给的后缀表达式，直接就可以进行运算。

后缀表达式运算很简单：

1.遇到操作数就入栈

2.遇到操作符，就取连续两个栈顶数据运算，运算结果继续入栈。

记住，先取出来的是右操作数，后取出来的是左操作数。因为左边先入栈右边后入栈，后进先出。这个地方区分左右是因为*和+不区分左右，/和-要区分左右。所以左右操作数的顺序不能乱。

我们拓展来讲一讲如何中缀转后缀：

1.遇到操作数，输出或者存储起来

2.遇到操作符先入栈，之后入栈就和栈顶操作符比较：

a、栈为空或者比栈顶优先级高入栈，之后继续重复1步骤。

b、比栈顶操作符优先级低/一样，出栈顶操作符。之后继续重复2步骤。

3.将栈中操作符全部出栈

class Solution {
public:
    int evalRPN(vector& tokens) {
		stack st;
        //&减少拷贝
        for(const auto& str : tokens)
        {
            if(str == "+" || str == "-"
               || str == "*" || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.pop();
                st.pop();
                
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '/':
                       st.push(left/right);
                       break;
                    default:
                        break;
                }
            }
            else
            {
                //字符串转整型为了符合switch语句
                st.push(stoi(str));
            }
        }
        return st.pop();
    }
};
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

   }
        else
        {
            //字符串转整型为了符合switch语句
            st.push(stoi(str));
        }
    }
    return st.pop();
}
1
2
3
4
5
6
7
8
9

};

1