目录
1.用两个栈实现队列（剑指offer 9 ）
2.包含min函数的栈（剑指offer 30 ）
3.栈的压入弹出顺序（剑指offer 31）(重要)
4.滑动窗口的最大值（剑指offer 59 ） （重要）
题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路：
栈是先入后出，而队列是先入先出， 维护两个栈，一个push栈，一个pop栈. 入队操作： 无脑压入push栈
出队操作：假如pop栈非空，直接弹栈顶元素完事 假如pop空，而就把push栈依次弹出，并且压入stack2，最后弹个pop的栈顶。 假如两个栈都空，就啥事不干。
代码：
class Solution { public: void push(int node) { stack1.push(node); } int pop() { if(stack1.empty() && stack2.empty()) return -1; int res; if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } } res = stack2.top(); stack2.pop(); return res; } private: stack<int> stack1; stack<int> stack2; };
相关：两个队列实现栈
跟上一题的解法不一样
任何时候两个队列总有一个是空的。添加元素总是向非空队列中 add 元素。取出元素的时候总是将非空的那个队列，所有元素除队尾最后一个元素外，依次导入另一空队列中，最后一个元素出队，返回。
题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解题思路：
两个栈，一个正常栈，一个min栈 压入： 压a的时候，正常栈直接压a，而压入min栈的时候，跟min栈顶b比较一下，假如a小于b，压a，假如a大于等于b，压b (min栈空的时候，直接压) 弹栈： 两个栈都正常弹 返回min，直接返回min的栈顶
代码：
class Solution { public: void push(int value) { s1.push(value); if(minstack.empty()) minstack.push(value); else if(value <= minstack.top()) minstack.push(value); else minstack.push(minstack.top()); } void pop() { s1.pop(); minstack.pop(); } int top() { return s1.top(); } int min() { return minstack.top(); } private: stack<int> s1; stack<int> minstack; };题目描述：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解题思路：
建立一个辅助栈，按压栈顺序压栈，按出栈顺序出栈 具体办法： 用i遍历出栈顺序（for循环），如果下一个要出栈的数字，在辅助栈s1顶则，直接出栈，i前进一位，即进入下一个循环，如果辅助栈为空或者不在，则按压栈顺序压一个，并重新判断，重复这个过程，如果压栈顺序里面所有数字都压进去了，还没有找到下一个弹出的数字，则不可能是出栈顺序。
代码：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.size() != popV.size()) return false; stack<int> s1; int index =0; for(int i=0;i<popV.size();++i){ //如果下一个要弹出的数字 popV[i] 不在栈s1顶，那么按压栈顺序pushV[index++]压栈，直到popV[i] 压进去 //过程中 检查 pushV都压进去了，那就不是一个弹出顺序 while(s1.empty() || s1.top() != popV[i]){ if(index >=pushV.size()) return false; s1.push(pushV[index++]); } s1.pop(); } return 1; // 压栈 012345 弹栈45321 为了防止这种情况 } };题目描述：
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
假如数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
解题思路：
中心思想： 如果我比你大，我来了，你就得滚。用双端队列deque 放下标 or 放pair也行 下标+值 维持一个从大到小的结构 队列头永远是最大的。
deque放下标，输入数组是arr，依次遍历arr，deque每次执行加数和减数操作。 假设现在遍历到arr[i]
加数： 1）deque为空，直接把下标i放进deque 2）deque不为空，取出deque队尾放的下标j，arr【j】跟arr【i】比较，假如，arr【i】<=arr【j】，把i放进去，假如小于，deque把j给弹出来，新队尾继续跟arr[i]比较，直到遇到比arr[i]大或者deque为空，那把i加进来
其实就是
while(!qmax.empty() && num[i]>num[qmax.back()]){ qmax.pop_back(); }
减数逻辑： 假如deque队头的值是x， i-x+1>w,说明这个下标已经过期了，弹出来（因为新窗口最右端是i，窗口大小是w）
先加逻辑 再减逻辑
代码：
class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { int len= num.size(); vector<int> res; if(len == 0 || size ==0 ) return res; // 假如size比num要大 /* if(size>= len){ int m = num[0]; for(int i=0;i!=len;++i){ m = max(m,num[i]); } res.push_back(m); return res; } */ if(size>len){ // 我寻思铁子也没说清 当窗口比数组大的时候咋变啊 return res; } //存的是下标 deque<int> qmax; for(int i=0;i!=len;++i){ //如果当前值比队列的最尾部值num[q.back()]大，那么删除队列尾部，保证最大值在队列首部 while(!qmax.empty() && num[i]>num[qmax.back()]){ qmax.pop_back(); } qmax.push_back(i); //加入新数 if(i-qmax.front()+1>size){ qmax.pop_front(); //如果最大值超过了size的区间(i-qmax.front()+1)，那么就把最大值删除 } if(i>=size-1){ res.push_back(num[qmax.front()]); //存放数值 } } return res; } };
