数据结构与算法之美 - 学习笔记
引出问题：浏览器如何实现前进后退功能
[图片上传失败...(image-56f9b3-1632473114756)]
栈
栈是一种‘操作受限’的线性表，具有后进者先出，先进者后出的特点。
区别于链表结构可两头操作，也区别于数组结构支持随机访问。栈这种数据结构，适用于数据集只支持在一端插入删除，且只满足先进后出、后进先出特性的数据操作
栈的实现
栈主要包含两个操作，入栈和出栈。可以用数组或者链表来实现栈，使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈
示例：实现顺序栈（JavaScript）
function Arraystack(n) {
var data = new Array(n); // 数组
var count = 0; // 栈中元素个数
var n = n; // 栈的大小
// 入栈
this.push = function(item) {
if (n === count) return false; // 栈已满
data[n] = item;
count++;
return true;
}
// 出栈
this.pop = function() {
if (count === 0) return null; // 栈中无数据
var res = data[count-1];
count--;
return res;
}
}
无论顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，其时间复杂度均为 O(1)
支持动态扩容的顺序栈
出栈时间复杂度仍为 O(1)
入栈时，当栈未满时间复杂度仍为 O(1)最好；满栈需要进行扩容，且将当前栈中数据迁移，时间复杂度为 O(n)最坏。根据摊还分析法计算平均复杂度
当 K 个数据入栈每次入栈操作时间复杂度为 O(1)，再次入栈需要进行扩容及数据迁移动作，时间复杂度为 O(k)。将 K 个数据搬移均摊到 K 次入栈操作，每个入栈操作只需要一个数据搬移和一个数据入栈操作，以此类推均，入栈操作的均摊事件复杂度为 O(1)。
将耗时多的操作均摊到其他操作上，因此均摊时间复杂度一般都等于最好情况的时间复杂度
经典应用场景
1. 函数调用栈
操作系统给每个线程分配独立的内存空间，内存空间被组织成“栈”结构，用来存储函数调用时的临时变量。函数执行过程中，进行相应的入栈出栈操作。
2. 编译器利用栈来实现表达式求值
使用两个栈。分别为操作数栈，运算符栈
简化背景：表达式中，只存在加减乘除预算
实现原理：
- 遍历表达式串，当遇到数字时将数字推入操作数栈。
- 遇到操作符时，取操作符栈顶项比较优先级，若当前优先级高，直接推入操作符栈。否则(优先级低或相同)依次从操作数栈中取两位进行计算，将计算结果推入操作数栈
- 遍历结束依次取操作数与符号进行计算，直至栈为空
3. 栈在括号匹配中的应用
简化背景：表达式中，只存在方、圆、花三种类型括号，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式，检测表达式使用括号是否合法
实现原理：
- 使用一个栈来存储我们的左括号
- 遍历表达式，遇到左括号时推入栈中。遇到右括号，从栈中取出一个左括号与之匹配，若匹配成功则继续遍历。若无法匹配或者栈中无数据，说明为不合法字串。当所有括号都扫描完后，如果栈为空，说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式
解答开篇
浏览器如何实现前进后退
使用两个栈 X 和 Y，X 存储前进页，Y 存储后退页，根据前进后退操作 XY 出栈入栈，注意 Y 有需要清空栈的情况存在
- 依次打开 abc 页。则 X 中从上至下有 cba，Y:null
- 后退至 a 页。X:a，Y:bc
- 前进至 b 页后打开 d。X:dba，Y:null
思考
为什么函数调用要用“栈”来保存临时变量？用其他数据结构不行吗？
不一定非要用栈来保存临时变量，只是如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，最顺理成章
从调用函数进入被调用函数，对于数据来说变化的是作用域。因此，保证每进入一个新的函数，都是一个新的作用域就可以。使用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。
关于栈的题目
序号对应 Leetcode 上题序
- 有效的括号 20
- 最小栈 155
- 用栈实现队列 232
- 比较含退格的字串 844
- 基本计算器 224
- 棒球比赛 682
- 下一个更大元素 496
这里简述一下我的解题方式，具体代码实现移步下篇
有效的括号
使用栈存储左括号
遍历字串，遇到左括号时入栈；右括号时，取栈顶符号匹配，若无法匹配或者栈中无数据，说明为不合法字串
当所有括号都扫描完后，如果栈为空，说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式
最小栈
先进先出，一个栈中加入A时已存在BCD，那么只要A存在，BCD就一定存在栈中
使用辅助栈保存最小值，当进栈时取辅助栈顶元素与当前值比较存储最小值(每次存储当前栈中的最小值)
出栈时将辅助栈中最顶值一并弹出
在任意时刻，栈内的最小值就是辅助栈顶的值
用栈实现队列
将一个栈当作输入栈，用于压入push传入的数据；另一个栈当作输出栈，用于pop和peak操作
每次 pop或peak 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序
比较含退格的字串
数字入栈，当遇到'#'时，将栈顶元素出栈，结束后比较值
基本计算器
创建符号号栈及数字栈
遍历匹配')'时，取符号至'('、取数字计算，将结果存入数字栈
遍历结束进行计算至栈为空
棒球比赛
遍历计算每回合得分后计算总得分
下一个更大元素
暴力解法：在nums2中找到当前num1中比较元素，后遍历剩下元素找到第一个较大元素
单调栈解法：先行将nums2中的数字，对应的下一个更大的数字找出来，然后放到哈希表中；供后面nums1 直接使用即可，可以将时间复杂度降到n + m
创建一个临时栈，一个hash表
- 遍历num2找到每个数的下一个最大数。
将遍历数X与栈顶元素比较，若栈顶无元素直接推入X
若栈顶数 > X 将元素推入栈中以便下一次比较
若栈顶数 < X 将栈顶数弹出，与X对应记录在hashmap中 - 遍历栈，设置下一个更大元素默认数为-1
- 遍历num1直接从hashmap中获取对应结果
