栈与队列理论基础
队列是先进先出，栈是先进后出
栈与标准库剖析：
首先大家要知道 栈和队列是STL（C++标准库）里面的两个数据结构。
C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。
那么来介绍一下，三个最为普遍的STL版本：
-
HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
-
P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
-
SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
在STL中，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列，只要封住一端，只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈,vector作为底层容器可插拔
队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
所以STL 队列也不被归类为容器，而被归类为container adapter（容器适配器）。
232.用栈实现队列
题目链接：232.用栈实现队列
文档讲解：代码随想录
状态：轻松AC
思路
思考过程：一个栈一定实现不了队列，思考两个，两个栈相互反转就相当于正，即正向队列。
需要注意的细节：出栈时取最后一个，要把输入栈的所有元素加入输出栈。
if(s2.empty())
{
while(!s1.empty())//转移操作
{
int x = s1.top();
s1.pop();
s2.push(x);
}
}
一定切记：.pop()方法只删除不返回，.top()和.front()才返回。
代码复用问题，理解本题中peek方法复用pop。
题解
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
s1.push(x);
}
int pop() {
if(s2.empty())
{
while(!s1.empty())//转移操作
{
int x = s1.top();
s1.pop();
s2.push(x);
}
}
int result = s2.top();
s2.pop();
return result;
}
int peek() {
// if(s2.empty())
// {
// while(!s1.empty())//转移操作
// {
// int x = s1.top();
// s1.pop();
// s2.push(x);
// }
// }
// return s2.top();
int result = this->pop();
s2.push(result);
return result;
}
bool empty() {
return s1.empty() && s2.empty();
}
private:
stack<int> s1;
stack<int> s2;
};
225. 用队列实现栈
题目链接：225. 用队列实现栈
文档讲解：代码随想录
状态：两种方法轻松AC思路
一个队列有两个口（入与出），即一个队列就可模拟栈，这也是双向队列可以作为栈的底层数据结构的原因。
两个队列：主队列接收数据，暂存队列在front或pop时暂存所有非末尾数。
一个队列：循环队列可解，充分理解队列的数据结构。
题解
// class MyStack {
// public:
// queue<int> q1;
// queue<int> q2;
// MyStack() {
// }
// void push(int x) {
// q1.push(x);
// }
// int pop() {
// while(q1.size()>1)
// {
// int x = q1.front();
// q1.pop();
// q2.push(x);
// }
// int result = q1.front();
// q1.pop();
// while(q2.size()>0)
// {
// int x = q2.front();
// q2.pop();
// q1.push(x);
// }
// return result;
// }
// int top() {
// int result = this->pop();
// q1.push(result);
// return result;
// }
// bool empty() {
// return q1.empty() && q2.empty();
// }
// };
class MyStack {
public:
queue<int> q;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
for(int i = 0;i<q.size()-1;i++)
{
int temp = q.front();
q.pop();
q.push(temp);
}
int result = q.front();
q.pop();
return result;
}
int top() {
int result = this->pop();
q.push(result);
return result;
}
bool empty() {
return q.empty();
}
};
20. 有效的括号
思路
栈常应用于按顺序、成对出现的匹配（关于自身对称），如程序中括号匹配。
明确好用栈数据结构，思考本题所注意细节：
匹配成功很简单，只需要)、]、}与栈顶元素成对即可
失败的情况有很多，先想全再编码，而不是面向结果编程
失败情况：
题解
class Solution {
public:
bool isValid(string s) {
//完全是栈的思想
if(s.size()%2 != 0)return false;
map<char,char> chart = //二维数组，每对为括号（因网站原因不能输入）;
stack<char> st;
for(int i = 0;i<s.size();i++)
{
if(chart.find(s[i])!=chart.end())st.push(chart[s[i]]);
else if(!st.empty() && s[i] == st.top())st.pop();
else return false;
}
return st.empty();
}
};
1047.删除字符串中的所有相邻重复项
题目链接：1047.删除字符串中的所有相邻重复项
文档讲解：代码随想录
状态：利用栈轻松AC
思路
完全按照栈的数据结构量身打造，熟悉各个数据结构的用途是关键
题解
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i = 0;i<s.size();i++)
{
if(!st.empty() && s[i] == st.top())st.pop();
else st.push(s[i]);
}
string result("");
while(!st.empty())
{
char temp = st.top();
st.pop();
result += temp;
}
reverse(result.begin(),result.end());
return result;
}
};