一般什么情况下会使用栈

Question

在老师的课程讲解下，我理解的栈是有多种的实现方式，比如依赖于动态数组的实现方式，方法其实都是调用动态数组的方法，只不过是把规则改为了只能先进后出的。
什么时候会用到这种数据结构呢？比如说数组我们平时程序中会用到，集合也是一样，但是栈就不知道了

Answer 1

liuyubobobo 2018-11-23 19:10:23

栈确实是一个在组建业务逻辑是不太常用的数据结构，但是在计算机的很多专有领域，有着关键的，不可替代的作用。

在课程中，我印象里给出了几个很常见的应用栈的例子：

如果你想做一个编辑器的“撤销”功能（不管是word，excel，IDE，ps，甚至是游戏中），你都需要栈；

和撤销类似，“返回”也是一个需要栈的场景。点击浏览器的“返回”，为什么能回到上一个页面，再点一下，回到上上个页面？这一切记录在栈中；

在编译原理中，大量的需要使用栈，比如括号匹配算法（你的IDE能自动提示你括号匹配是否有问题，这背后因为有栈）。实际上，就连简单的表达式计算，也需要栈（比如你在IDE里写出x = 1 + 2 * (3 + 4) /5 - 6，运行以后，编译器或者解析器是如何给x赋上正确的值的？这个算法背后需要使用栈：）有兴趣可以搜索学习一下Shunting-yard算法）

递归本身和栈有着密不可分的关系。这点在这个课程讲树的时候我就会提到，而在我的《玩转算法面试》课程（https://coding.imooc.com/class/82.html）中，还会有更深入的介绍。所有的递归转非递归，都需要使用栈；而递归在计算机的世界中，近乎无所不在：）

而实际上，我们整个操作系统中，系统调用都是基于栈的，所谓的“系统栈”。想象一下计算机语言中的函数调用过程，函数A中调用B，函数B中调用C，C执行完会返回B，B执行完又会返回A，怎么返回？用栈记录：）所以，你可能常听到“系统栈”这个词，就是这个道理。

如果想了解更多使用栈可以解决的问题，Leetcode中所有有着“栈”标签的问题，都可以使用栈解决（虽然不全面，毕竟Leetcode比较偏面试问题，缺少更多实际问题，但足以用于参考）。传送门：https://leetcode-cn.com/tag/stack/

加油！：）

• 提问者 无心铁憨憨 #1

  那我是不是可以理解为，栈其实在程序中是经常存在，甚至无处不在的，只是我们显性的去使用的频率是非常非常少的，它在我们不知情的情况下一直都是存在的

• liuyubobobo 回复 提问者 无心铁憨憨 #2

  对于初学者来说，是的：）