用两个栈模拟一个队列

【题目链接】
将一个栈当作输入栈，用于压入 appendTail
传入的数据；另一个栈当作输出栈，用于 deleteHead操作。

每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

class CQueue {
public:CQueue() {}void appendTail(int value) {pushS.push(value);}int deleteHead(){if(popS.empty()){if(pushS.empty()){return -1;}while(!pushS.empty()){int top=pushS.top();pushS.pop();popS.push(top);}}int Del=popS.top();popS.pop();return Del;}stack<int> pushS;//进数据stack<int> popS;//出数据
};

用两个队列实现栈

【题目链接】
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

方案一
通过不断交换两个队列中的值保证其中一个队列中有我们想要弹出的数据

class MyStack {
public:queue<int>  q1;queue<int> q2;MyStack() {}void push(int x) {if(q1.empty() && q2.empty()){q1.push(x);return;}else if(!q1.empty()){q1.push(x);}else if(!q2.empty()){q2.push(x);}}int pop() {int Pop;if(q2.empty()){while(q1.size()>1){q2.push(q1.front());q1.pop();}Pop=q1.front();q1.pop();return Pop;}if(q1.empty()){while(q2.size()>1){q1.push(q2.front());q2.pop();}Pop=q2.front();q2.pop();return Pop;}return Pop;}int top() {if(!q1.empty())return q1.back();else if(!q2.empty())return q2.back();    return 0;   }bool empty() {return q1.empty() && q2.empty(); }
};

方案二
通过交换整个队列保证其中一个队列从表面上看，队头==栈顶，然后pop和top就很简单


class MyStack {
public:queue<int> q1;queue<int> q2;MyStack() {}void push(int x) {q2.push(x);while(!q1.empty()){q2.push(q1.front());q1.pop();}swap(q1,q2);//经过此次转化，q1队列队头就相当于栈顶}int pop() {int del=0;if(!q1.empty()){del=q1.front();q1.pop();}return del;}int top() {return q1.front();}bool empty() {return q1.empty() && q2.front();}
};

剑指 Offer 58 - I. 翻转单词顺序

【题目链接】
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

示例 1：

输入: “the sky is blue” 输出: “blue is sky the” 示例 2：

输入: " hello world! " 输出: “world! hello” 解释:
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：

输入: “a good example” 输出: “example good a” 解释:
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路：
把字符串按空格分割完毕存放到栈中，然后利用栈的特性完成

class Solution {
public:string reverseWords(string s) {stack<string> wordStack;  // 用栈存储单词string word = "";  // 存储当前单词string result = "";  // 存储结果// 遍历字符串for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {  // 遇到空格，把当前单词入栈if (word != "") {wordStack.push(word);word = "";}}else {  // 不是空格，把字符添加到当前单词word += s[i];}}// 把最后一个单词入栈if (word != "") {wordStack.push(word);}// 把单词出栈，拼接成结果字符串while (!wordStack.empty()) {result += wordStack.top();wordStack.pop();if (!wordStack.empty()) {result += " ";}}return result;}
};

剑指 Offer 59 - I. 滑动窗口的最大值

【题目链接】
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: 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

蛮力法：超出时间限制

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//蛮力法vector<int> v;int len=nums.size();for(int i=0;i<len-k+1;++i){int MinNUm=INT_MIN;for(int j=i;j<i+k;++j){MinNUm=MinNUm>nums[j]?MinNUm : nums[j];}v.push_back(MinNUm);}return v;}
};

优先级队列
利用堆的特性：大根堆堆顶最大。初始时，我们先将数组前 k 个元素放入优先队列中。每当我们向右移动窗口时，把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，如（[4,2,3,2] 3），在这种情况下，初始化最大值是4，移动一次之后窗口里面没有4，但是4还在堆顶，我们要想办法去掉，由于这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其移除队列。

我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。我们可以使用pair存储一个键值对，数据：对应数组下标，当满足【滑动窗口最右边下标-堆顶元素对应的下标>=k】时，就可以删除堆顶元素

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();priority_queue<pair<int, int>> pq;//找到第一个滑动窗口最大值for (int i = 0; i < k; ++i) {pq.emplace(nums[i], i);}vector<int> v= {pq.top().first};//添加第一个最大值for (int i = k; i < n; ++i) {pq.emplace(nums[i], i);while ((pq.top().second+k) <= i ) {//如果栈顶元素不在滑动窗口中，删除，如[423]2 ;4[232]pq.pop();}v.push_back(pq.top().first);}return v;}
};

双端队列
把有可能成为滑动窗口最大值的数据存放进一个双端队列：当右滑遇到的元素比当前队列尾部元素大的时候，那么尾部元素就不可能成为最大值，删除！不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
这就能保证队首对应的元素始终是滑动窗口最大值
特殊情况：当前处理的数据下标与最大值对应下标之差>=滑动窗口大小，这个数字已经不属于滑动窗口，直接删除这个最大值！这也导致了，队列中存放的不能是数组中的数据，而是数据对应的下标

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> vResult;//存储滑动窗口最大值if(nums.size()>=k && k>=1){deque<int>  dq_index;//存储滑动窗口值的下标for(int i=0;i<k;++i){//循环删除尾部比新插入小的元素while(!dq_index.empty() && nums[i]>nums[dq_index.back()])dq_index.pop_back();dq_index.push_back(i);    }vResult.push_back(nums[dq_index.front()]);for(int i=k;i<nums.size();++i){//循环删除尾部比新插入小的元素while(!dq_index.empty() && nums[i]>nums[dq_index.back()])dq_index.pop_back();dq_index.push_back(i);    //当前处理的数据下标与最大值对应下标之差>=滑动窗口大小，删除！if(!dq_index.empty() &&(i-dq_index.front())>=k){dq_index.pop_front();}    vResult.push_back(nums[dq_index.front()]);}}return vResult;}
};

剑指 Offer 30. 包含min函数的栈

【题目链接】
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路：
数据栈+辅助栈思想：数据栈负责存储元素，辅助栈存储当前栈中的最小元素值

class MinStack {
public:stack<int> s_data;stack<int> s_min;MinStack() {}void push(int x) {s_data.push(x);if(s_min.empty()||x<s_min.top())//如果min栈为空或者入栈的值小于min栈顶元素，{s_min.push(x);}else//入栈元素大于栈顶元素，最小值还是之前的元素{s_min.push(s_min.top());}}void pop() {if(s_data.empty() || s_min.empty())return;s_data.pop();s_min.pop();}int top() {assert(s_min.size()>0);return s_data.top();}int min() {assert(s_min.size()>0&& s_data.size()>0);return s_min.top();}
};

优化
可以发现辅助栈s_min每次都会push进一个元素，考虑进行小优化一下，当新插入的元素值大于当前min栈顶元素时不重复插入，只有当元素比栈顶小的时候在插入

class MinStack {
public:stack<int> s_data;stack<int> s_min;MinStack() {}void push(int x) {s_data.push(x);if(s_min.empty()||x<=s_min.top())//只需要插入新来的最小元素或相等元素{s_min.push(x);}}void pop() {if(s_data.empty() || s_min.empty())return;//分两种情况讨论删除    if(s_data.top()==s_min.top())s_min.pop();s_data.pop(); }int top() {assert(s_min.size()>0);return s_data.top();}int min() {assert(s_min.size()>0 && s_data.size()>0);return s_min.top();}
};

剑指 Offer 59 - II. 队列的最大值（max函数的队列）

【题目链接】
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：

输入: [“MaxQueue”,“pop_front”,“max_value”] [[],[],[]]
输出: [null,-1,-1]

解题思路：
借助辅助队列，从队列尾部插入元素时，删除队列中所有比这个元素小的元素，使得队列中只保留对结果有影响的数字

class MaxQueue {
public:MaxQueue() {}int max_value() {return dq.empty() ?-1:dq.front();}void push_back(int value) {//尾删比插入元素小的元素：对结果无影响while(!dq.empty() &&dq.back()<value){dq.pop_back();}dq.push_back(value);q.push(value);}int pop_front() {//删除数据并维护最大值队列if(q.empty()) return -1;int result=q.front();if(q.front()==dq.front()){dq.pop_front();}q.pop();return result;}
private:deque<int> dq;//存储每个阶段的最大值queue<int>  q;//存储所有数据       
};