代码随想录第七章 栈与队列

1、leecode232 用栈实现队列

使用栈模拟队列的行为，仅使用一个栈是不行的，所以需要两个栈，一个是输入栈，一个是输出栈。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class MyQueue {private:stack<int> stack_in;stack<int> stack_out;public:void push(int value) {stack_in.push(value);}int pop() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result = stack_out.top();stack_out.pop();return result;}int top() {if (stack_out.empty()) {while (!stack_in.empty()) {stack_out.push(stack_in.top());stack_in.pop();}}int result = stack_out.top();return result;}bool empty() {return stack_in.empty() && stack_out.empty();}
};void main() {MyQueue queue;queue.push(1);queue.push(2);queue.push(3);cout << "the first value: " << queue.pop() << endl;cout << "the next value: " << queue.pop() << endl;cout << "the next value: " << queue.pop() << endl;cout << "hello world" << endl;
}

2、用队列实现栈。 leetcode225

队列的规则是先进先出，把一个队列中的数据导入另一个队列，数据的顺序并没有变。所以用栈实现队列和用队列实现栈的思路是不一样的，取决于这两个数据结构的性质。如果用两个对列实现栈，那么两个队列就没有输入队列和输出队列的关系，另一个队列完全是用来备份的。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class MyStack {private:queue<int> queue_fir;queue<int> queue_sec;public:void push(int val) {queue_fir.push(val);}int pop() {int size = queue_fir.size();size--;while (size--) {queue_sec.push(queue_fir.front());queue_fir.pop();}int result = queue_fir.front();queue_fir.pop();queue_fir = queue_sec;while (!queue_sec.empty()) {queue_sec.pop();}return result;}int top() {return queue_fir.back();}bool empty() {return queue_fir.empty();}
};void main() {MyStack stack;stack.push(1);stack.push(2);stack.push(3);cout << stack.pop() << endl;cout << stack.pop() << endl;cout << stack.pop() << endl;cout << "hello world" << endl;
}

3、匹配括号 leetcode20

这里有三种不匹配的情况

（1）、第一种情况，字符串中左方向的括号多余了，所以不匹配。

第一种情况：已经遍历了字符串，但是栈不为空，说明有相应的左括号，但没有右括号，所以返回错误。

（2）、第二种情况，括号没有多余，但是括号的类型不匹配。

在遍历字符串的过程中，发现栈中没有要匹配的字符，返回错误。

（3）、第三种情况，字符串中右方向的括号多余了，所以不匹配。

在遍历字符串的过程中栈已经为空，没有匹配的字符了，说明右括号没有找到对应的左括号，返回错误。

那么什么时候说明左括号和右括号全部匹配了呢？如果遍历字符串之后，栈是空的，则说明全都匹配了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
using namespace std;class Solution {private:stack<int> st;public:bool IsValid(string& s) {for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {st.push(')');}else if (s[i] == '{') {st.push('}');}else if (s[i] == '[') {st.push(']');}else if (st.empty() || st.top() != s[i]) {return false;}else {st.pop();}}return st.empty();}
};void main() {string s = "(){}[]{[]}";Solution slo;slo.IsValid(s);cout << "hello world" << endl;
}

4、滑动窗口最大值 leetcode239

一个大小为k的滑动窗口，从前向后在数组nums上移动，返回滑动窗口每移动一次时窗口中的最大值。

（1）、设计单调对列，设计的时候，pop和push操作保持如下规则：

pop()：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不进行任何操作。

push()：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于或等于队列入口元素的数值。

基于以上规则，每次窗口移动的时候，只要调用que.front()就可以返回当前窗口的最大值。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;//单调队列，从大到小
class MyQueue {private:deque<int> que;//使用deque实现单调队列public://每次弹出元素时，比较当前要弹出元素的数值是否等于队列出口元素的数值，如果相等则弹出。//弹出元素之前，需要判断队列当前是否为空void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}//如果要push的数组大于入口元素的数值，那么就将队列入口元素弹出，知道push的数值小于或等于对列入口元素的数值。//这样就保持了队列中的数值是从大到小的单调递减了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}
};void main() {cout << "hello world" << endl;
}

这样就用deque实现了一个单调队列，接下来解决求滑动窗口最大值的问题就简单了。

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
using namespace std;class Slotuion {private://单调队列，从大到小class MyQueue {private:deque<int> que;//使用deque实现单调队列public://每次弹出元素时，比较当前要弹出元素的数值是否等于队列出口元素的数值，如果相等则弹出。//弹出元素之前，需要判断队列当前是否为空void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}//如果要push的数组大于入口元素的数值，那么就将队列入口元素弹出，知道push的数值小于或等于对列入口元素的数值。//这样就保持了队列中的数值是从大到小的单调递减了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {return que.front();}};private:MyQueue que;public:vector<int> MaxSlidingWindow(vector<int> &input,int k) {vector<int> result;for (int i = 0; i < k; i++) {que.push(input[i]);}result.push_back(que.front());for (int i = k; i < input.size(); i++) {que.push(input[i]);que.pop(input[i - k]);result.push_back(que.front());}return result;}
};void main() {vector<int> input = { 2,4,-2,-4,3,1,5 };int k = 4;Slotuion slo;slo.MaxSlidingWindow(input, k);cout << "hello world" << endl;
}