堆栈 stacktype
status
date
slug
summary
tags
category
icon
password
Property
堆栈Stack
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入的删除和操作的一端，称为栈顶 。另一端则称为栈底 。栈中的元素遵守后进先出的原则，即LIFO原则（Last In First Out）。
压栈：栈的插入操作叫做 进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
进栈出栈的形式
栈对线性表的插入和删除的位置做了限制，并没有对元素进出的时间进行限制，所以，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。所以栈是：一种入栈顺序，多种出栈顺序。
比如，元素1、2、3依次进栈，出栈顺序：
- 第一种：1、2、3（1进、1出、2进、2出、3进、3出）
- 第二种：3、2、1（1、2、3进，3、2、1出）
- 第三种：2、1、3（1、2进，2、1出，3进、3出）
- 第四种：1、3、2（1进、1出，2、3进，3、2出）
- 第五种：2、3、1（1、2进，2出，3进，3出，1出）
栈的存储结构
- 栈的顺序存储结构「顺序栈」
数组的首元素作为栈底，另外一端作为栈顶，同时定义一个变量
top来记录栈顶元素在数组中的位置。使用数组模拟栈
- 栈的链式存储结构「链式栈」
单链表的尾部作为栈底，头部作为栈顶，方便插入和删除（进栈头插，出栈头删），头指针和栈顶指针
top合二为一C++ STL 中的栈
适配器模式是一种设计模式，用于将一个类的接口转换成客户所期望的另一种接口。
stack和queue虽然可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，因为stack和queue只是对其它容器的接口进行了包装。stack和queue默认使用的是deque函数说明 | 接口说明 |
stack() | 构造空的栈 |
empty() | 检测 stack 是否为空 |
size() | 返回 stack 中元素的个数 |
top() | 返回栈顶元素的引用 |
push() | 将元素 val 压入 stack 中 |
pop() | 将 stack 中尾部的元素弹出 |
得益于容器适配器的使用，接口相较于
vector和list少了很多，也没有迭代器用队列实现栈
单调栈Monotone Stack
单调栈（Monotone Stack）：一种特殊的栈。在栈的先进后出规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。
注意：这里定义的顺序是从「栈顶」到「栈底」。
单调递增栈
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。
单调递增栈的入栈、出栈过程如下：
- 假设当前进栈元素为
x，如果x比栈顶元素小，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把小于
x或者等于x的元素弹出栈，直到遇到一个大于x的元素为止，然后再把x压入栈中。
以数组
[2, 7, 5, 4, 6, 3, 4, 2] 为例，模拟一下「单调递增栈」的进栈、出栈过程。具体过程如下：数组元素：
[2, 7, 5, 4, 6, 3, 4, 2]，遍历顺序为从左到右。第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作 用 |
1 | 2 | 2 入栈 | [2] | 元素 2 的左侧无比 2 大的元素 |
2 | 7 | 2 出栈，7 入栈 | [7] | 元素 7 的左侧无比 7 大的元素 |
3 | 5 | 5 入栈 | [7, 5] | 元素 5 的左侧第一个比 5 大的元素为：7 |
4 | 4 | 4 入栈 | [7, 5, 4] | 元素 4 的左侧第一个比 4 大的元素为：5 |
5 | 6 | 4 出栈，5 出栈，6 入栈 | [7, 6] | 元素 6 的左侧第一个比 6 大的元素为：7 |
6 | 3 | 3 入栈 | [7, 6, 3] | 元素 3 的左侧第一个比 3 大的元素为：6 |
7 | 4 | 3 出栈，4 入栈 | [7, 6, 4] | 元素 4 的左侧第一个比 4 大的元素为：6 |
8 | 2 | 2 入栈 | [7, 6, 4, 2] | 元素 2 的左侧第一个比 2 大的元素为：4 |
最终栈中元素为
[7, 6, 4, 2]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 2, 4, 6, 7，满足递增关系，所以这是一个单调递增栈。以上述过程第 5 步为例，所对应的图示过程为：
单调递减栈
单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的。
单调递减栈的入栈、出栈过程如下：
- 假设当前进栈元素为
x，如果x比栈顶元素大，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把大于
x或者等于x的元素弹出栈，直到遇到一个小于x的元素为止，然后再把x压入栈中。
以数组
[4, 3, 2, 5, 7, 4, 6, 8] 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：数组元素：
[4, 3, 2, 5, 7, 4, 6, 8]，遍历顺序为从左到右。第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作用 |
1 | 4 | 4 入栈 | [4] | 元素 4 的左侧无比 4 小的元素 |
2 | 3 | 4 出栈，3 入栈 | [3] | 元素 3 的左侧无比 3 小的元素 |
3 | 2 | 3 出栈，2 入栈 | [2] | 元素 2 的左侧无比 2 小的元素 |
4 | 5 | 5 入栈 | [2, 5] | 元素 5 的左侧第一个比 5 小的元素是：2 |
5 | 7 | 7 入栈 | [2, 5, 7] | 元素 7 的左侧第一个比 7 小的元素是：5 |
6 | 4 | 7 出栈，5 出栈，4 入栈 | [2, 4] | 元素 4 的左侧第一个比 4 小的元素是：2 |
7 | 6 | 6 入栈 | [2, 4, 6] | 元素 6 的左侧第一个比 6 小的元素是：4 |
8 | 8 | 8 入栈 | [2, 4, 6, 8] | 元素 8 的左侧第一个比 8 小的元素是：6 |
最终栈中元素为
[2, 4, 6, 8]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 8, 6, 4, 2，满足递减关系，所以这是一个单调递减栈。以上述过程第 6 步为例，所对应的图示过程为：
单调栈适用场景
单调栈可以在时间复杂度为的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。所以单调栈一般用于解决一下几种问题：
- 寻找左侧第一个比当前元素大的元素
- 一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。
- 如果插入时的栈为空，则说明左侧不存在比当前元素大的元素。
从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 寻找左侧第一个比当前元素小的元素
- 一个元素左侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。
- 如果插入时的栈为空，则说明左侧不存在比当前元素小的元素。
从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 寻找右侧第一个比当前元素大的元素
- 从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 一个元素右侧第一个比它大的元素就是将其「弹出单调递增栈」时即将插入的元素。
- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素大的元素。
- 从右到左遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 一个元素右侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。
- 如果插入时的栈为空，则说明右侧不存在比当前元素大的元素。
- 寻找右侧第一个比当前元素小的元素
- 从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。
- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素小的元素。
- 从右到左遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。
- 如果插入时的栈为空，则说明右侧不存在比当前元素小的元素。