2.3 栈和队列
后进先出、先进先出
Last updated
后进先出、先进先出
Last updated
数据结构里的“栈/堆”和内存里的“堆栈”是完全不一样的，数据结构里的一般是指栈和二叉堆。
栈的特点是后进先出，它只允许在栈顶插入一个元素、在栈顶删除一个元素。如下图所示：
First in - Last out，先进后出 Last in - First out，后进先出
队列的特点是先进先出，它只允许在队尾插入一个元素、在队头删除一个元素。如下图所示：
First in - First out，先进先出 Last in - Last out，后进后出
严格来说，栈和队列更像是个“容器”。它们都是线性存储的，且只在头和尾进行操作，所以底层实现要么是数组，要么是链表。
用数组实现的栈/队列，叫顺序栈/队列 用链表实现的栈/队列，叫链式栈/队列
虽然从定义上看，栈和队列都是一种操作受限的线性“容器”，但因为它们的实用性，大部分语言都提供了栈和队列的数据类型或者库，以便我们直接使用。所以，一般情况下我们都会说栈和队列是一种非常基础的“数据结构”。
普通队列是一端进另一端出，而双端队列是头和尾都是可进可出的。如下图所示：
双端队列也可以用数组或者链表来实现。如果是用数组实现的，通常会选择循环数组，因为这样可以更好地利用存储空间。
普通队列是以“时间”为顺序的（先进先出），而优先队列是按照元素的“优先级”取出的，比如它保证出队的元素总是优先级最高的。“优先级”可以是自己定义的一个元素属性，一般是个整数。
优先队列是个容器/接口/方法，它可以用很多种数据结构来实现，比如二叉堆/二叉平衡树（它们都能动态维护一个集合里的最大值/最小值）。
栈, 队列
Push O(1) Pop O(1) Access O(1)
入栈/入队 出栈/出队 访问栈顶/队头
双端队列
插入 O(1) 删除 O(1) 访问 O(1)
队头和队尾
优先队列
访问最值 O(1)
插入 O(logN)
一些高级数据结构可以做到 O(1), eg.配对堆/斐波那契堆
取最值 O(logN)
取完了还需动态调整下剩余的
stack，栈
queue，队列
deque，双端队列
priority queue，优先队列
栈可以解决“最近相关性”的问题。最近相关性就蕴含着此序列只在一个口操作（后进先出），比如：
有效括号：一个序列（一维容器），且匹配的操作只在结尾处发生（一端操作），逻辑是右括号和离它最近的左括号相匹配（最近相关性）
函数调用：核心是维护一个作用域（最近相关性）
后缀表达式求值：遇到操作符（总在尾部），就用最近的两个结果来做运算（最近相关性）
三种表达式的基本定义，如下：
前缀表达式（波兰式），形如op A B，eg.* 3 + 1 2
类似写程序-调函数 ie.op(A, B)
eg.mult(3, plus(1,2))
后缀表达式（逆波兰式），形如A B op，eg.3 1 2 + *
中缀表达式：形如A op B，eg.3 * (1 + 2)
“前/中/后”指的是操作符的位置。前缀和后缀表达式写出来之后，操作顺序是固定的，所以不需要括号。
队列这种数据结构很适合用来存储排队请求，比如线程池/数据库连接池/请求池/分布式消息池。
阻塞队列是在队列的基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据的操作会被阻塞（因为此时没数据可取），直到队列中有了数据之后才能返回；在队列满了的时候，从队尾插入数据的操作会被阻塞，直到队列中有了空闲位置之后才能插入数据然后再返回。
当条件不满足时，非阻塞的处理方式是直接拒绝任务请求 而阻塞的处理方式是先将请求排队，然后等条件满足了再处理并返回
我们可以用阻塞队列轻松地实现“生产者-消费者模型”，进而有效地协调生产和消费的速度。
此外还有并发队列、循环队列，它们在很多偏底层的系统/框架/中间件中起着关键性的作用。比如高性能队列 Disruptor 和 Linux 环形缓存都用到了循环并发队列、Java concurrent 并发包利用了 ArrayBlockingQueue 来实现公平锁等。
线程安全的队列叫并发队列
队列大小的设置也很关键。队列太大容易导致等待的请求过多，队列太小容易导致没法充分利用系统的资源。
严格来说，单调栈和单调队列其实不是一种数据结构，而是一种对程序和算法的优化。即利用单调性排除一些不可能的冗余选项，只不过是借用了栈和队列这两个容器而已。
单调栈的思想是先考虑“前面不能影响到后面”的条件（是递增还是递减），然后就可以单独计算前面的了。思路就是一个一个遍历，然后把数据修剪成单调栈，符合单调性的直接进栈，不符合的就先修剪成符合的然后再进栈（此时会更新一次答案）。比如 84. 柱状图中最大的矩形（H）。
单调队列的思想是利用队列来维护一个候选集合。过程是利用单调性来尽快地排除掉在这个集合里永远不可能成为答案的一些选项，只保留那些在某些时刻可能成为答案的选项，进而简化候选集合。比如 239. 滑动窗口最大值（H）。
这部分重点介绍了栈和队列的基本原理及其时间复杂度，同时介绍了栈和队列的基本应用。
基本原理
栈：后进先出，O(1) 入栈/出栈/访问栈顶
队列：先进先出，O(1) 入队/出队/访问队头
双端队列：两头都可进可出，O(1) 插入/删除/访问
优先队列：出队的总是优先级之最
基本应用
栈：最近相关性问题
队列：排队请求问题
单调栈和单调队列：是对程序和算法的一种优化
栈和队列作为两个基本容器，在很多算法里都会用到 (eg. DFS, BFS)，所以一定要把它们的原理掌握好。
此外，栈和队列的原理又相对比较简单，所以重点还是在于使用。首先熟悉下自己使用的编程语言里自带的与栈和队列相关的数据类型和接口，以便在实战中灵活运用。再就是多练习，感受下这两种数据结构的解题思路。
