栈结构(上)

作者:Windson Yang
更新时间:January 8, 2020
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明 www.enginego.org。

概述

栈绝对是数据机构中最被低估的一类,许多对栈的理解仅仅停留在后入先出这几个字。却不知道这几个字真正蕴含的力量,首先介绍下栈结构,简单来说,当你手上有排序好的编号为1到n的书,当你从编号1开始把这些书放到一个箱子的话,那么这个箱子会变成。

![img]()

如果你把书再次拿出来,编号为n的书因为在顶部所以第一本被拿出来,如此类推,手上的书从编号1到n变成编号n到1。

![img]()

好吧,这有什么用,这不就是翻转一个队列吗?或者说,原本从头开始取,现在从最后开始取而已。有什么实际作用呢?这是一个非常好的问题。现实生活中我们一般只会将一维数组按顺序放入栈中,就如放书的例子,这样用途确实不大(除了单调栈之外,我们以后会介绍到)。但是当你将图或者树这类相对复杂的结构和栈结合起来的话,那么就能得到非常多的应用方式。而且当每个元素可以根据状态重复放入栈的时候,更加演变出非常复杂的使用方法。例如使用栈来实现 DFS 或者 递归。通过改变元素的状态以及运行顺序就能实现我们需要的算法。这属于比较高级的用法,不过只要你真正理解了栈结构的话,我觉得你也可以轻而易举地把递归改为栈来实现。

树的遍历

常见的树的遍历类型有四种,前序,中序,后序以及层序,其中前三种非常类似,只是父节点以及子节点位置的相对不同。

img

实现方式也有多种,最简单的当然是递归实现,这里给出伪代码:

function preorder(root):
    if not root:
        return
    print root
    preorder(root.left)
    preorder(root.right)

前序

[ root ] [ left ] [ right ]

中序

[ left ] [ root ] [ right ]

后序

[ left ] [ right ] [ root ]

为什么使用 stack,如何使用 stack