232.用栈实现队列
思路
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
代码实现
//栈和队列是stl（c++标准库）里的两个数据结构
//sgi stl是基于sp stl实现的，被Linux采用的开源软件，可读性甚高
//deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了
这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。
//使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要
//两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
class MyQueue {
public:
stack<int> stIn;//定义两个栈，一个是入口一个是出口。
stack<int> stOut;
/** 初始化数据结构 */
MyQueue() {
}
void push(int x){
stIn.push(x);//入栈操作
}
int pop(){
if(stOut.empty()){//如果出栈为空的话，
while(!stIn.empty){//且stack in不为空
stOut.push(stIn.top());//出栈就把所有元素都吸收了
stIn.pop();//接着把入栈（那个栈？）的元素pop（输出？）
// 应该还是入口栈，意思就是把入口站的元素给予出口栈
}
int result = stOut.top();//用result收集结果，
stOut.pop();//出口栈将元素弹出（pop）
return result;
}
// 可以看出peek()的实现，直接复用了pop()， 要不然，对stOut判空的逻辑又要重写一遍。
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
};
}
注意
可以看出peek()的实现，直接复用了pop()， 要不然，对stOut判空的逻辑又要重写一遍。
225. 用队列实现栈
思路
队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
优化其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了
代码展示
//225. 用队列实现栈
//其实这道题目就是用一个队列就够了。
//一个队列在模拟栈弹出元素的时候只要将队列头部的
//元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
class MyStack {
public:
queue<int> que;
/** 初始化一个数据结构 队列 */
MyStack() {
}
/** 把元素放进队列中 */
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();//获取队列的size
size--;//这就是size-1，即把 除了最后一个元素的之前的元素弹出
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());//再把弹出的元素加入队列的头部
que.pop();//front仅仅取了第一个元素，pop才是真正的弹出
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();//弹出初始队列的最后元素
return result;
}
/** 获取栈里面的第一个元素，而不用弹出 */
int top() {
return que.back();//这里的back就是队列里入口处的第一个元素
}
20. 有效的括号
题目链接：20. 有效的括号
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
思考
括号匹配是使用栈解决的经典问题。
这里有三种不匹配的情况，
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第二种情况，括号没有多余，但是 括号的类型没有匹配上。
第三种情况，字符串里右方向的括号多余了，所以不匹配；
只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目。
代码展示
class Solution {
public:
bool isValid(string s){
if(s.szie() % 2 != 0) return false;
stack<char> st;
for(i = 0; i < s.size(); i++){//开始遍历
// 这里是第一种情况--字符串里左方向的括号多余了 ，所以不匹配
if(s[i] == '(') st.push(')');//如果初始为左括号（，那么在栈里push一个）
else if(s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');//同上，只不过左括号类型不一样
//第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号
//第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if(st.empty() || st.top() != s[i]) return false; //st.empty()是第三； st.top() != s[i]是第二
else st.pop();
}
return st.empty();
//已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
}
}
1047. 删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项
题目描述：
示例：
输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
思考
本题要删除相邻相同元素，相对于20. 有效的括号 (opens new window)来说其实也是
匹配问题，20. 有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。
本题也是用栈来解决的经典题目。
当然可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作
代码展示
//1047. 删除字符串中的所有相邻重复项、
定义一个字符串，目的是来模拟栈的行为
string result;
for(char s : S){//c++遍历形式代码。s取了S里的
if(result.empty() || s != result.back() ){//两种情况；
// 一种是类似栈的形式为空；一种是字符串首元素和字符串的back（即类似栈的栈顶）
result.push_back(s);//则把S的元素放入类似栈的字符串中
else return.pop_back();//若相等元素，则从尾部bak弹出该元素
}
}
return result;
150. 逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
题目描述：即后缀表达式的计算
示例 1：
输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
思路
其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后序遍历的方式把二叉树序列化了，就可以了。
如动画所示：
这和1047. 删除字符串中的所有相邻重复项 (opens new window)是差不错的，只不过本题不要相邻元素做消除了，而是做运算！
代码所示
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
stack<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;
}
};