致我最喜欢的栈-网络避难所

栈，先进后出，后进先出。

我最喜欢，是因为它实在太简单太好理解了，手搓AC的快感you know?

但也有要记忆的东西：

1.C++中stack 是容器么？
2.我们使用的stack是属于哪个版本的STL？
3.我们使用的STL中stack是如何实现的？
4.stack 提供迭代器来遍历stack空间么？

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

三个最为普遍的STL版本：

（1）HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
（2）P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
（3）SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

现在用的是SGI STL。

栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的，主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL中队列底层实现缺省情况下一样使用deque实现的。

不允许有遍历行为，不提供迭代器。

这就是栈！简单易懂的栈，这就不得不提今天手搓的简单爽题了：

20. 有效的括号

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路比较简单：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

最后：什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

学到一个技巧：每当左括号要入栈时，把它对应的右括号入了，这样匹配时只要看是否相等即可。

代码如下：

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;

        for(auto x:s){
            if(x=='('){
                st.push(')');//小技巧，化左为右
            }
            else if(x=='{'){
                st.push('}');
            }
            else if(x=='['){
                st.push(']');
            }
            else {
                if(!st.empty()&&x==st.top()){//这样只要看相等不相等就可以了
                    st.pop();
                }
                else
                return false;
            }
        }
        if(st.empty()){
            return true;
        }
        else
        return false;
    }
};

另一道比较简单的栈题：

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

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

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

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

需要注意的是：字符串从栈取出来是反的，需要倒转一下。

代码如下：

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result ;
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};

再有一题：

150. 逆波兰表达式求值

做这道题遇到了一些小问题：

在压入栈时，要把string类型转化为int类型。

这时候就要用到stoi() 函数。

stoi() 函数是 C++ 中的一个函数，用于将字符串转换为整数。它接受一个字符串参数，并返回相应的整数值。

int stoi (const string& str, size_t* idx = 0, int base = 10);

str：要转换的字符串。
idx：可选参数，用于存储转换过程中第一个无效字符的索引。
base：可选参数，指定数字的进制，默认为十进制。

以下为代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto x : tokens) {
            if(x != "+" && x != "-" && x != "/" && x != "*") {
                st.push(stoi(x)); // 将字符串转换为整数并压入栈中
            } else {
                int num2 = st.top(); // 注意先弹出的是第二个操作数
                st.pop();
                int num1 = st.top();
                st.pop();
                if(x == "+") {
                    st.push(num1 + num2);
                } else if(x == "-") {
                    st.push(num1 - num2);
                } else if(x == "/") {
                    st.push(num1 / num2);
                } else if(x == "*") {
                    st.push(num1 * num2);
                }
            }
        }
        return st.top();
    }
};