【算法】栈与模拟

【ps】本篇有 5 道 leetcode OJ。

一、算法简介

二、相关例题

1）删除字符串中的所有相邻重复项

.1- 题目解析

.2- 代码编写

2）比较含退格的字符串

.1- 题目解析

.2- 代码编写

3）基本计算器 II

.1- 题目解析

.2- 代码编写

4）字符串解码

.1- 题目解析

.2- 代码编写

5）验证栈序列

.1- 题目解析

.2- 代码编写

一、算法简介

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出的原则。它的插入操作叫做进栈（或进栈/入栈），插入的数据在栈顶；删除操作叫做出栈。出的数据也在栈顶。

栈一般与模拟算法结合在一起出题，在题目中野经常充当数据的缓存容器，来帮助模拟入栈和出栈的过程以求得结果。

二、相关例题

1）删除字符串中的所有相邻重复项

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

.1- 题目解析

我们用一个新字符串，对每个字符模拟入栈和出栈的过程即可，具体方式是遍历字符串，从左往右依此将字符入栈（尾插入新字符串），如果当前字符与栈顶的字符（新字符串的末尾字符）相同，就将栈顶的字符出栈（对新字符串尾删），且跳过当前字符，继续遍历下一个字符。

.2- 代码编写

class Solution {
public:string removeDuplicates(string s) {string ret;for(int i=0;i<s.size();i++){//用一个新字符串对每个字符模拟入栈和出栈的过程if(ret.size() && s[i]==ret.back())ret.pop_back();else ret+=s[i];}return ret;}
};

2）比较含退格的字符串

844. 比较含退格的字符串

.1- 题目解析

类似的，这道题也可以用字符串来模拟入栈和出栈的过程，但与上道题不同的是，出栈的条件变成了若当前字符为 '#'，入栈的条件为若当前字符不为 '#'。

.2- 代码编写

class Solution {
public:bool backspaceCompare(string s, string t) {return stackString(s)==stackString(t);}//用一个新字符串模拟入栈和出栈的过程string stackString(string& s){string st;for(auto ch:s){if(ch=='#'){if(st.size())st.pop_back();}else {st+=ch;}}return st;}
};

3）基本计算器 II

227. 基本计算器 II

.1- 题目解析

这道题只有加减乘除四个运算，没有括号，并且每一个数都是大于等于 0 的，这样可以大大地减少需要处理的情况。

由于表达式里面没有括号，因此只用处理加减乘除混合运算即可，这样不需要用到双栈。根据四则运算的顺序，我们可以先计算乘除法，然后再计算加减法。由此可以得出下面的结论：

当一个数前面是 ' + ' 号的时候，这⼀个数是否会被立即计算是不确定的，因此可以先入栈。
当一个数前面是 ' - ' 号的时候，这⼀个数是否被立即计算也是不确定的，但是这个数已经和前面的负号绑定了，因此可以将这个数的相反数入栈。
当一个数前面是 ' * ' 号的时候，这⼀个数可以立即与前面的⼀个数相乘，此时让将栈顶的元素乘上这个数；
当一个数前面是 ' / ' 号的时候，这⼀个数也是可以立即被计算的，因此让栈顶元素除以这个数。

当遍历完完整的表达式时，栈中剩余的元素之和就是最终结果。此外，这里可以用数组来模拟栈。

.2- 代码编写

class Solution {
public:int calculate(string s) {char op='+';//表达式开头没有运算符，但应默认是+号int i=0,n=s.size();vector<int> st;//用数组模拟栈while(i<n){if(s[i]==' ')i++;//跳过空格else if(s[i]>='0'&&s[i]<='9'){int tmp=0;//提取一个完整的操作数while(i<n && s[i]>='0'&& s[i]<='9'){tmp=tmp*10+(s[i++]-'0');}//按运算符处理操作数if(op=='+')st.push_back(tmp);else if(op=='-')st.push_back(-tmp);else if(op=='*')st.back()*=tmp;else if(op=='/')st.back()/=tmp;}else op=s[i++];}//累加栈中的数，即可得到结果int ret=0;for(auto x:st)ret+=x;return ret;}
};

4）字符串解码

394. 字符串解码

.1- 题目解析

本题可以用两个栈来模拟解码的过程，其中一个栈存字符，另一个栈存数字。

解码的顺序，是从括号内部向外部依此解码，如：3[ab2[cd]] -> 3[abcd cd] -> abcdcd abcdcd abcdcd 。

.2- 代码编写

class Solution {
public:string decodeString(string s) {stack<int> nums; //数字栈stack<string> st;//字符栈st.push("");//预留一个空字符串，以防越界访问int i=0,n=s.size();while(i<n){//提取数字放入数字栈中if(s[i]>='0'&&s[i]<='9'){int tmp=0;while(s[i]>='0'&&s[i]<='9'){tmp=tmp*10+(s[i++]-'0');}nums.push(tmp);}//遇到'['，提取字符串放入字符栈中else if(s[i]=='['){i++;string tmp;while(s[i]>='a'&&s[i]<='z'){tmp+=s[i++];}st.push(tmp);}//遇到']'，解析，然后将其尾插到字符栈栈顶字符串的后面else if(s[i]==']'){string tmp=st.top();st.pop();int k=nums.top();nums.pop();while(k--){st.top()+=tmp;}i++;}//提取字符串，直接尾插到字符栈栈顶字符串的后面else{string tmp;while(i<n && s[i]>='a'&& s[i]<='z'){tmp+=s[i++];}st.top()+=tmp;}}return st.top();}
};

5）验证栈序列

946. 验证栈序列

.1- 题目解析

这是一道经典的栈相关的题目，给定一个进栈序列，再给定一个出栈序列，要求根据进栈序列判断出栈序列是否合法。

我们可以创建一个栈，然后分别遍历这两个序列，来模拟进栈和出栈的过程。遍历进栈序列的时候，先将序列中的元素依此 push 入栈，再遍历出栈序列中的元素，如果当前元素与刚入栈的这个元素相同，那么就将其出栈，如果不是，就继续对进栈序列中的元素进行入栈，直到遇到出栈序列中的相同元素再出栈。如此，遍历完两个序列后，如果栈为空，则说明栈序列是合法的。

.2- 代码编写

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i=0;for(auto x:pushed){st.push(x);while(st.size()&&st.top()==popped[i]){st.pop();i++;}}return st.empty();}
};