理论基础
在STL（C++标准库）中，栈和队列往往不被归类为容器，而被归类为container adapter（容器适配器）
- 从图中可以看出，栈对外提供统一的接口，但实际上是以 可插拔的 底层容器来完成其所有的工作的（可以控制究竟使用哪种容器来实现栈的功能）。
- 如果没有指定底层实现的话，默认是以 双向队列deque 作为缺省情况下栈和队列的底层结构。
栈与队列区别
- 实现弹入弹出的方法均为
pop()&push()- 但
pop只实现弹出操作，并不返回弹出元素，需要借助元素获取方法
- 但
- 但栈与队列在元素获取方法上有所不同
- 栈只能获取栈顶stack.top()
- 队列可以同时获取 队头
queue.front()和 队尾queue.back()
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。
思路
- 栈和队列要实现的方法类似，只不过返回结果要遵循不同的输出顺序，因此需要利用两个栈（一个输出、一个输入）来进行调整
- 入队： 相同，进入输入栈；
- 出队： 此时 输入栈（后出）和 预期队列（先出）输出顺序相反，可以借助 输出栈 将现有元素翻转，以塑造为先出，但在输出栈的栈空之前不能再补充元素；
- 返回首部： 与出队操作类似，队头即输出栈的栈顶；
- 判空： 输入栈和输出栈均为空时，判定为队空；
代码实现
class MyQueue {
public:
stack<int> stkIn;
stack<int> stkOut;
MyQueue() {
}
void push(int x) {
stkIn.push(x);
}
int pop() {
if(stkOut.empty()){
while(!stkIn.empty()){
stkOut.push(stkIn.top());
stkIn.pop();
}
}
int result = stkOut.top();
stkOut.pop();
return result;
}
int peek() {
if(stkOut.empty()){
while(!stkIn.empty()){
stkOut.push(stkIn.top());
stkIn.pop();
}
}
int result = stkOut.top(); // 跟pop()基本一样，
return result; // 只不过不stkOut.pop();
}
bool empty() {
return stkIn.empty() && stkOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。
思路
栈作为单向输出的结构，可以通过输入输出栈实现逆序输出，但队列作为两端结构，无论如何组合，都只是更大的队列。
与上题一样，核心还是集中在 出栈 的逻辑上：
- 出栈：想要实现 “后入队的元素先出队”，只要将前面的所有元素挪开即可。但为了在挪开复原时不破坏原有元素顺序，备份容器同样使用一个队列即可。
错误记录：
在写题的时候犯了以下几个错误：
- 直接将
que1.size()放在了for循环终值判断里，没有考虑到持续出队时que1.size()是个变化值。 - 遇到两次出栈就会报错，因为没有初始化：出栈后，需要将
que2里的元素返回给que1，并将que2清空， - 本题返回首部的逻辑跟出栈有所不同，因此不能删除
pop()复用，而是可以直接利用队列的queue.back()简单获取队尾（栈顶）元素
代码实现
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size() - 1;
for(int i=0; i<size; i++){
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
que1 = que2;
while(!que2.empty()){
que2.pop();
}
return result;
}
int top() {
int size = que1.size() - 1;
for(int i=0; i<size; i++){
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
que1 = que2;
while(!que2.empty()){
que2.pop();
}
return result;
}
bool empty() {
return que1.empty() && que2.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路
利用一个匹配栈，将字符串s从左到右送到输入栈中，逐个进行处理：
- 若为左括号
'(' '{' '['则放入匹配栈； - 若为右括号
')' '}' ']'则将 匹配栈 的栈顶元素弹出两者进行匹配：- 若两者类型相同且方向相反，则匹配成功，继续处理；
- 否则该字符串内的括号无效，false；
- 最后匹配栈判空，空则全部有效，有多余括号则false。
代码实现
自己写的：
写的时候犯了一个错误，stk.empty()只能说明无 “左括号多余”，并没有考虑到右括号多余的情况，实际上每次做右括号判断时，都有 匹配栈 内没有左括号stk.empty()的风险，即 “右括号多余”。因此每个 else if 分支都需要加上stk.empty() || ...
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
stk.push(s[i]);
} else if (s[i] == ')') {
if (stk.empty() || stk.top() != '(') return false;
stk.pop();
} else if (s[i] == '}') {
if (stk.empty() || stk.top() != '{') return false;
stk.pop();
} else if (s[i] == ']') {
if (stk.empty() || stk.top() != '[') return false;
stk.pop();
}
}
return stk.empty();
}
};
答案给的简洁版： 先将遍历到的左括号都变成右括号入栈，这样各类型括号的匹配问题就变成了相等问题，而无需分类分支讨论。
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca" 输出："ca" 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
思路
将字符串S中的元素逐个放入栈中，对 当前元素 进行判定：
- 若栈中为空，或与栈顶元素不相等，则 当前元素 入栈；
- 否则（当前元素与栈顶元素相等），则 栈顶元素 出栈。
代码实现
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for(char s : S){
if(st.empty() || s != st.top()){
st.push(s);
}
else{
st.pop();
}
}
// 现在 st 中保存了输出结果的翻转版本
string result;
while(!st.empty()){
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
后记
栈天生适合于做匹配问题，原因在于它可以很轻松的获取：在遍历数组当前元素时候，前一个元素是什么。
