作者 | 梁唐

大家好，我是梁唐。

栈这个结构我想大家应该都耳熟能详，尤其是在很多地方将和堆并列在一起，称作“堆栈”就更广为人知了。

但有名归有名，真要问起来栈这个结构到底有什么用？在哪里派上了用场，估计不少同学还是一脸懵。今天就和大家聊聊这个话题。

栈和队列的本质其实都是数组（严格地说是线性表）。只不过我们在数组上增加了一些限制，使得它满足一定的条件而已，所以很多对数据结构畏首畏尾的同学可以放宽心，栈没什么特别的花样，就只是一种特殊的数组。

和其他广义上的线性表数据结构比起来，栈的特殊性只有两条，一条是先进后出，另一条是只能从数组的一侧读写。但本质上来说这两条是一样的，由于我们只能从一侧读写元素，所以进的越早出的越晚，当然是先进后出。从下面这张图应该很容易能看明白。

栈规定了我们只能从一侧进行读写，常规上我们将能够读写的一侧称作是栈顶。不能读写的另一侧称为是栈底。从上面的图可以看到，只有栈顶的元素出栈了之后，才能访问到栈底的元素。

我们用Python的数组来实现栈这个数据结构，去掉注释真的只有30行不到，可以说是非常简单，我们先来看代码。

本质上来说，一般的栈实现只有以上这么几个方法，可能会更少。因为有些语言当中的栈，top和弹出是合并的。意味着访问必须要弹出，不支持非弹出访问。所以栈的实现逻辑是非常简单的，甚至可以说是毫无技术含量，非常适合入门数据结构。

当然，从另一个方面也可以说栈的实现原理并不太重要，相比之下更重要的是栈一般会用在什么地方。

栈最广泛的应用就是在操作系统当中，比如在程序执行调用方法的时候，在编译器内部，其实是记录了一个当前调用的方法栈。

举个例子，比如当前调用到的方法是A，如果在A方法中又去调用了方法B，那么计算机就会在系统方法栈当中存储一个指向B方法的指针，如果B方法又调用到了C方法，那么又会新增一个C的指针。当C方法执行结束，那么C就会弹出，计算机会将C的结果带入B，继续执行之前的B，以此类推，直到栈空为止。

比如这么一段代码：

当它运行的时候，内部的方法栈是这样的：

当funcD返回结果的时候，则随着结果的返回，栈中的方法一层层地出栈。

那么，问题来了，如果一个方法A自己调用自己会怎么样？

答案是计算机会创建一个新的A的指针填入栈中，如果A继续递归，那么系统再创建一个新的指针入栈……从上面这个结论发散，我们可以得到另外两个结论。

第一，我们写程序时候的递归，在编译器内部其实是以栈的形式记录的。

第二，既然是栈，那么必然是有存储限制的。如果我们用一个死循环去不停地递归，当栈的深度超过限制的时候，就会出现错误。大家可以去尝试一下，如果是C++，应该会得到SystemStackExceed错误，它表示超过栈的最大深度，也就是俗称的爆栈。

所以，递归的深度并不是无限的，因为除了操作系统对于运行内存的限制之外，编译器还会有最大递归深度的限制，防止递归中死循环导致系统崩溃。虽然各个语言实现机制不完全一样，但是有一点是肯定的，递归深度是有限的，我们不能无限制递归。

那问题来了，如果我们系统就是会存在大规模的递归怎么办？难道还要手动给机器加内存吗？

这是ACM玩家在赛场上经常遇到的问题之一，有经验的选手在第一天的热身赛时一定会做的事情除了配置vim或者其他IDE之外，就是会测试一下电脑的最大递归深度，防止在做题的时候出现爆栈。

在C++当中，可以通过嵌入汇编指令强行开大递归深度限制，但是即使如此也是有限的。并且据我所知只有C++可以这么干，对于其他语言，以及开大了递归深度还是不够用的情况，就只有一种办法，就是手动建栈模拟递归。

许多同学可能觉得递归痛苦，但是如果他们试着手动建栈来模拟递归的话，会发现要更加痛苦。不仅要额外增加变量存储中间状态，并且对于编程也是一个巨大的挑战。

我们来看一个例子：

这是一棵简单的二叉树，画出来是这个样子：

下面我们要通过栈在不使用递归的情况下来中序遍历它，中序遍历我们都知道，就是先遍历左子树，然后输出当前节点，再遍历右子树。写成递归非常方便，只有几行：

大家想想，如果不使用递归应该怎么办？如果你真的试着去写，就会发现看起来很简单的问题好像变得非常复杂。根据上面的结论，我们很容易可以想到，我们可以把节点存储在栈当中，但是存储数据只是表象。本质问题是当我们从栈当中拿到了一个节点之后，我们怎么判断它究竟应该做什么？应该遍历左节点吗，应该输出吗，还是应该遍历右节点？

对这些问题仔细分析和思考，我们可以发现它们都和递归的回溯有关。

在递归当中，当我们遍历完了当前节点的某棵子树之后，随着栈的弹出，还会回到这个节点。比如上面这棵树当中，在递归过程当中，我们会两次碰到1这个节点。第一次时它不会输出1，而是先去遍历了它的左子树，也就是3，之后再次回到1，由于它的左子树已经遍历过，所以会输出1。

这个离开又回来的过程称为回溯。如果你把树结构想象成瀑布的话，这个过程有点像是先顺流而下，又逆流而上，翻译成回溯还是蛮合理的。

我们回到之前的问题，所有的搞不清楚的本质都来源于我们无法判断当前遇到的节点究竟是初次见面，还是回溯之后的久别重逢。而这关系到我们要对它做什么。

原本在递归当中，由于程序会记录递归时的状态和代码运行的位置，递归回溯之后会回到上次调用的位置，所以我们可以忽略这个问题。而现在我们由于不再使用递归，所以需要我们自己来判断节点的状态。

既然要判断节点的状态，那么我们就需要在节点当中加一个状态的字段，表示这个节点的左子树是否遍历过。显然在一开始的时候，所有的节点状态都是True，表示没有遍历过。

接着就很简单了，我们就按照左中右的顺序遍历节点，只要左子树存在就往左边遍历，在一路往左的过程中遇到的这些节点填入栈中，并把它们的状态改成false。因为往左遍历，就是在遍历这些节点的左子树，所以需要设置成False。

当内层的while循环执行结束的时候，说明左子树已经遍历完了，因为是中序遍历，所以我们先输出当前节点的值，再往右遍历。往右得到的是一棵全新的子树，并没有被遍历过左子树，所以状态依然保持True。

这段代码虽然短，但其实不简单，想要完全看懂需要对递归和循环有深入的理解。

属于典型的看着简单实际不容易的题，我个人比较喜欢这类问题，除了锻炼思维之外也很适合用来面试，候选人的思维能力、代码驾驭能力基本上都一清二楚了。

没有看懂的同学也不用担心，因为在实际场景当中并不会遇到这样的场景，以后还会推出其他关于递归和搜索算法的文章，只要你坚持阅读，我相信一定会看懂的。