1.栈与队列理论基础
2.C++ stack（STL stack）容器适配器用法详解
3.C++ STL queue容器适配器详解
栈是先进后出，队列是先进先出，用栈实现队列，需要用到两个栈，一个反转元素的入队顺序，另一个存储元素的最终顺序
入栈：
入栈的时候只需要把数据放入输入栈
出栈：
出栈时，如果输出栈为空，那么就将数据按先进后出全部导入输出栈，再从输出栈弹出数据；
如果输出栈不为空，则直接从输出栈弹出数据。
当输入栈和输出栈都为空时，模拟的队列为空。
模拟执行语句：
queue.push(1); queue.push(2); queue.pop(); queue.push(3); queue.push(4); queue.pop(); queue.pop(); queue.pop(); queue.empty();
还要注意的是stack成员函数的具体功能，不能模糊。
class MyQueue {
public:
stackinstack; //定义输入栈
stackoutstack; //定义输出栈
MyQueue() { } //初始化构造函数
void push(int x) { //将元素x推到队列的末尾
instack.push(x);
}
int pop() { //移除队列开头的元素
if (outstack.empty()) { //如果输出栈为空，那么就将数据全部导入输出栈
while (!instack.empty()) { //从输入栈导入直到输入栈为空
outstack.push(instack.top()); //输入栈按后入先出的顺序将元素复制到输出栈，此时的栈顶即为队列开头的元素
instack.pop(); //弹出输出栈栈顶元素
}
}
int result = outstack.top(); //注意top的功能：返回一个栈顶元素的引用，类型为 T&
outstack.pop(); //弹出栈顶元素
return result;
}
int peek() { //返回队列开头元素
int res = this->pop(); //指向的是输出栈的栈顶元素
outstack.push(res); //将弹出的输出栈栈顶元素重新压入输出栈
return res;
}
bool empty() { //当输入栈和输出栈都为空时，模拟的队列为空
return instack.empty() && outstack.empty();
}
};
题目2：225.用队列实现栈
解法一：两个队列
模拟的队列执行语句如下：
queue.push(1); queue.push(2); queue.pop(); // 注意弹出的操作 queue.push(3); queue.push(4); queue.pop(); // 注意弹出的操作 queue.pop(); queue.pop(); queue.empty();
que1存放压入的元素，当要实现弹出操作时，把que1最后面的元素以外的元素都备份到que22，然后弹出最后面的元素，再把其他元素从que2导回que1。
class MyStack {
public:
queueque1; //定义两个队列
queueque2;
MyStack() { } //初始化
void push(int x) { //将元素x压入栈顶
que1.push(x);
}
int pop() { //移除栈顶元素
int size = que1.size(); //当que1中元素的个数减少
size--;
while (size--) { //将que1导入que2，只留下最后一个元素
que2.push(que1.front()); //成员函数push(const T& obj) 功能：在 queue 的尾部添加一个元素的副本
que1.pop(); //删除que1中的第一个元素
}
int result = que1.front(); //留下的最后一个元素就是要返回的值
que1.pop(); //删除que1中留下的值
que1 = que2; //再将que2赋值给que1
while (!que2.empty()) { //清空que2
que2.pop();
}
return result;
}
int top() { //返回栈顶元素
return que1.back();
}
bool empty() { //返回栈是否为空
return que1.empty();
}
};
解法二：一个队列
但用队列实现栈用一个队列就够了
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
class MyStack {
public:
queueque; //定义队列
MyStack() { } //初始化
void push(int x) { //将元素x压入栈顶
que.push(x);
}
int pop() { //移除栈顶元素
int size = que.size();
size--;
while (size--) { //将队列头部的元素(除了最后一个元素外)重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); //此时弹出的元素顺序就是栈的顺序
que.pop();
return result;
}
int top() { //返回栈顶元素
return que.back();
}
bool empty() { //返回栈是否为空
return que.empty();
}
};
题目3：20.有效的括号
解法：栈
解题思路：
如果遍历字符串，计算左括号和右括号的数量，看左右括号的数量是否相等，这种是不可行的，如[ { ] }
由于栈结构的特殊性，比较适合做对称匹配。
首先列出括号不匹配的情况：
1.字符串中左边括号多余：
2.括号不多余，但括号类型不匹配：
3.字符串中华右边括号多：
将括号放入栈中，如果是有效的括号，就可以将这对括号从栈中删除，那么最后栈为空。
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false。
class Solution {
public:
bool isValid(string s) {
stackst;
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(']');
}
else if (st.empty() || st.top() != s[i]) { //第三种和第二种情况
return false;
}
else {
st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
}
return st.empty(); //遍历完了字符串，栈若为不为空则情况一、return false，否则就return true
}
};
这一题官方也给出了一种栈的解法:
class Solution {
public:
bool isValid(string s) {
int n = s.size(); //判断s长度若为奇数，则一定不成对，返回false
if (n % 2 == 1) {
return false;
}
//定义一个辅助栈，判断')'在s中是否有对应的'('
unordered_map pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack stk;
for (char ch : s) {
if (pairs.count(ch)) { //判断ch是否为右括号
//判断栈是否为空或者栈顶元素是否等于ch的value，若满足其中一个则返回false
//若栈为空则表示，右括号在做左括号前面；若栈顶元素和ch的value不相等，则不匹配
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
题目4：1047.删除字符串中的所有相邻重复项
解法：栈
解题思路：
也是匹配问题，其实和20题一样，相同左元素相当于左括号，相同右元素相当于右括号，匹配上了删除即可
因此可以遍历字符串，将其放到栈中，如果有相同元素栈就弹出
class Solution {
public:
string removeDuplicates(string S) {
stack st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string result = "";
while (!st.empty()) { // 将栈中元素放到result字符串汇总
result += st.top();
st.pop();
}
reverse (result.begin(), result.end()); // 此时字符串需要反转一下
return result;
}
};
可以拿字符串直接作为栈
class Solution {
public:
string removeDuplicates(string S) {
string result;
for(char s : S) {
if(result.empty() || result.back() != s) {
result.push_back(s);
}
else {
result.pop_back();
}
}
return result;
}
};
