数据结构与算法之美 - 学习笔记
引出问题:浏览器如何实现前进后退功能
[图片上传失败...(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中获取对应结果