栈目录栈试题1删除字符串中的所有相邻重复项算法原理代码编写试题2比较含退格的字符串算法原理代码编写试题3基本计算器II算法原理代码编写试题4字符串解码算法原理代码编写试题5验证栈序列算法原理代码编写试题1删除字符串中的所有相邻重复项算法原理解法模拟栈代码编写class Solution { public: string removeDuplicates(string s) { string ret; for(auto ch : s) { if(ret.size() ch ret.back()) { ret.pop_back(); } else { ret ch; } } return ret; } };试题2比较含退格的字符串算法原理解法模拟栈代码编写class Solution { public: bool backspaceCompare(string s, string t) { return changeStr(s) changeStr(t); } string changeStr(string s) { string ret; for(auto ch : s) { if(ch ! #) { ret ch; } else { if(ret.size()) { ret.pop_back(); } } } return ret; } };试题3基本计算器II算法原理解法模拟栈遇到操作符更新操作符栈遇到数字提取数字分情况讨论根据操作符栈的符号加号数字入数字栈减号数字的相反数入栈乘号直接与数字栈栈顶元素相乘除号直接与数字栈栈顶元素相除代码编写class Solution { public: int calculate(string s) { // 用数组模拟栈结构 vectorint st; int i 0, n s.size(); char op ; 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); i; } 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 x : st) { ret x; } return ret; } };试题4字符串解码算法原理解法模拟栈遇到数字提取数字放入数字栈遇到左括号提取后面的字符串放入字符串栈遇到右括号拿出两个栈的栈顶元素解析放到字符串栈的栈顶元素后面遇到单独字符提取字符串放到字符串栈的栈顶元素后面代码编写class Solution { public: string decodeString(string s) { stackint nums; stackstring 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); i; } nums.push(tmp); } else if(s[i] [) { i;// 跳过左括号 string tmp; while(s[i] a s[i] z) { tmp s[i]; 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]; i; } st.top() tmp; } } return st.top(); } };试题5验证栈序列算法原理解法模拟栈让元素一直进栈进栈的同时判断是否出栈所有元素进栈完后判断i是否遍历完毕或者判断栈是否为空代码编写class Solution { public: bool validateStackSequences(vectorint pushed, vectorint popped) { stackint st; int i 0, n popped.size(); for(auto x : pushed) { st.push(x); while(st.size() st.top() popped[i]) { st.pop(); i; } } return i n; } };