数据结构中队列有很多，例如：先进先出队列、双端队列、单调队列、优先队列（堆） 等等。我来简单介绍一下吧。

「 数据结构 」 和 「 算法 」 是密不可分的，两者往往是「 相辅相成 」的存在，所以，在学习 「 数据结构 」 的过程中，不免会遇到各种「 算法 」。
数据结构 常用的操作一般为：「 增 」「 删 」「 改 」「 查 」。基本上所有的数据结构都是围绕这几个操作进行展开的。那么这篇文章，作者将用 「 十张动图 」 来阐述一种 「 一端插入 」「 两端删除 」 的数据结构「 单调队列 」 。

单调队列的操作浓缩为以下一张图：

看不懂没有关系，我会把它拆开来一个一个讲。

【例题1】给定一个长度为 整数数组 ，有一个大小为 的滑动窗口从数组的最左侧移动到数组的最右侧。只能看到在滑动窗口内的 个数字。滑动窗口每次只向右移动一位。返回 每个滑动窗口 的最大值。

看到这个问题，最简单的思路就是：枚举一个起点 ，然后记录区间 内的最大值。枚举起点的时间复杂度为 ，记录区间最值的时间复杂度为 ，所以总的时间复杂度为 ，对于这个问题的数据量，最大的数据量达到了 量级，所以这个做法是行不通的。

这个问题是个经典的区间最值问题，可以通过 ST表 (Sparse Table, 稀疏表) 求解，时间复杂度为 ，除了 ST表，还可以采用 线段树 求解区间最值，时间复杂度也为 。当然，这两块内容都不是本文讨论的重点，如果对 ST表 感兴趣，可以参考以下文章：。对线段树感兴趣，可以参考以下文章：。

本文将介绍一种 的算法。它将会用到一种数据结构 —— 单调队列。在这个问题中，两个相邻的滑动窗口，实际上只相差两个元素，如下图所示：

假设，我们提供了一种容器，这个容器能够支持三种操作：
1）【询问】通过 的时间，获取容器中元素的最大值。
2）【删除】通过 的时间，删除元素；
3）【插入】通过 的时间，插入元素；

那么，我们只要不断的移动滑动窗口，每一次移动，删除一个元素，插入另一个元素，并且记录下最大值，那么，每一次滑动，只需要三步 的操作。总共 次滑动，只需要 的时间复杂度就能解决这个问题。 这种容器存在吗？让我们首先简单了解一下 FIFO 队列 和 双端队列，如果你对 以上两种数据结构 已经 了如指掌，则可以跳过相关内容，直接观看

队列 是仅限在 一端 进行 插入，另一端 进行 删除 的 线性表。

允许进行元素删除的一端称为 队首。如下图所示：

允许进行元素插入的一端称为 队尾。如下图所示：

队列的插入操作，叫做 入队。它是将 数据元素 从 队尾 进行插入的过程，如图所示，表示的是 插入 两个数据（绿色 和 蓝色）的过程：

队列的删除操作，叫做 出队。它是将 队首 元素进行删除的过程，如图所示，表示的是 依次 删除 两个数据（红色 和 橙色）的过程：

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 重合时，就代表队尾为空了，如图所示：

对于一个队列来说只能获取 队首 数据，一般不支持获取 其它数据。

队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 的时间复杂度获取队列元素个数。

当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作。

队列的实现，可以参考以下这篇文章：

双端队列 是一种具有 队列 和 栈 的性质的数据结构，是我们常说的 deque（double-ended queue），是一种限定 插入 和 删除 操作在表的两端进行的线性表。这两端分别被称为 队首 和 队尾。

双端队列的一端被称为 队首，如下图所示：

双端队列的另一端被称为 队尾，如下图所示：

队列的插入操作，叫做 入队。

队首入队 就是将 数据元素 从 队首 进行插入的过程。如图所示，表示的是在队首 插入 一个蓝色数据的过程：

队尾入队 就是将 数据元素 从 队尾 进行插入的过程。如图所示，表示的是在队尾 插入 一个紫色数据的过程：

队列的删除操作，叫做 出队。队首出队 是将 队首 元素进行删除的过程，如图所示，表示的是在队首 删除 一个蓝色数据的过程：

队尾出队 是将 队尾 元素进行删除的过程，如图所示，表示的是在队尾 删除 一个紫色数据的过程：

队列的清空操作，就是一直 出队，直到队列为空的过程，当 队首 和 队尾 正好错开一个位置时，就代表队尾为空了，如图所示，细心的读者会发现，队尾 和 队首 错开了一个位置：

队列元素个数一般用一个额外变量存储，入队 时加一，出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 的时间复杂度获取队列元素个数。

当队列元素个数为零时，就是一个 空队，空队 不允许 出队 操作。

队首指针 指向的数据被称为 队首元素，可以通过 的时间复杂度来获取。

队尾指针 指向的数据被称为 队尾元素，可以通过 的时间复杂度来获取。

需要了解双端队列的实现，可以参考如下文章：

单调队列 就是能够完美支持下面三种操作的一种容器：
1）【询问】通过 的时间，获取容器中元素的最大值。
2）【删除】通过 的时间，删除元素；
3）【插入】通过 的时间，插入元素；

单调队列是一个限制只能 队尾插入，但是可以 两端删除 的 双端队列 。单调队列 存储的元素值，是从 队首 到 队尾 呈单调性的（要么单调递增，要么单调递减）。

对于求解最大值的问题，则需要维护一个 单调递减 的队列。

如图所示，⑨ 为原先的 队首元素，执行 队首删除（出队） 操作以后，⑥ 成为新的 队首元素；而在队尾执行插入④这个元素的时候，为了保持单调性，需要将①②依次从队尾删除；当队尾执行插入②这个元素的时候，满足单调性。

由于单调队列是单调递减的，所以队首元素 最大，直接 获取队首元素。

如图所示，head 指向 队首元素，直接获取，由于这是一个单调递减队列，所以得到的，就是最大值。

删除分为 队首删除 和 队尾删除。 队首删除即直接队首元素出队， 即可完成操作。如图所示：

队尾删除 一般是配合 队尾插入 进行的。我们接着往下看。

在进行 队尾插入 的时候，我们往往需要明白一个重要的点，就是需要保证它 单调递减 的性质，所以如果 队尾元素 插入元素 ，则当前的 队尾元素 是需要执行删除操作的（也就是上文提到的 队尾删除），直到满足 队尾元素 插入元素，才能真正执行 插入 操作。

这样才能保证，执行 队尾插入 后，单调队列仍然是 单调递减 的。插入过程，虽然伴随着元素的删除，但是每个元素至多被 插入一次 和 删除一次，所以均摊时间复杂度还是 $O(1)$ 的。

如图所示，在队尾执行插入④这个元素的时候，为了保持单调性，需要将①②依次从队尾删除；当队尾执行插入②这个元素的时候，满足单调性，所以直接执行插入操作。

由于单调队列执行插入的时候，一定是从队尾进行插入，所以单调队列中的数据，从队首到队尾的顺序，一定是和原序列严格保序的；

为了让单调队列的数据足够干净，在单调队列中，一般存储 原序列的下标 即可，而不需要存储原序列的值，根据保序性，存储的下标一定是单调递增的；

单调队列中的元素是 原序列的下标，对应到原序列时，根据求解问题的不同，当需要求最大值时，它是单调递减的；当需要求最小值时，它是单调递增的；

继续回到上文提到的滑动窗口中的最大值问题。

【例题1】给定一个长度为 整数数组 ，有一个大小为 的滑动窗口从数组的最左侧移动到数组的最右侧。只能看到在滑动窗口内的 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

我们要实现的，就是把原序列 中的元素逐个执行单调队列的 插入 操作。当 插入 的原序列的下标为 $i$ 时，期望是单调队列中的元素从 队首 到 队尾 都在原序列的区间 为右端点，长度为 的区间内），且对应到原序列的值单调递减，这样每次插入完毕，就可以在 的时间内，从队首获取到最大值（即区间 内的最大值）。

为什么是单调递减？而不是单调递增？

对于每个需要插入的下标 ，队尾的元素为原序列的下标 ，则根据保序性，一定能够满足 ，如果对应到原序列中，满足 ，那么 不会比 更优，原因是：对于区间 来说， 一定在区间内，而 则未必，也就是说 下标 没必要存储到单调队列中。于是对于单调队列中的存储的元素 需要满足： ，即 维护一个单调递减的队列。

实际执行过程中，每次插入后，队尾元素 减去 队首元素 必须小于等于 ，一旦超过 ，就要从队首不断出队了。

【例题2】给定一个下标从 0 开始，元素个数为 的整数数组 和一个整数 。开始在下标 0 处。每一步，最多可以往前跳 步，但不能跳出数组的边界。也就是说，可以从下标 跳到 包含 两个端点的任意位置。
目标是到达数组最后一个位置（下标为 ），得分 为经过的所有数字之和，求得分的最大值。

比较容易想到的是动态规划，假设跳到位置 的最大值是 ， 那么一定是从 中的某个位置跳过来的，可以得到状态转移方程如下：

但是这一步的问题在于，数组长度为 时，每次状态转移的时间为 ，所以整個算法的时间复杂度为 。所以我们需要想办法将 这步操作化为 。
维护一个单调递减的队列，这样就能通过 的时间找到从队首找到最大值。单调队列始终保持 的元素在队列中是单调递减的。对于队列中的两个元素，下标位置为 , 如果 ，则 不能放入 单调队列中，因为它不会比 更优。并且时刻保证，当前元素插入单调队列之后，单调队列队列的

【例题3】返回数组 的最短的非空连续子数组的长度，该子数组的和至少为 。如果没有和至少为 的非空子数组，返回 。

前缀和预处理：令 代表 的前缀和，对于一段左开右闭子数组 ， 就是这段子数组的和，其中 ，并且必须满足子数组和 。
单调性的思考：对于两个下标 ， 如果 ，则 不会比 更优，所以，我们只需要维护一个 值单调递增的单调队列；
维护单调队列：单调队列的队首一定是 值最小的， ，则记录 作为一个候选解，并且弹出队首；
实际落地方案：然后只需要枚举 ，维护 的单调队列，且单调队列插入的是前缀和的下标值，候选最优值 用于和最终最优值进行比较取小者，不存在候选解则返回 。

关于 「 单调队列 」 的内容到这里就结束了。 更多队列相关的内容可以参考我知乎专栏 「 法 」中队列相关的文章。

一步都应确切地、无二义性地定义；(3)可行性：每条指令可以执行且有正确的结果。

10、评价一个算法的好坏主要依据：1正确性2、可读性3、健壮性4、高效率

11、算法效率的衡量方法有：事后统计法和事前分析估算法；事前估算法主要

考虑：（1）算法选用的策略、（2）、问题的规模。

12、算法时间复杂度是算法中基本运算重复执行次数多少的量度。记作O(n)，

空间复杂度作为实现算法所需的辅助存储空间的大小，记作S(n)=O(f(n))。

1、线性表是具有相同特性的数据元素的一个有限序列。其特征有三：所有元素

类型相同、线性表是由有限个数据元素组织、线性表中的数据元素与位置有关的，这一点表明线性表不同于集合，线性表中的每一个元素都有一个对应的序号，线性表中元素可以重复出现。

2、线性结构特点：有“头”元素有“尾”元素，中间的元素有“前驱”元素和

3、线性表的顺序表示是指：用一组地址连续的存储单元依次存放线性表中的数

4、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O

（1），在表尾插入元素的时间复杂度为O（n）。

5、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表

1、栈(Stack):是一种特殊的线性表（数据元素之间的关系是线性关系），其插入、删除只能在表的一端进行，另一端固定不动。

栈顶（top）：插入、删除的一端；

栈底（bottom）：固定不动的一端；

入栈（push）：又称压入，即插入一个元素；

出栈（pop）：又称弹出，即删除一个元素；

2）入栈Push(s)：即在栈顶插入一个元素；

3）出栈Pop(s)：即在栈顶删除一个元素；

4）取栈顶元素Get_top(s)：访问栈顶元素；

5）判断栈是否空Empty(s)：判断是否为空；

7）栈清空Clear(s)：将栈清为空；

5、存储方式：同一般线性表的顺序存储结构完全相同。但是栈底可以在地址低端，也可以在地址高端。

栈的顺序存储结构的特点：简单，方便，但易产生溢出。

上溢（overflow）：栈已经满，又要压入元素；

下溢（Underflow）：栈已经空，还要弹出元素；

注：上溢是一种错误，使问题的处理无法进行下去；而下溢一般认为是一种结束条件，即问题处理结束。

3）出栈//若栈不空，则删除S的栈顶元素，用e返回其值

//若栈不空，用e返回栈顶元素