October 11, 2018 · 数据结构与算法 本文字数: 635 阅读时长:2 min 全站字数:344.2k

敏而好学之WHAT——栈的精髓

  1. 栈征状
  2. 栈实现
  3. 栈应用
    1. 函数调用栈
    2. 表达式求值
    3. 括号匹配
    4. 浏览器的后退和前进功能

本文是数据结构与算法之美专栏的学习笔记。

栈征状

说到栈,最经典的比喻就是那一摞的盘子。只能从上往下一个一个取,不能再中间取,因为会倒了摔个粉碎。栈的最大特点就是后进先出。栈只允许在一端插入和删除数据。

栈实现

栈既可以使用数组实现,也可是使用链表实现。栈的空间复杂度为O(1),因为不需要额外的数组,除了存储栈本身的数据。出栈和入栈的时间复杂度为O(1)

如果是数组实现的顺序栈,同时支持动态扩容。由于当栈满是需要动态扩容拷贝数据,出栈的时间复杂度仍然不变为O(1),但是入栈时的最差时间复杂度将为O(n)。这是由于当栈空间不够是,需要重新申请内存并进行数据移动。

对于栈的平均入栈时间复杂度分析,可以使用均摊分析的方法。对于一个大小为n的数组,进行n此入栈操作,复杂度是O(1),当第n个元素入栈时,需要扩容,假设为2n大小,则需要进行n次数据移动操作,时间复杂度为O(n)。可以将这n次的数据移动均摊到之前的n次入栈操作,这样入栈的平均时间复杂度就是O(1)

栈应用

函数调用栈

操作系统会给每一个线程分配一个独立的内存空间,这个空间被组织成为栈的数据结构。每次调用一个函数,就会将临时变量等入栈,函数执行完毕后,将对应的变量出栈。

表达式求值

编译器使用栈数据结构求表达式的值。通过两个栈来实现。一个保存操作数,一个保存运算符。然后从左到右遍历表达式,遇到数字就如操作数栈,遇到运算符就比较与操作数栈顶元素的优先级,如果比栈顶操作符的优先级高,就将当前操作符入操作数栈,否则,将栈顶的运算符出栈,并取两个操作数出栈,进行计算,将结果入操作数栈。

括号匹配

实现思路同上,只不过使用一个栈即可。

浏览器的后退和前进功能

使用双栈实现。