算法_栈专题---持续更新

本文主要是介绍算法_栈专题---持续更新，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本文将会向你介绍有关栈的相关题目：删除字符中的所有相邻重复项、比较含退格的字符串、基本计算器II、字符串解码、验证栈序列

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

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

题目要求

题目解析

当出现重复的字符后，比如aa，我们需要将其全部删除，我们可以使用一个栈来保存删除重复项后的字符串，只需要比较 i 所指位置的字符是否与栈顶元素相同，如果相同，就将栈顶元素删除即可，我们可以不创建stack栈，而是用string来替代，因为string中包含成员函数back、pop_back，我们就可以轻易地模拟获取栈顶元素以及删除栈顶元素了

代码如下

class Solution {
public:string removeDuplicates(string s) {string tmp;int i = 0;     while(i < s.size()){if(!tmp.empty() && tmp.back() == s[i]){tmp.pop_back();i++;}else tmp += s[i++];}return tmp;}
};

比较含退格的字符串

https://leetcode.cn/problems/backspace-string-compare/

题目要求

题目解析

这道题与第一题相似，都是用栈的思想，用栈保存剩余的字符，当遍历到#，就需要删去栈顶的元素

代码如下

class Solution {
public:bool backspaceCompare(string s, string t) {string tmp1; for(auto ch : s){if(ch != '#'){tmp1 += ch;}else{if(tmp1.size()) tmp1.pop_back();}}string tmp2; for(auto ch : t){if(ch != '#'){tmp2 += ch;}else{if(tmp2.size()) tmp2.pop_back();}}return tmp1 == tmp2;}
};

基本计算器II

https://leetcode.cn/problems/basic-calculator-ii/description/

题目要求

题目解析

根据题意要求实现一个计算器，首先应该考虑到加减乘除中最特殊的还是乘与除，乘除的优先级最高，那么肯定会涉及到一部分数先不动，另一部分先算的情况，这时我们可以想到用栈这个数据结构。 用一个char类型的变量保存操作符，用vector数组模拟栈，遍历字符串，将加一个数，看作正数，减一个数，看作负数，统统压入栈中稍后计算，当遇到乘除，就用栈顶元素（vector中的接口back）乘除当前遍历的数，然后压入栈中，最后栈里剩下的就都是正数负数，最后全部相加即可（最后的相加如果使用栈会比较麻烦，用vector迭代器轻松解决，这也是我们使用vector来替代栈的原因） ## 代码如下

class Solution {
public:int calculate(string s) {char op = '+'; //保存操作符vector<int> st; //保存操作数int ret = 0, tmp = 0;int i = 0;while(i < s.size()){//跳过空格if(s[i] == ' '){i++;    }else if(s[i] >= '0' && s[i] <= '9'){tmp = 0;    //将tmp置零//提取操作数while(i < s.size() && 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 st.back() /= tmp; }else{op = s[i];i++;}}   for(auto e : st){ret += e;}return ret;}
};

字符串解码

https://leetcode.cn/problems/decode-string/

题目要求

题目解析

根据题目要求，我们需要把括号中间的字符串重复写，具体重复几次根据括号外面的数字，因此我们是需要在 ] 右括号完后，才能知道有多长字符串需要重复写，可以借助两个栈解决，分别是数字串栈，字符串栈
根据示例可以得知，这道题的本质还是模拟，模拟解码的过程
一共有四种情况：

1、遇到数字，先让数字入栈，并不着急使用，等到右括号出现
2、遇到左括号，提醒我们左括号后一定是字符串，我们需要接收这个字符串
3、遇到右括号，此时需要解码，我们就需要取出数字串与字符串，并对字符串进行叠加写
4、无左括号包含的字符串，即字符串不在括号里的情况，直接加入到字符串栈即可

一些需要注意的细节：
这个数字可不仅仅是0~9之内的
遍历时记得跳过左右括号

代码如下

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(s[i] >= '0' && s[i] <= '9'){//提取所有的数字int num = 0;while(s[i] >= '0' && s[i] <= '9'){num = num * 10 + (s[i] - '0');i++;}st2.push(num);}//把左括号后面的字符提取出来else if(s[i] == '['){i++;    //跳过左括号string tmp = "";//提取所有的字符while(i < n && s[i] >= 'a' && s[i] <= 'z'){tmp += s[i++];}st1.push(tmp);}//解码else if(s[i] == ']'){string s = st1.top();int k = st2.top();st1.pop();st2.pop();while(k--){st1.top() += s;}i++;    //跳过右括号}//遇到单独的字符/字符串（不在括号里的情况）else{string tmp = "";while(i < n && s[i] >= 'a' && s[i] <= 'z'){tmp += s[i++];}st1.top() += tmp;}}return st1.top();}
};

验证栈序列

https://leetcode.cn/problems/validate-stack-sequences/

题目要求

题目解析

该题目要求验证出栈顺序是否合理，题目给出两个数组分别是pushed与popped，通过依次比较栈顶元素与popped序列中的元素是否相等，如果popped序列是合理的，那么下标 j 一定能走到最后，如果栈顶元素与 j 下标指向元素不同，那么入栈元素，可能是因为元素还没入栈导致的不同，如果所有元素都以入栈，栈顶元素与 j 下标指向的元素不同，那么此时出栈序列一定是不合理的

代码如下

//该题要求验证栈出栈顺序是否合理
class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i = 0, j = 0;st.push(-1);    //防止一开始用栈顶元素比较时为空报错while(j < popped.size()){if(st.top() != popped[j]){//结束条件：当pushed已经结束且栈顶元素不等于出栈顺序if(i == pushed.size()){return false;}st.push(pushed[i++]);}else{   st.pop();j++;}}return true;}
};

这篇关于算法_栈专题---持续更新的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---