前言：

栈本质上是一个比较简单的容器，算法题里有直接考察栈的先进后出的特性，也有跟其他算法相结合，还是挺有意思的，难度也适中

一、JZ31 栈的压入、弹出序列

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

解析：

1、入栈序列：先让当前数据入栈

2、栈顶元素跟出栈元素序列比较，是否相等

如果相等：出栈，出栈序列++，直到栈为空，或者不相等。如果不相等，再让入栈序列入栈。

结束的判断条件：

1、出栈序列走到尾，说明全匹配（true）

2、栈顶元素和出栈序列匹配不上，且入栈序列已经走完，没有数据可以入栈（false）

原码：

bool IsPopOrder(vector& pushV, vector& popV) {stack st;int pushi = 0,popi = 0;//定义下标名称有讲究while(pushi < pushV.size()){st.push(pushV[pushi++]);while(!st.empty() && popV[popi] == st.top()){st.pop();popi++;}}if(popi == popV.size()) return true;else return false;}};

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

题目描述：

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

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

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

解析：

这题明显是利用栈进行解决，这里有个技巧，就是我们不用真的栈容器去解决，我们用数组模拟一个栈即可，这样会更加简洁！！！

原码：

class Solution {public:string removeDuplicates(string s) {string ret;//模拟栈结构即可~for(auto ch : s){if(ret.size() && ret.back() == ch)//出栈 ret.pop_back();else ret += ch;//入栈}return ret;}};

三、227. 基本计算器 II

题目描述：

给你一个字符串表达式s，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"输出：7

解析：

一般需要符号栈、数据栈，两个。但是，看到网上一个写的不错的算法，只用了一个数据栈。符号栈用一个变量op代替了，只存储上一个符号。

1、遇到操作符：更新操作符

2、遇到数字：

  1. op == ‘+’ ，tmp直接入栈
  2. op == ‘-‘，-tmp入栈
  3. op == ‘*’，直接乘到栈顶元素上
  4. op == ‘/’，直接除到栈顶元素上

原码：

class Solution {public:int calculate(string s) {//第一位加上+，便于后面编程char sign = '+';//模拟符号栈vector arr;//模拟数据栈arr.resize(s.size());int i = 0;int index = 0;while(i = '0' && s[i] <= '9'){//先把这个数字提取出来while(i = '0' && s[i] <= '9'){tmp = tmp * 10 + (s[i] - '0');i++;}if(sign == '+') arr[index++] = tmp;else if(sign == '-') arr[index++] = -tmp;else if(sign == '*') arr[index-1] *= tmp;else if(sign == '/') arr[index-1] /= tmp;}else{if(s[i] == '+') sign = '+';else if(s[i] == '-') sign = '-';else if(s[i] == '*') sign = '*';else if(s[i] == '/') sign = '/';i++;}}int sum = 0;for(int j = 0;j<index;j++){sum += arr[j];}return sum;}};

四、394. 字符串解码

题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。

示例 1：

输入：s = "3[a]2[bc]"输出："aaabcbc"

解析：

用栈来模拟。

细节：字符串这个栈中，先放入一个空串。

分情况讨论：

  1. 遇到数字：提取出这个数字，放入数字栈中
  2. 遇到’ [ ‘：把后面的字符串提取出来，放入“字符串栈”中
  3. 遇到’ ] ‘：按题目操作，然后放到字符串栈栈顶的字符串后面
  4. 遇到单独的字符：提取出来这个字符串，直接放在字符串栈栈顶字符串的后面

原码：

class Solution {public:string decodeString(string s) {stack nums;//数据栈stack st;//字符串栈st.push("");//先放入一个空串，防止后面数据溢出int i = 0;while(i= '0' && s[i] = '0' && s[i] = 'a' && s[i] <= 'z'){ret += s[i];i++; }st.push(ret);}//3、]else if(s[i] == ']'){int tmp = nums.top();string ret1 = st.top();string ans;nums.pop();st.pop();for(int j = 0;j<tmp;j++){ans += ret1;}st.top() += ans;i++;}//4、遇到单独的字符else { st.top() += s[i++];}}return st.top();}};

简单题中可以用数组或者string来模拟栈结构，但是操作一复杂，还是直接用真正的栈模拟比较好！