栈和队列是非常经典的数据结构，基本上是随处可见了。
为什么把这两者放在一起说呢？
因为对于C++的STL来说，这两者都是容器适配器，默认都是以deque为底层实现的。
我们都知道栈是【先进后出】，队列是【先进先出】
使用双端队列deque并且进行一些加工就可以实现栈和队列的效果，这也是STL中栈和队列的实现方式。
具体细节可以看这篇笔记：
【STL源码剖析】总结笔记（7）：巧妙的deque
栈和队列互相实现
有一类题目是栈和队列的相互实现，比如用栈实现队列或者用队列实现栈。
虽然没有太明显的实际意义，但是对于理解栈和队列的结构至关重要。
用栈实现队列
用栈实现队列就要思考队列的特点，那些是栈需要调整的。
入队列和入栈一致，不需要修改。
而出队和出栈恰好相反，所以我们需要两个栈来对栈内的数据进行处理。
比如想实现1，2，3入队列然后1出队。
这时候要把1号栈中的[1,2,3]全部出栈，再放入2号栈变为[3,2,1]，这时出栈的就是队头。
如果1出队后，变为[2,3]，此时[4,5]又入栈了怎么办呢？
这就要看2号栈里是否还有数据，如果有那么还是存在队头的，不需要把新数据倒入。
class MyQueue {
public:
stack<int>stack1;
stack<int>stack2;
MyQueue() {
}
void push(int x) {
stack1.push(x);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int res=stack2.top();
stack2.pop();
return res;
}
int peek() {
int res=pop();//直接复用pop()
stack2.push(res);
return res;
}
bool empty() {
return stack1.empty()&&stack2.empty();
}
};
需要注意：
在stack中的pop()会直接把栈顶元素删除，而不会返回值。所以想要实现题目中的pop()需要先记录再pop()
peek()这个地方直接复用了写好的pop()函数，因为需要队列的头元素，所以复用更高效。
用队列实现栈
队列实现栈就要考虑栈的特点和队列有什么差异。
队列入队和栈入栈还是一致的，不需要改动。
出队因为是队头，而栈需要出的元素在队尾，所以需要调整。
这里我们不使用新的空间，直接把前面的元素搬到队尾的后面，再次入队。
比如[1,2,3,4]，弹出栈头应该是4，我们把前面的元素重新入队，得到[4,1,2,3]，再弹出4即可。
class MyStack {
public:
queue<int>que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size=que.size();
while(size>1){
que.push(que.front());
que.pop();
size--;
}
int res=que.front();
que.pop();
return res;
}
int top() {
int res=pop();//复用写好的pop()
que.push(res);
return res;
}
bool empty() {
return que.empty();
}
};
同理，top就可以直接复用写好的pop()。
符号匹配
栈的一大作用就是符号的匹配，我们来看两道这样的题目
括号匹配
在判断括号匹配时用栈会方便很多。
给定一个字符串，判断括号是否有效。
"()[]{}“这样就是有效的组合，而”[)"则不是有效的组合。
需要特别注意，"([)]"这种类型即使看上去数量是对的，也不符合正确的括号闭合。
核心：
我们的核心做法就是使用栈进行匹配。
遇到比如"(“，我们直接存入栈”)“，因为如果结果正确那么后面也会有”)"，这样就可以相互抵消。
抵消过程就是当前的元素和栈顶比较，如果相等就出栈即可，一层一层解开嵌套。
如果抵消失败说明不符合要求。
最后如何判断是否成功呢？只要循环结束后栈空就说明成功。
我们在循环内也有栈空的情况，也就是没有遇到左括号，这个时候返回false。
而整个循环外的栈空就说明已经全部配对了，所以是true。
bool isValid(string s) {
stack<char>stack1;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
stack1.push(')');
}
else if(s[i]=='['){
stack1.push(']');
}
else if(s[i]=='{'){
stack1.push('}');
}
else if (stack1.empty() || stack1.top() != s[i]) return false;//与栈顶不对应
else stack1.pop();//对应就弹出
}
return stack1.empty();
}
逆波兰表达式
逆波兰式是计算机中一种重要的算术表达方式。
比如(2+1)*3，我们需要使用括号来表示优先级。
而改为逆波兰式就是2 1 + 3 *
解释为2和1用+计算，然后结果再与3用*计算，这样不需要括号也可以区分优先级。
还有一点小知识，逆波兰式其实是二叉树的后序遍历。
我们以运算符为父节点，数字为子节点就可以画出这棵树。
给出逆波兰表达式，求出运算结果。
我们依旧使用栈，在遇到数字时入栈，遇到符号就把前两个数提出来做计算，再将新值入栈。
int evalRPN(vector<string>& tokens) {
stack<int>sta;
for(int i=0;i<tokens.size();i++){
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){//遇到运算符就取数
int num1=sta.top();
sta.pop();//取值后清空
int num2=sta.top();
sta.pop();//取值后清空
//再压入运算值
if(tokens[i]=="+")
sta.push(num1+num2);
if(tokens[i]=="-")
sta.push(num2-num1);
if(tokens[i]=="*")
sta.push(num1*num2);
if(tokens[i]=="/")
sta.push(num2/num1);
}
else{//stoi是将字符转换为数字
sta.push(stoi(tokens[i]));
}
}
return sta.top();//最后栈中剩余的就是计算结果。
}
单调栈
单调栈是以栈为基础的一种数据结构，但是做了一些属性的修改，保证栈内的元素具有单调性。
基本逻辑
先来看一道题
给定一个nums1和nums2，根据nums1找到nums2对应的元素，然后在nums2中寻找右侧第一个比该元素大的数。
比如nums1=[4,1]，nums2=[1,3,4,2]
对于4来说，在nums2中4的右侧没有比它大的，所以返回-1
对于1来说，在nums2中1的右侧第一个比它大的是3
最后返回[-1,3]
这就是整道题的逻辑
单调栈的遍历方法
在这之前，我们先简化上一道题的场景。
对于nums1和nums2，我们去掉nums1，留下nums2。
只找nums2对应元素的右侧第一个比它大的元素。
比如[1,3,4,2]
返回结果应该是[3,4,-1,-1]
从这里开始我们构建单调栈。
核心：
如果我们将[1,3,4,2]入栈遍历，应该如何进行呢？
因为我们要找的是右侧第一个比它大的元素，要看右边，所以最好的入栈方式是倒着入栈。
上例中就应该按照2，4，3，1的顺序来。
判断条件也比较清楚：如果当前这个数比已经入栈的元素（栈顶）大（或者等于），那说明已经入栈的元素不是它右侧第一个大的元素，直接把入栈元素弹出即可。
最后这个位置的答案就是栈顶元素，没有即为-1
按2，4，3，1走一遍。
2先遍历，因为栈为空，所以表示没有2右侧大于它的元素，返回-1，2入栈
然后遍历到4，因为4>2，所以2不是目标值，故弹出2。然后返回-1，4入栈
然后到3，因为3<4，所以4是目标值，结果为栈顶4，然后3入栈
最后是1，因为1<3，所以3是目标值，结果为栈顶3，然后1入栈
最后返回结果数组即可。
stack<int>sta;
vector<int>res(nums.size());
for(int i=nums.size()-1;i>=0;i--){
while(!sta.empty()&&nums[i]>=sta.top()){
sta.pop();
}
if(sta.empty())
res[i]=-1;
else
res[i]=sta.top();
sta.push(nums[i]);
}
return res;
再回到我们的题目中，因为有nums1和nums2，我们可以用一个哈希表存放nums2和对应的下一个更大元素，然后遍历nums1将对应的哈希表中的数值取出即可。
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int>map;
stack<int>sta;
vector<int>res(nums1.size());
for(int i=nums2.size()-1;i>=0;i--){
while(!sta.empty()&&nums2[i]>=sta.top()){
sta.pop();
}
if(sta.empty())
map[nums2[i]]=-1;
else
map[nums2[i]]=sta.top();
sta.push(nums2[i]);
}
for(int i=0;i<nums1.size();i++){
res[i]=map[nums1[i]];
}
return res;
}
每日温度
再看一道变体的题目，大同小异。
给定一个数组，返回的是再走几个数就可以得到比它大的下一个元素。
与上题的区别就是，上题返回的是比它大的下一个数，而该题返回的是距离。
返回距离也很简单，我们只需要操作下标就可以了。把原来栈内的元素换成下标。
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int>s;
vector<int>res(temperatures.size());
for(int i=temperatures.size()-1;i>=0;i--){
while(!s.empty()&&temperatures[i]>=temperatures[s.top()] ){
s.pop();
}
res[i]=s.empty()?0:(s.top()-i);
s.push(i);
}
return res;
}
逻辑和上题没有任何区别
升级版下一个更大元素
下一个更大元素还有一道升级版的题目：
给定一个数组，比如[1,2,1]，按照我们的正常求法求下一个更大元素，返回的是[2,-1,-1]
而本题让数组循环，1并不是结尾，而是继续回到起始位置重新循环。
这时返回的就是[2,-1,2]
很明显，我们只要把给定的数组double，变成[1,2,1,1,2,1]就可以正确返回前三个元素的下一个更大元素了。
而对于for循环来说，因为控制的是下标，所以并不需要真正的去扩展数组。
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int>sta;
vector<int>res(nums.size());
int n=nums.size();
for(int i=n*2-1;i>=0;i--){//遍历两倍的长度
while(!sta.empty()&&nums[i%n]>=sta.top()){
sta.pop();
}
res[i%n]=sta.empty()?-1:sta.top();
sta.push(nums[i%n]);
}
return res;
}
这里的精髓就是将for循环的长度变为两倍，然后使用取模的方法使结果只存在长度为n的数组中。
单调队列
单调队列，和单调栈性质一样，使队列维持一个具有单调性的状态。
想要让队列保持单调性，就要在入队和出队的时候做一些处理。
这里我们直接来看一道经典题目，体会自己实现单调队列的方法。
给定一个数组和窗口大小，返回这个窗口内的最大值，然后移动窗口。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
单调队列的核心
这个窗口的移动很像队列的出入队操作。但是我们想让队列直接帮我们求出最大值。
所以我们实现一个单调队列，以deuqe为基础（因为可以在队头和队尾进行插入删除操作，很灵活）
单调队列有这样几个重点：
- 想要获得最大值，那么要在入队时和上一个入队的元素比较，比上一个大的话上一个元素就没有必要留下来，删掉即可。
- 在窗口滑动时要出队，而这时出队只有一种情况：要移出窗口的元素和队头元素相等。（因为不够大的元素已经被动踢出去了）
举个例子：[1,3,-1,-3,5,3,6,7]
1入队，3入队时发现比1大，所以1出队。
-1入队，这时候队列为[3,-1]
窗口移动，因为需要移出去的1和队列的3不匹配，所以队列不需要动。
-3入队，队列为[3,-1,-3]
窗口移动，这时候需要移出去的是3，队头也是3，所以pop。
5入队，发现比-3大，删除-3，又比-1大。，删除-1
这时候的队列为[5]
…后面以此类推。
所以单调队列的实现我们就可以写出来了：
deque用到的操作有：push_front()，push_back()，pop_front()，pop_back()
class MyQueue{
public:
deque<int>myque;
void push(int value){
while(!myque.empty()&&value>myque.back()){//如果入队比前面的元素大，把前面的元素弹出
myque.pop_back();
}
myque.push_back(value);//入队
}
void pop(int value){
if(!myque.empty()&&myque.front()==value){//只有相等时才真正出队，否则不需要操作
myque.pop_front();//队头是要出队的方向
}
}
int max(){
return myque.front();//队头就是最大的元素。
}
};
有了单调队列，我们就可以根据窗口移动的方式，往队列里放元素，让单调队列给我们最大值。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int>res;//结果集
for(int i=0;i<k;i++){//先放窗口大小的元素
que.push(nums[i]);
}
res.push_back(que.max());//存第一个最大值
for(int i=k;i<nums.size();i++){//循环后面的值，出队入队并且记录最大值
que.pop(nums[i-k]);
que.push(nums[i]);
res.push_back(que.max());
}
return res;
}
其他
还有一些与优先级队列有关的题目，我们在总结完二叉树之后继续探究。
