leetcode学习——栈和对列

leetcode学习——栈和对列"/>

leetcode学习——栈和对列

目录

栈与队列理论基础

 题目列表

232.用栈实现队列

225. 用队列实现栈

20. 有效的括号

1047. 删除字符串中的所有相邻重复项

150. 逆波兰表达式求值【后缀表达式】

239. 滑动窗口最大值【单调对列】

347.前 K 个高频元素【优先级对列】

栈与队列总结

---

开始在leetcode上刷栈和对列相关题目了，同时整理一些栈和对列的相关知识点。主要跟着代码随想录学习，大家也可以参考该博主的内容【附各种语言的代码，解释也很详细】。对于我而言，相当于秉持着【学有留痕】的原则做一个学习上的记录，方面自己以后回顾相关知识点。祝看到文章的小伙伴们都学有所成！

对不同类型的堆和栈的具体使用，尤其是性质和函数还在继续，后面会继续补充该部分的内容。

栈与队列理论基础

特点：队列是先进先出，栈是先进后出。

如图所示：

那么这里再列出四个关于栈的问题，大家可以思考一下。以下是以C++为例，使用其他编程语言的同学也对应思考一下，自己使用的编程语言里栈和队列是什么样的。

1. C++中stack 是容器么？【不是，是容器适配器】
2. 我们使用的stack是属于哪个版本的STL（c++标准库）？【一共有三个版本】
3. 我们使用的STL中stack是如何实现的？【以SGI版本为例，默认是通过deque实现的，也可以指定其它类型的数据结构实现】
4. stack 提供迭代器来遍历stack空间么？【不提供】

首先需要知道 栈和队列是STL（C++标准库）里面的两个数据结构。

C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。

那么来介绍一下，三个最为普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。

2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。

3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

这一块还不是很了解。

接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

来说一说栈，栈先进后出，如图所示：

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

我们也可以指定vector为栈的底层实现，初始化语句如下：

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

刚刚讲过栈的特性，对应的队列的情况是一样的。

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

注意：这里讲的都是C++ 语言中的情况。

后面再整理补充c++中栈和对列的基本函数和语法的使用。

 题目列表

232.用栈实现队列

题目链接：232. 用栈实现队列

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

---

解题思路：使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

下面动画模拟以下队列的执行过程：

执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

这道题目我写的代码没有添加注释，所以这里就直接使用原博主的代码啦~

class MyQueue {
public:stack<int> stIn;stack<int> stOut;/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）if (stOut.empty()) {// 从stIn导入数据直到stIn为空while(!stIn.empty()) {stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();stOut.pop();return result;}/** Get the front element. */int peek() {int res = this->pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去return res;}/** Returns whether the queue is empty. */bool empty() {return stIn.empty() && stOut.empty();}
};

• 时间复杂度: push和empty为O(1), pop和peek为O(n)
• 空间复杂度: O(n)

拓展【针对代码复用问题】

可以看出peek()的实现，直接复用了pop()， 要不然，对stOut判空的逻辑又要重写一遍。

再多说一些代码开发上的习惯问题，在工业级别代码开发中，最忌讳的就是 实现一个类似的函数，直接把代码粘过来改一改就完事了。

这样的项目代码会越来越乱，一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！（踩过坑的人自然懂）

工作中如果发现某一个功能自己要经常用，同事们可能也会用到，自己就花点时间把这个功能抽象成一个好用的函数或者工具类，不仅自己方便，也方便了同事们。

225. 用队列实现栈

题目链接：225. 用队列实现栈

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

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

---

解题思路：（这里要强调是单向队列）

队列模拟栈，其实一个队列就够了。队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。

但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！

如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

模拟的队列执行语句如下：

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作       
queue.push(3);        
queue.push(4);       
queue.pop();  // 注意弹出的操作    
queue.pop();    
queue.pop();    
queue.empty();    

代码 【直接用的原博主的代码】

class MyStack {
public:queue<int> que1;queue<int> que2; // 辅助队列，用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que1.size();size--;while (size--) { // 将que1 导入que2，但要留下最后一个元素que2.push(que1.front());que1.pop();}int result = que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 = que2;            // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};

• 时间复杂度: pop为O(n)，其他为O(1)
• 空间复杂度: O(n)

优化

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

C++优化代码

class MyStack {
public:queue<int> que;/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que.size();size--;while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部que.push(que.front());que.pop();}int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了que.pop();return result;}/** Get the top element. */int top() {return que.back();}/** Returns whether the stack is empty. */bool empty() {return que.empty();}
};

• 时间复杂度: pop为O(n)，其他为O(1)
• 空间复杂度: O(n)

20. 有效的括号

题目链接：20. 有效的括号

题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：输入：s = "()" 输出：true

示例 2：输入：s = "()[]{}" 输出：true

示例 3：输入：s = "(]" 输出：false

---

解题思路：由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

建议在写代码之前要分析好有哪几种不匹配的情况，如果不在动手之前分析好，写出的代码也会有很多问题。

先来分析一下 这里有三种不匹配的情况：

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

2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。

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

代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出动手之前分析好题目的重要性。

动画如下：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

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

分析完之后，代码其实就比较好写了，

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！【如果不这样的话，还需要去找括号的随影关系，就比较麻烦】

代码

class Solution {
public:bool isValid(string s) {// 处理长度是奇数的情况if (s.size() % 2 != 0) return false;stack<char> st;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('}');// 当当前元素是右括号，就判断当前元素和栈顶元素是否相等，不相等就返回false//此外，还需要判断栈是否为空，如果为空，说明右括号是多余的，也要返回false// 如果当前元素和栈顶元素相等，说明括号匹配，则弹出栈顶元素else if (st.empty() || st.top() != s[i]) return false;else st.pop();}// 如果栈不为空，说明左括号多余，返回false,否则返回truereturn st.empty();}
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

1047. 删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项

题目描述：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

---

解题思路：本题是用栈来解决的经典题目。

可以依次遍历元素，用栈来存放遍历之后的元素。当遍历当前的这个元素的时候，看一下和现在的栈顶元素是否相等，相等则不用继续存入栈中且将栈顶元素弹出，不相等则加入到栈中。

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

代码

class Solution {
public:string removeDuplicates(string s) {stack<char> st;for (int i = 0; i < s.size(); i++) {// 如果栈为空，当字符加入到栈中if (st.empty()) st.push(s[i]);// 如果栈不为空，需要判断当前字符和栈顶元素是否相等// 不相等则直接加入到栈中// 相等则弹出栈顶元素else if (st.top() == s[i]) st.pop();else st.push(s[i]);}// 按顺序存储栈中元素，因为栈的先进后出的性质，所以有翻转字符串操作string s1 = "";while (!st.empty()) {s1 += st.top();st.pop();}reverse(s1.begin(),s1.end());return s1;}
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

优化

可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)，返回值不计空间复杂度

扩展

这道题目就像是我们玩过的游戏对对碰，如果相同的元素挨在一起就要消除。

游戏的后端逻辑就可以用一个栈来实现（我没有实际考察对对碰或者爱消除游戏的代码实现，仅从原理上进行推断）。

游戏开发可能使用栈结构，编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，但不是每种编程语言都支持递归，例如：

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

相信大家应该遇到过一种错误就是栈溢出，系统输出的异常是Segmentation fault（当然不是所有的Segmentation fault 都是栈溢出导致的） ，如果你使用了递归，就要想一想是不是无限递归了，那么系统调用栈就会溢出。

而且在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）

150. 逆波兰表达式求值【后缀表达式】

题目链接：150. 逆波兰表达式求值

题目描述：给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

---

背景知识：

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。【后缀表达式对于计算机而言非常友好】

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

解题思路：其实逆波兰表达式相当于是二叉树中的后序遍历。 可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。

但没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后序遍历的方式把二叉树序列化了，就可以了。

在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程。

如动画所示：

代码

class Solution {
public:int evalRPN(vector<string>& tokens) {// 定义栈存储数据以及数据计算的结果stack<long long> st;for (int i = 0; i < tokens.size(); i++) {if ( tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {// 如果遍历的是操作符，则取出两个数字并计算结果将结果存入到栈中long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();// 根据不同的操作符进行对应的操作if (tokens[i] == "+") st.push(num2 + num1);else if (tokens[i] == "-") st.push(num2 - num1);else if (tokens[i] == "*") st.push(num2 * num1);else if (tokens[i] == "/") st.push(num2 / num1);}// 如果遍历的字符是数字，则直接存入到栈中即可else{// tokens数组是字符串类型，栈里面存储的数据是long long型// 所以需要调用类型转换函数进行转换 stoll(string to longlong)st.push(stoll(tokens[i]));}}// 最后的栈顶元素就是计算的最终结果return st.top();}
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

239. 滑动窗口最大值【单调对列】

题目链接：239. 滑动窗口最大值

题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

示例 1：

输入：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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

---

解题思路：这是使用单调队列的经典题目。

难点是如何求一个区间里的最大值呢？

暴力方法，遍历一遍的过程中每次从窗口中再找到最大的数值，这样很明显是O(n × k)的算法。

有的可能会想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了， 但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。

此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

这个队列应该长这个样子：

class MyQueue {
public:void pop(int value) {}void push(int value) {}int front() {return que.front();}
};

每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。

我们需要自己实现这么个队列。

然后再分析一下，队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。

但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。

那么问题来了，已经排序之后的队列 怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢。

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列

不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。

来看一下单调队列如何维护队列里的元素。

动画如下：

对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。

此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢？

设计单调队列的时候，pop，和push操作要保持如下规则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

为了更直观的感受到单调队列的工作过程，以题目示例为例，输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：

那么我们用什么数据结构来实现这个单调队列呢？

使用deque最为合适，常用的queue在没有指定容器的情况下，deque就是默认底层容器。

基于刚刚说过的单调队列pop和push的规则，代码不难实现，如下：

class Myque {public:deque<int> que;// 删除滑动窗口最左端元素void pop(int value) {// 只有当对列非空且要删除的值等于对列的队首值即目前的最大值是才需要删除// 因为如果不是这样的话，说明需要删除的那个元素就没有在对列里面【这个是根据右面插入的操作决定的】if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {// 插入元素需要保持对列从大到小单调递减// 所以需要将插入的元素和前面已有的元素进行比较// 需要将前面所有比插入的元素小的值都弹出对列while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 返回对列的队首元素，即当前滑动窗口的最大值int front() {return que.front();}};

这样我们就用deque实现了一个单调队列。接下来就是不断滑动窗口记录最大值啦！

代码

class Solution {
public:class Myque {public:deque<int> que;// 删除滑动窗口最左端元素void pop(int value) {// 只有当对列非空且要删除的值等于对列的队首值即目前的最大值是才需要删除// 因为如果不是这样的话，说明需要删除的那个元素就没有在对列里面【这个是根据右面插入的操作决定的】if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {// 插入元素需要保持对列从大到小单调递减// 所以需要将插入的元素和前面已有的元素进行比较// 需要将前面所有比插入的元素小的值都弹出对列while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 返回对列的队首元素，即当前滑动窗口的最大值int front() {return que.front();}};vector<int> maxSlidingWindow(vector<int>& nums, int k) {Myque que;// 依次存储滑动窗口最大值的数组vector<int> result;// 先将前k个元素加入对列【不会存储所有的元素哦，里面的元素时单调递减的】for (int i = 0; i < k; i++) {que.push(nums[i]);}int j = 0;// 存储第一个滑动窗口的最大值result.push_back(que.front());// 开始往后面滑动窗口for (int i = k; i < nums.size(); i++) {// 窗口开始从左向右滑动，依次删除最左边的元素并在右边添加一个元素// 当然只有即将被删除的元素为当前最大值时才会被删除// 而添加的元素要保证前面没有元素比它小，否则将前面比它小的元素先弹出再添加元素que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}return result;}
};

• 时间复杂度: O(n)
• 空间复杂度: O(k)

拓展：

要明确的是，题解中单调队列里的pop和push接口，仅适用于本题哈。单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。 不要以为本题中的单调队列实现就是固定的写法哈。

此外，C++中deque是stack和queue默认的底层实现容器，deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。

347.前 K 个高频元素【优先级对列】

题目链接：347. 前 K 个高频元素

题目描述：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:  输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

示例 2:  输入: nums = [1], k = 1 输出: [1]

---

解题思路：这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢， 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

此时要思考一下，是使用小顶堆呢，还是大顶堆？

有的同学一想，题目要求前 K 个高频元素，那么果断用大顶堆啊。

那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

寻找前k个最大元素流程如图所示：（图中的频率只有三个，所以正好构成一个大小为3的小顶堆，如果频率更多一些，则用这个小顶堆进行扫描）

代码

class Solution {
public:class mycomparision {public:// 设计排序规则bool operator()(const pair<int, int>&l, const pair<int, int>& r) {// 从大到小排序return l.second > r.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 统计不同元素出现频率// first为元素，second为该元素出现的次数unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 其实后面的操作就是对元素出现的次数进行排序，然后选择前k个次数大的输出// 因为只需要前k个，所以选择堆排序，为了操作方便，选择小顶堆// 首先定义一个小顶堆大小为k priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparision> pri_que; //这里的定义后面需要研究学习一下// 然后用固定大小为k的小顶堆， 扫描所有频率的元素for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);// 如果堆的大小大于K,则对列弹出，保证堆的大小一直为kif (pri_que.size() > k) {pri_que.pop();}}// 最后找出前k个高频元素，因为小顶堆先弹出的是最小的，所以倒叙输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};

栈与队列总结

栈与队列的理论基础

首先讲解了栈和队列的理论基础。

里面提到了灵魂四问：

1. C++中stack，queue 是容器么？
2. 我们使用的stack，queue是属于那个版本的STL？
3. 我们使用的STL中stack，queue是如何实现的？
4. stack，queue 提供迭代器来遍历空间么？

思考栈和队列是如何实现的。

可以出一道面试题：栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

• 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
• 陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

栈经典题目

栈在系统中的应用

如果还记得编译原理的话，编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑，就是使用了栈这种数据结构。

再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不过了。

cd a/b/c/../../

这个命令最后进入a目录，系统是如何知道进入了a目录呢 ，这就是栈的应用。这在leetcode上也是一道题目，71. 简化路径，有空可以做一下。

递归的实现是栈：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

所以栈在计算机领域中应用是非常广泛的。

有的同学经常会想学的这些数据结构有什么用，也开发不了什么软件，大多数同学说的软件应该都是可视化的软件例如APP、网站之类的，那都是非常上层的应用了，底层很多功能的实现都是基础的数据结构和算法。

所以数据结构与算法的应用往往隐藏在我们看不到的地方！

括号匹配问题

在【20. 有效的括号】中讲解了括号匹配问题。括号匹配是使用栈解决的经典问题。

建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。

先来分析一下 这里有三种不匹配的情况，

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。
3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

这里还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

字符串去重问题

【1047. 删除字符串中的所有相邻重复项】

思路就是可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。

逆波兰表达式问题

【150. 逆波兰表达式求值【后缀表达式】】

本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和中的对对碰游戏是不是就非常像了。

队列的经典题目

滑动窗口最大值问题

【239. 滑动窗口最大值【单调对列】】

这道题目还是比较绕的，如果第一次遇到这种题目，需要反复琢磨琢磨

主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来一个单调队列

而且不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。

设计单调队列的时候，pop，和push操作要保持如下规则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列出口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

一些同学还会对单调队列都有一些困惑，首先要明确的是，题解中单调队列里的pop和push接口，仅适用于本题。

单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。

不要以为本地中的单调队列实现就是固定的写法。

用deque作为单调队列的底层数据结构，C++中deque是stack和queue默认的底层实现容器，deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。

求前 K 个高频元素

在347.前 K 个高频元素【优先级对列】中讲解了求前 K 个高频元素。通过求前 K 个高频元素，引出另一种队列就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题就要使用优先级队列来对部分频率进行排序。 注意这里是对部分数据进行排序而不需要对所有数据排序！

所以排序的过程的时间复杂度是，整个算法的时间复杂度是。

总结

使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。

我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。