232、用栈实现队列
建立两个栈，一个栈输入，一个栈输出。若输出栈为空，将输入栈元素转移到输出栈中，经过两次先进后出，就会变成先进先出
注意：
top() 函数：返回栈顶元素但不删除
pop()函数：没有返回值，删除栈顶元素
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()) {
int tem = stIn.top();
stIn.pop();
stOut.push(tem);
}
}
int res = stOut.top();
stOut.pop();
return res;
}
int peek() {
int res = this->pop();
stOut.push(res);
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};时间复杂度：push和empty为O(1)，pop和peek为O(n)
空间复杂度：O(n)
225、用队列实现栈
注意：
front 返回队首元素，但不删除
pop 没有返回值，删除队首元素
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
while(--size) {
int tem = que.front();
que.pop();
que.push(tem);
}
int res = que.front();
que.pop();
return res;
}
int top() {
int res = this->pop();
que.push(res);
return res;
}
bool empty() {
return que.empty();
}
};时间复杂度：push和empty操作为O(1)，pop和top为O(n)
空间复杂度：O(n)
20、有效的括号
建立栈，将左括号入栈；遍历到右括号时，判断栈顶是否有对应的左括号，如果有弹出栈顶元素，继续遍历，没有则返回false
class Solution {
public:
bool isValid(string s) {
if(s.size()%2 == 1) return false;
stack<char> st;
for(int i = 0; i < s.size(); i++) {
if(s[i] == ')') {
if(st.empty() || st.top() != '(') {
return false;
}else {
st.pop();
}
}else if(s[i] == '}') {
if(st.empty() || st.top() != '{') {
return false;
}else {
st.pop();
}
}else if(s[i] == ']') {
if(st.empty() || st.top() != '[') {
return false;
}else {
st.pop();
}
}else {
st.push(s[i]);
}
}
return st.empty();
}
};时间复杂度：O(n)
空间复杂度：O(n)
1047、删除字符串中的所有相邻重复项
建立栈，遍历字符串；每遍历一个元素，判断与栈顶元素相不相同，若相同，弹出栈顶元素，若不相同，入栈；最终得到的栈输出序列为答案的倒序，reverse反转一下
class Solution {
public:
string removeDuplicates(string s) {
stack<int> st;
for(int i = 0; i < s.size(); i++) {
if(st.empty() || st.top() != s[i]) {
st.push(s[i]);
}else {
st.pop();
}
}
string result;
while(!st.empty()) {
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
};时间复杂度：O(n)
空间复杂度：O(n)
