优选算法——栈

💁‍♂️个人主页：进击的荆棘

👇作者其它专栏：

《数据结构与算法》《算法》《C++起始之路》

相关题解

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

算法思路：

本题仔细观察消除过程，可以发现本题与我们之前做过的【括号匹配】问题是类似的。当前元素是否被消除，需要知道上一个元素的信息，因此可以用【栈】来保存信息。

但是若使用stack来保存的话，最后还需要把结果从栈中取出来。可以直接用【数组模拟一个栈】结构：在数组的尾部【尾插尾删】，实现栈的【进栈】和【出栈】。那么最后数组存留的内容就是最后的结果。

// class Solution { // public: // string removeDuplicates(string s) { // stack<char> st; // string ret; // for(int i=0;i<s.size();i++){ // if(!st.empty()){ // if(s[i]==st.top()){ // st.pop(); // continue; // } // } // st.push(s[i]); // } // while(!st.empty()){ // ret+=st.top(); // st.pop(); // } // reverse(ret.begin(),ret.end()); // return ret; // } // }; class Solution { public: //不用真的用栈，直接用一个数组模拟栈的操作即可 string removeDuplicates(string s) { string ret; for(int i=0;i<s.size();i++){ if(ret.size()!=0){ if(s[i]==ret.back()){ ret.pop_back(); continue; } } ret+=s[i]; } return ret; } };

2.比较含退格的字符串

算法思路：

由于退格的时候需要知道【前面元素【的信息，而且退格也符合【后进先出】的特性。因此可以使用【栈】结构来模拟退格的过程。

●当遇到非#字符的时候，直接进栈；

●当遇到#的时候，栈顶元素出栈。

为方便统计结果，使用【数组】来模拟实现栈结构。

class Solution { public: bool backspaceCompare(string s, string t) { return changeStr(s)==changeStr(t); } string changeStr(string s){ string ret; for(int i=0;i<s.size();i++){ if(s[i]!='#'){ ret+=s[i]; } else { if(ret.size()!=0) ret.pop_back(); } } return ret; } };

3.基本计算器 II

题目解析：

从提示中可以看到此题：

●只有【加减乘除】四个运算；

●没有括号；

●并且每一个数都是大于等于0的。

这样可以大大的【减少】需要处理的情况。

算法思路：

由于表达式中没有括号，因此只需处理【加减乘除】混合运算即可。根据四则运算的顺序，可以先计算乘除法，然后再计算加减法。由此：

●当一个数前面是'+'号的时候，这一个数是否会被立即计算是【不确定】的，因此可以先压入栈中；

●当一个数前面是'-'号的时候，这一个数是否被立即计算也是【不确定】的，但是这个数已经和前面的-号绑定了，因此可以将这个数的相反数压入栈（这样最后只需执行'+'操作）；

●当一个数前面是'*'号的时候，这一个数可以立即与前面的一个数相乘，此时让栈顶的元素乘上这个数；

●当一个数前面是'/'号的时候，这一个数也是可以立即被计算的，因此让栈顶元素除以这个数。

当遍历完全部的表达式的时候，栈中剩余的【元素之和】就是最终结果。

class Solution { public: int calculate(string s) { vector<int> st;//用数组模拟栈 int i=0,n=s.size(); char op='+'; //先将*和/的结果计算出来 while(i<n){ if(s[i]==' ') i++; else if('0'<=s[i]&&s[i]<='9'){ int tmp=0; //提取数字 while(i<n&&'0'<=s[i]&&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 st.back()/=tmp; } else{ op=s[i]; i++; } } //在计算+和- int ret=0; for(auto e:st) ret+=e; return ret; } };

4.字符串解码

算法思路：

对于3[ab2[cd]]，需要先解码内部的，再解码外部：

●3[ab2[cd]] ->3[abcd cd] -> abcdcd abcdcd abcdcd

在解码cd的时候，需要保存3 ab 2这些元素的信息，并且这些信息使用的顺序是哦才能够后往前，正好符合栈的结构，因此可以定义两个栈结构，一个用来保存解码前的重复次数k（左括号前的数字），一个用来保存解码之前字符串的信息（左括号前的字符串信息）。

class Solution { public: string decodeString(string s) { stack<string> st1;//字符串栈 stack<int> st2;//数字栈 //防止出现越界访问情况，提前存入一个空串 st1.push(""); int i=0,n=s.size(); while(i<n){ //若为数字 if('0'<=s[i]&&s[i]<='9'){ //提取这个数字 int num=0; while(i<n&&'0'<=s[i]&&s[i]<='9') num=num*10+(s[i++]-'0'); st2.push(num); } //若为'[' else if(s[i]=='['){ i++;//从'['的后一个字符开始 //提取字符串 string str; while(i<n&&'a'<=s[i]&&s[i]<='z') str+=s[i++]; st1.push(str); } //若为']' else if(s[i]==']'){ int k=st2.top(); st2.pop(); string str=st1.top(); st1.pop(); while(k--) st1.top()+=str; i++;//跳过']' } //若为单独字母 else { string str; while(i<n&&'a'<=s[i]&&s[i]<='z') str+=s[i++]; st1.top()+=str; } } return st1.top(); } };

5.验证栈序列

算法思路：

用栈来模拟进出栈的流程。

一直让元素进栈，进栈的同时判断是否需要出栈。当所有元素模拟完毕之后，若栈中还有元素，那么就是一个非法的序列。否则，就是一个合法的序列。

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