栈与队列力扣经典例题20. 有效的括号1047. 删除字符串中的所有相邻重复项150. 逆波兰表达式求值
对于栈与队列，我们首先要搞清楚，栈是先入后出，而队列是先入先出，利用这个特性，我们来判断题目用什么STL容器，便于我们去解决问题
20. 有效的括号
这道题，首先我们要知道哪些情况，是会使结果变为false的，第一种就是括号数是奇数，那肯定不能两两匹配，第二种就是括号数是偶数可以匹配，但是括号类型不对，就像case 3一样
class Solution {
public:bool isValid(string s) {stack<char>str;if(s.size()%2){return false;}for(int i=0;i<s.size();i++){if(s[i]=='(')str.push(')');else if(s[i]=='[')str.push(']');else if(s[i]=='{')str.push('}'); else if(str.empty()||str.top()!=s[i])return false;else str.pop();}return str.empty();}
};1047. 删除字符串中的所有相邻重复项
遇到这种题我们的思路就是，遍历数组，如果遍历到的数与栈顶元素相同，那么栈顶元素出栈，再遍历下一个，如果不同才可以入栈
class Solution {
public:string removeDuplicates(string s) {int n=s.size();stack<char>st;for(int i=0;i<n;i++){if(!st.empty()&&s[i]==st.top()){st.pop();continue;}st.push(s[i]);} string ss="";int t=size(st);for(int i=0;i<t;i++){ss+=st.top();st.pop();}reverse(ss.begin(),ss.end());//记得翻转字符串return ss;}
};
150. 逆波兰表达式求值
这道题的思路就是，当我们碰到的是一个数时，我们就让它入栈，如果碰到一个运算符号，我们就进行对应的运算，再将运算结果入栈
class Solution {
public:int evalRPN(vector<string>& tokens) {// 力扣修改了后台测试数据，需要用longlongstack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）return result;}
};