03-1 栈

数据结构与算法之美 - 学习笔记

引出问题:浏览器如何实现前进后退功能
[图片上传失败...(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)。

入栈的时间复杂度.png

将耗时多的操作均摊到其他操作上,因此均摊时间复杂度一般都等于最好情况的时间复杂度


经典应用场景

1. 函数调用栈

操作系统给每个线程分配独立的内存空间,内存空间被组织成“栈”结构,用来存储函数调用时的临时变量。函数执行过程中,进行相应的入栈出栈操作。

2. 编译器利用栈来实现表达式求值

使用两个栈。分别为操作数栈,运算符栈

简化背景:表达式中,只存在加减乘除预算

实现原理:

  1. 遍历表达式串,当遇到数字时将数字推入操作数栈。
  2. 遇到操作符时,取操作符栈顶项比较优先级,若当前优先级高,直接推入操作符栈。否则(优先级低或相同)依次从操作数栈中取两位进行计算,将计算结果推入操作数栈
  3. 遍历结束依次取操作数与符号进行计算,直至栈为空
栈实现计算器.png

3. 栈在括号匹配中的应用

简化背景:表达式中,只存在方、圆、花三种类型括号,{[] ()[{}]}或[{()}([])]等都为合法格式,而{[}()]或[({)]为不合法的格式,检测表达式使用括号是否合法

实现原理:

  1. 使用一个栈来存储我们的左括号
  2. 遍历表达式,遇到左括号时推入栈中。遇到右括号,从栈中取出一个左括号与之匹配,若匹配成功则继续遍历。若无法匹配或者栈中无数据,说明为不合法字串。当所有括号都扫描完后,如果栈为空,说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式

解答开篇

浏览器如何实现前进后退

使用两个栈 X 和 Y,X 存储前进页,Y 存储后退页,根据前进后退操作 XY 出栈入栈,注意 Y 有需要清空栈的情况存在

  1. 依次打开 abc 页。则 X 中从上至下有 cba,Y:null
  2. 后退至 a 页。X:a,Y:bc
  3. 前进至 b 页后打开 d。X:dba,Y:null

思考

为什么函数调用要用“栈”来保存临时变量?用其他数据结构不行吗?

不一定非要用栈来保存临时变量,只是如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,最顺理成章

从调用函数进入被调用函数,对于数据来说变化的是作用域。因此,保证每进入一个新的函数,都是一个新的作用域就可以。使用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。


关于栈的题目

序号对应 Leetcode 上题序

  1. 有效的括号 20
  2. 最小栈 155
  3. 用栈实现队列 232
  4. 比较含退格的字串 844
  5. 基本计算器 224
  6. 棒球比赛 682
  7. 下一个更大元素 496

这里简述一下我的解题方式,具体代码实现移步下篇

有效的括号

使用栈存储左括号
遍历字串,遇到左括号时入栈;右括号时,取栈顶符号匹配,若无法匹配或者栈中无数据,说明为不合法字串
当所有括号都扫描完后,如果栈为空,说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式

最小栈

先进先出,一个栈中加入A时已存在BCD,那么只要A存在,BCD就一定存在栈中
使用辅助栈保存最小值,当进栈时取辅助栈顶元素与当前值比较存储最小值(每次存储当前栈中的最小值)
出栈时将辅助栈中最顶值一并弹出
在任意时刻,栈内的最小值就是辅助栈顶的值

用栈实现队列

将一个栈当作输入栈,用于压入push传入的数据;另一个栈当作输出栈,用于pop和peak操作
每次 pop或peak 时,若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序

比较含退格的字串

数字入栈,当遇到'#'时,将栈顶元素出栈,结束后比较值

基本计算器

创建符号号栈及数字栈
遍历匹配')'时,取符号至'('、取数字计算,将结果存入数字栈
遍历结束进行计算至栈为空

棒球比赛

遍历计算每回合得分后计算总得分

下一个更大元素

暴力解法:在nums2中找到当前num1中比较元素,后遍历剩下元素找到第一个较大元素

单调栈解法:先行将nums2中的数字,对应的下一个更大的数字找出来,然后放到哈希表中;供后面nums1 直接使用即可,可以将时间复杂度降到n + m
创建一个临时栈,一个hash表

  1. 遍历num2找到每个数的下一个最大数。
    将遍历数X与栈顶元素比较,若栈顶无元素直接推入X
    若栈顶数 > X 将元素推入栈中以便下一次比较
    若栈顶数 < X 将栈顶数弹出,与X对应记录在hashmap中
  2. 遍历栈,设置下一个更大元素默认数为-1
  3. 遍历num1直接从hashmap中获取对应结果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容