1. 什么是栈?
栈的特点是后进先出, 是一种 "操作受限" 的线性表, 只允许在一端插入和删除. 当某个数据集合只涉及在一端插入和删除数据, 并且满足后进先出, 先进后出的特性, 就应该首选 "栈" 这种数据结构.
2. 如何实现栈?
栈主要包含两个操作, 入栈和出栈. 实际上, 栈既可以用数组来实现, 也可以用链表来实现. 用数组实现的栈叫作顺序栈, 用链表实现的栈叫作链式栈. 用 Java 实现并不难, 建议两种方式都试一试.
不管是顺序栈还是链式栈, 入栈, 出栈只涉及栈顶个别数据的操作, 所以时间复杂度是 O(1). 在入栈和出栈过程中, 只需要一两个临时变量存储空间, 所以空间复杂度是 O(1).
3. 支持动态扩容的顺序栈
实际上, 支持动态扩容的顺序栈, 我们平时开发中并不常用到, 讲这个的目的是复杂度分析.
对于出栈操作来说, 不会涉及内存的重新申请和数据的搬移, 所以出栈的时间复杂度仍然是 O(1). 对于入栈操作来说, 在大部分情况下, 时间复杂度 O 都是 O(1), 只有在个别时刻才会退化为 O(n), 把耗时多的入栈操作的时间均摊到其他入栈操作上, 平均情况下的耗时就接近 O(1). 所以入栈操作的均摊时间复杂度就为 O(1).
4. 栈的应用举例
1. 在函数调用中的应用
经典的一个应用场景就是函数调用栈. 操作系统给每个线程分配了一块独立的内存空间, 这块内存被组织成 "栈" 这种结构, 用来存储函数调用时的临时变量. 每进入一个函数, 就会将临时变量作为一个栈帧入栈, 当被调用函数执行完成, 返回之后, 将这个函数对应的栈帧出栈.
2. 在表达式求值中的应用
对于加减乘除这种数学运算, 比如 34+13*9+44-12/3, 编译器通过两个栈来实现. 一个保存操作数的栈, 另一个是保存运算符的栈. 从左向右遍历表达式, 当遇到数字时, 就直接压入操作数栈; 当遇到运算符, 就与运算符栈的栈顶元素进行比较. 如果比运算符栈顶元素的优先级高, 就将当前运算符压入栈; 如果比运算符栈顶元素的优先级低或者相同, 从运算符栈中取栈顶运算符, 从操作数栈的栈顶取 2 个操作数, 然后进行计算, 再把计算完的结果压入操作数栈, 继续比较.
3. 在括号匹配中的应用
借助栈来检查表达式中的括号是否匹配, 比如 {}{()}. 假设表达式中只包含三种括号, 圆括号 (), 方括号 [] 和花括号 {}, 并且它们可以任意嵌套. 给出一个包含三种括号的表达式字符串, 如何检查它是否合法呢?
用栈来保存未匹配的左括号, 从左到右依次扫描字符串. 当扫描到左括号时, 则将其压入栈中; 当扫描到右括号时, 从栈顶取出一个左括号. 如果能够匹配, 则继续扫描剩下的字符串. 如果扫描的过程中, 遇到不能配对的右括号, 或者栈中没有数据, 则说明为非法格式. 当所有的括号都扫描完成之后, 如果栈为空, 则说明字符串为合法格式; 否则, 说明有未匹配的左括号, 为非法格式.
4. 实现浏览器的前进后退功能
来源: http://www.jianshu.com/p/66d2603ff38e