📁 JZ9 用两个栈实现队列
一个栈in用作进元素，一个栈out用于出元素。当栈out没有元素时，从in栈获取数据，根据栈的特性，栈out的top元素一定是先进入的元素，因此当栈out使用pop操作时，一定时满足队列的特性的。
class Solution
{
public:void push(int node) {s1.push(node);}int pop() {if(s2.empty()){while(!s1.empty()){int top = s1.top();s1.pop();s2.push(top);}}int top = s2.top();s2.pop();return top;}private:stack<int> s1;stack<int> s2;
};📁 JZ30 包含min函数的栈
一个栈s1用于存放所有元素，一个栈s2用于存放最小元素以及在入栈之前的那些最小元素。
class Solution {
public:void push(int value) {s1.push(value);if(s2.empty() || value <= s2.top())s2.push(value);}void pop() {if (s1.top() == s2.top()){s1.pop();s2.pop();}else {s1.pop();}}int top() {return s1.top();}int min() {return s2.top();}
private:stack<int> s1;stack<int> s2;
};📁 JZ31 栈的压入、弹出序列
使用stack模拟进栈和出栈，如果能模拟出来返回true，不能返回false。
class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> s;int i=0;for(auto& e : pushV){s.push(e);while(!s.empty() && s.top() == popV[i]){s.pop();++i;}}return s.empty();}
};📁 JZ73 翻转单词序列
以空格为分隔符，取出每一个单词放入栈中，根据栈的性质出栈完成单词翻转。
#include <string>
class Solution {
public:string ReverseSentence(string str) {stack<string> s;int i=0,j=0;while(i < str.length()){j = i;while(j < str.length() && str[j] != ' ')++j;s.push(str.substr(i,j-i));i = j+1;}string newStr;while(!s.empty()){newStr += s.top();s.pop();if(!s.empty())newStr += " ";}return newStr;}
};📁 JZ59 滑动窗口的最大值
📁 JZ59 滑动窗口的最大值
根据性质，得出当有一个较大值进入窗口时，所有比他小的元素不影响结果，因此我们就可以使用一个双端队列来完成：当一个较大值进入时，移除所有比它小的之前进入的元素。
双端队列的队头就是该窗口内的最大值下标。为什么这里采用下标呢，因为为了方便处理判断该元素是否还在窗口内。
vector<int> maxInWindows(vector<int>& num, int size) {vector<int> ret;deque<int> dq;if(num.size() < size || size <= 0)return ret;//找第一个窗口for(int i = 0 ; i < size ; ++i){//插入新元素时, 去除比他小的之前的元素（下标）while(!dq.empty() && num[dq.back()] < num[i])dq.pop_back();dq.push_back(i);} for(int i = size; i < num.size() ; ++i){ret.push_back(num[dq.front()]);//窗口后移, 窗口之前的元素去掉while(!dq.empty() && dq.front() < (i-size+1))dq.pop_front();//插入新元素时, 去除比他小的之前的元素while(!dq.empty() && num[dq.back()] < num[i])dq.pop_back();dq.push_back(i);}ret.push_back(num[dq.front()]);return ret;}
