一：删除字符串中的所以后相邻重复项
题目要求：
解题思路：
思路：模拟入栈和出栈的过程，在该过程中比较栈顶元素和入栈元素是否相同，如若相同则出栈，注意出栈时，判断栈是否为空。，不相同则入栈，直至字符串遍历结束。
注：先向栈插入字符串中首元素，避免取栈顶报错。
实现代码：
class Solution {
public:string removeDuplicates(string s) {string ret("");ret += s[0];for(int i = 1; i < s.size(); i++) {if(ret.size() && ret.back() == s[i]) ret.pop_back();elseret += s[i];}return ret;}
};二：比较含退格的字符串
题目要求：
解题思路：
思路：和上一题区别不大，无非把重复字符的判断改成是否为'#'，如果是，则出栈，不是则入栈，注意出栈时，判断栈是否为空。
实现代码：
class Solution {
public:string DeleteBackSpace(string& str) {string ret("");for(int i = 0; i < str.size(); i++) {if(ret.size() && str[i] == '#')ret.pop_back();else if (str[i] != '#')ret += str[i];}return ret;}bool backspaceCompare(string s, string t) {string ret1 = DeleteBackSpace(s);string ret2 = DeleteBackSpace(t);if(ret1.compare(ret2) == 0)return true;elsereturn false;}
};三：基本计算器Ⅱ
题目要求：
解题思路：
思路：
定义一个符号位：char f = '+'; 下标 i = 0；
当我们遍历到一个数字时
注：该数字可能是多位数，对于string类型的数据，每次只能遍历一个数字，因此若当前数据为数字时，需要再做循环遍历，直至不是数字为止。定义 tmp = 0；每次遍历时令
tmp = tmp * 10 + (当前数字字符 - '0');
根据符号位做不同处理
①为’+‘：直接将当前数字入栈
②为'-'： 将当前数字的负值入栈
③为'*': 取栈顶元素 *= 当前数字
④为'/'： 取占地元素 /= 当前数字
上述过程结束后，此时 i位置 对应元素应该为符号位，更新符号位，i++，开始下一次循环，遍历完字符串s
实现代码：
class Solution {
public:int calculate(string s) {vector<int> tmp;int i = 0;char f = '+';while(i < s.size()){if(s[i] >= '0' && s[i] <='9') {int n = 0;while(i < s.size() && s[i] >= '0' && s[i] <='9')n = n*10+(s[i++]-'0');if(f == '+') tmp.push_back(n);else if (f == '-')tmp.push_back(-n);else if (f == '*')tmp.back() *= n;elsetmp.back() /= n;}else if (s[i] == ' ')i++;else { f = s[i]; i++;}}int ret = 0;for(auto& N : tmp) ret += N;return ret;}
};四：字符串解码
题目要求：
解题思路：
理解题意：将括号内的字符，打印括号前数字k的k次，需要从内向外破译，因此当遍历到']'该符号时，则需要开始破译。
思路：
定义两个栈(用于模仿栈，实际不是栈)
vector<int> num; 用于字符串s中的数字
string ret;用于存放字符串s中的符号
定义 i = 0 来遍历字符串s
①当s[i]为数字时，入栈至num，
②当s[i]为符号时
1.不为']'时，入栈至ret
2.为']'时，定义变量string tmp; 循环出ret栈顶元素，直至为'['为止，并将遍历过程中所有的字符插入到tmp中，循环结束后，当前ret栈顶元素为']',因此需要再出一次栈顶，定义cnt = num.back()，循环cnt次将当前tmp字符串翻转插入到ret栈顶中。
如图所示：
当s[i]再次遍历到字符']'时，重复上述过程，最终得到如下结果：
ret即为我们所求的最终答案。
实现代码：
class Solution {
public:string decodeString(string s) {vector<int> num;string ret;int i = 0;while(i < s.size()){if(s[i] >= '0' && s[i] <= '9'){int n = 0;while(i < s.size() && s[i] >= '0' && s[i] <= '9')n = n * 10 + (s[i++] - '0');num.push_back(n);}else {if(s[i] == ']'){string str;while(ret.back() != '['){ str += ret.back();ret.pop_back();}reverse(str.begin(),str.end());ret.pop_back();int cnt = num.back();num.pop_back();while(cnt) {ret += str;cnt--;}i++;}else{ret += s[i];i++;}}}return ret;}
};五：验证栈序列
题目要求：
解题思路：
思路：
定义变量 queue<int> q;
定义遍历 int i = 0，j = 0; 分别用于遍历怕pushed和popped
遍历pushed
①将元素入栈q
②取栈顶元素，循环判断当前元素是否等于 popped[j]; 若等于，q出栈顶，j++；
实现代码：
class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> ret;for(int i = 0, j = 0; i < pushed.size(); i++) {ret.push(pushed[i]);while(ret.size() && j < popped.size() && ret.top() == popped[j]){ret.pop();j++;}}return ret.empty();}
};
