栈容器的应用

第一题：

用数组来模拟栈：

题解代码：

class Solution {
public:string removeDuplicates(string s) {// 用数组模拟栈string s1;for (int i = 0; i < s.size(); i++) {if(s1.size() == 0){s1+=s[i];}else if (s1.back() == s[i]) {s1.pop_back();} elses1 += s[i];}return s1;}
};

 第二题：

还是数组模拟栈

题解代码：

class Solution {
public:bool backspaceCompare(string s, string t) {//同样的用数组来模拟string s1,s2;for(const auto& e:s){//当不为空并且e == #时才尾删if(s1.size()&&e == '#'){s1.pop_back();}//不能将#也➕到串中else if(e != '#') s1+=e;}for(const auto& e:t){if(s2.size()&&e == '#'){s2.pop_back();}else if(e!='#')s2+=e;}return s1 == s2;// if(s1.size() == 0&&s2.size() == 0){//     return true;// }// else if(s1.size()!= s2.size()){//     return false;// }// else {//     int i = 0;//     while(i<s1.size()){//         if(s1[i] == s2[i]) i++;//         else return false;//     }// }// return true;} 
};

第三题：

表达式求值

算法原理：

 题解代码：

class Solution {
public:int calculate(string s) {//数组模拟vector<int> st;char op = '+';int i =0;int n = s.size();while(i<n){if(s[i] == ' '){i++;}//数字else if(s[i]>='0'&&s[i]<='9'){int tem = 0;while(i<n&&s[i]>='0'&&s[i]<='9'){tem = tem*10+(s[i++]-'0');}//此时的i指向的是非数字的元素if(op == '+') st.push_back(tem);if(op == '-') st.push_back(-tem);if(op == '*') st.back() *= tem;if(op == '/') st.back() /= tem;}else {op = s[i];i++;           }}int ret = 0;for(auto& e:st){ret+=e;}return ret;}
};

第四题：

题解思路：

 

题解代码：

这里我同样采用的vector来模拟栈 

class Solution {
public:string decodeString(string s) {vector<int> num;vector<string> st;st.push_back("");int i = 0;int n = s.size();while (i < n) {if (s[i] >= '0' && s[i] <= '9') {int tem = 0;while (i < n && s[i] >= '0' && s[i] <= '9')tem = tem * 10 + (s[i++] - '0');num.push_back(tem);}// i走到这表明不是数字了；else if (s[i] == '[') {i++; // 注意要先加1string s1;while (i < n && s[i] >= 'a' && s[i] <= 'z') {s1 += s[i++];}// 将s尾插到最后；st.push_back(s1);}// 走到这表明不是[;// 若是]，就提出来进行解码else if (s[i] == ']') {// 将栈顶元素提出来；string tmp = st.back();st.pop_back();// 再提取栈顶的数字int nums = num.back();num.pop_back();// 重复；while (nums--) {st.back() += tmp;}i++; // 跳过这个右括号}// 这，纯字符else {string s1;while (i < n && s[i] >= 'a' && s[i] <= 'z') {s1 += s[i];i++;}st.back() += s1;}}return st.back();}
};

第五题：

验证栈序列：

题解思路：

1.将入栈序列挨个入栈；

2、判断出栈序列是否与栈顶元素相同，相同就出栈；

3、最后返回栈是否为空；

题解代码：

这里我还是用的vector来模拟的栈：

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {vector<int> vt;int i = 0;for (const auto& e : pushed) {vt.push_back(e);while (vt.size() && vt.back() == popped[i]) {vt.pop_back();i++;}}return vt.empty();}
};