📁?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;}
