👉stack 的介绍和使用👈
stack 的介绍
stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque。
stack 的使用
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
1. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
思路：最小栈MinStack包含两个栈：一个是存储插入元素的栈_st，另一个是存储最小值的栈_minst。插入元素时，必须向栈_st中插入新元素。对于_minst来说，如果栈_minst为空，直接向_minst插入新元素。如果栈_minst不为空，当新插入的元素小于或等于_minst的栈顶元素，那么向_minst中插入新元素；而新插入的元素大于_minst的栈顶元素，则向_minst中插入栈顶元素。那么，此时的_minst中的栈顶元素就是栈_st对应位置的最小值。出栈时，让栈_st和_minst同时出栈即可。
class MinStack { public: MinStack() {} void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top()) { _minst.push(val); } else { _minst.push(_minst.top()); } } void pop() { _st.pop(); _minst.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } stack<int> _st; stack<int> _minst; };
其实按照上面的思路来解题，栈_minst中可能会存储着大量的重复的最小值。那么我们可以做一些小小的优化：当新插入元素大于_minst栈顶元素时，不再向_minst插入栈顶元素了。按照这种思路的话，出栈也要做相应的改变：当_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(); } stack<int> _st; stack<int> _minst; };
但是第二种思路面对着大量重复的最小值的场景时，也会存在空间浪费的情况。那么我们还可以进一步的优化，增加多一个计算器并将其封装成一个类struct valCont，该类的成员变量_val和_count。此时，栈_minst的元素是struct valCount。当新插入元素等于_minst.top()._val时，++_minst.top()._count。当_minst.top()._count == 0时，则_minst栈顶元素出栈。
struct valCount { int _val; int _count; valCount(int val = 0, int count = 0) { _val = val; _count = count; } }; class MinStack { public: MinStack() {} void push(int val) { _st.push(val); if(_minst.empty() || val < _minst.top()._val) { _minst.push(valCount(val, 1)); } else if(val == _minst.top()._val) { ++_minst.top()._count; } } void pop() { if(_st.top() == _minst.top()._val) { --_minst.top()._count; if(_minst.top()._count == 0) _minst.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top()._val; } stack<int> _st; stack<valCount> _minst; };
注：struct valCount 最好自己提供默认构造函数，这样就可以支持匿名对象的用法了。以上思路实现的 MinStack 都没有提供构造函数，为什么也有过呢？因为对于自定义类型，编译器会调用自定义类型的默认构造函数。
2. 验证栈序列
给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
思路：给定一个入栈序列，可能会有多个出栈序列。因为会存在边入边出、入几个再出等等情况。本道题是让我们验证出栈序列popped是不是入栈序列pushed的出栈序列。那么如何解决这道题呢？这道题可以这样来解决：1. 入栈序列的元素先入栈 2. 栈顶元素和出栈序列的元素比较，相等则栈顶元素出栈并继续比较 3. 当入栈序列的元素已全部入栈，循环结束。如果栈为空或者出栈序列也全部遍历了一次，那么popped就是pushed的出栈序列了，否则不是。
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> st; int i = 0; // 遍历出栈序列popped用的下标 for(auto& e : pushed) { st.push(e); // 入栈序列先入栈 // 比较：相同则出栈且继续比较 while(!st.empty() && st.top() == popped[i]) { st.pop(); ++i; } } //return i == popped.size(); return st.empty(); } };
3. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的乘法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
逆波兰表达式是一种后缀表达式，而我们日常学习用到的是中缀表达式。中缀表达式操作符在中间，操作数在两遍；而后缀表达式则操作符在后面，操作数在前面。如：前缀表达式2 + 3 * 4对应的后缀表达式为2 3 4 * +。那为什么要有后缀表达式呢？因为计算机是顺序读入表达式的，当读到操作符时，计算机就会去两个操作数进行运算。如果采用的是中缀表达式，计算机将无法识别该操作符后是否存在更高级的操作符。而后缀表达式不会存在这样的情况，可以依据后缀表达式的次序计算出正确结果。
那么解决这道题的思路是什么呢？其实很简单，就是遇到数字则入栈；遇到操作符则取栈顶两个数组进行计算（对于减法和除法，需区分左操作数和右操作数），并将结果压入栈中。遍历结束，栈顶元素就是后缀表达式的计算结果。
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(); // 后缀表达式的结果 } };
stoi 函数的第二个参数是一个输出型参数，其值为 str 转化成整型数字时的结束位置的下一个位置，该参数可以设置为nullptr，表明不关心该值；第三个参数则表示要转化的字符串 str 里的数字是什么进制的。该参数的缺省值为 10，表示 str 里的数字是十进制的。如果该值被设置为 0 ，则需要根据 str 里的标致来判别其数字是什么进制的。
stoi 函数的演示使用
#include <iostream> #include <string> using namespace std; int main() { string str_dec = "2001, A Space Odyssey"; string str_hex = "40c3"; string str_bin = "-10010110001"; string str_auto = "0x77"; std::string::size_type sz; // alias of size_t int i_dec = std::stoi(str_dec, &sz); int i_hex = std::stoi(str_hex, nullptr, 16); // 十六进制 int i_bin = std::stoi(str_bin, nullptr, 2); // 2进制 int i_auto = std::stoi(str_auto, nullptr, 0); // cout << str_dec << ": " << i_dec << " and [" << str_dec.substr(sz) << "]\n"; // substr(sz)表示从sz位置取到str_dec的结尾作为子串 cout << str_hex << ": " << i_hex << '\n'; cout << str_bin << ": " << i_bin << '\n'; cout << str_auto << ": " << i_auto << '\n'; return 0; }
4. 中缀表达式转为后缀表达式
注：该中缀表达式中包含 + - * / ( ) =等符号，且包含空格。转换得到的后缀表达式也不包含空格。
那么如何将中缀表达式转为后缀表达式呢？
从左往右遍历中缀表达式，跳过空格
遇到操作数直接输出
如果当前操作符为左括号，左括号直接入栈
如果当前操作符为右括号，让栈顶到左括号之间的操作符出栈添加到后缀表达式中，括号不出现在后缀表达式中
如果当前操作符优先级小于或等于栈顶操作符的优先级，先将栈顶操作符出栈直至栈顶操作符优先级小于当前操作符优先级，再将当前操作符入栈
遍历完中缀表达式，将栈中的操作符出栈添加到后缀表达式中
注意：出栈有可能会出多个操作符；栈为空时，操作符一定要入栈。遍历结束时，栈内的操作符要依次出栈。
class Solution { public: vector<string> convertToRPN(vector<string> &expression) { vector<string> ret; stack<string> st; // 存储操作符的栈 for(auto& str : expression) { if(str == "(") // 左括号直接入栈 st.push(str); else if(str == ")") { // 左括号上面的操作符全部出栈添加到后缀表达式中 while(st.top() != "(") { ret.push_back(st.top()); st.pop(); } st.pop(); // 左括号出栈但不添加到后缀表达式中 } else if(str == "+" || str == "-" || str == "*" || str == "/") { // 栈顶操作符优先级大于或等于当前操作符，则出栈 while(!st.empty() && compare(st.top(), str)) { ret.push_back(st.top()); st.pop(); } st.push(str); // 当前操作符入栈 } else { ret.push_back(str); // 数字直接添加到后缀表达式中 } } while(!st.empty()) { ret.push_back(st.top()); st.pop(); } return ret; } private: // 比较操作符的优先级：first >= second时，返回 true bool compare(const string& first, const string& second) { if(first == "*" || first == "/") return true; else if(first == "(") return false; else if(second == "+" || second == "-") return true; else return false; } };
