栈(上)

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

概述

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

img

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

img

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

树的遍历

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

![img](father, child)

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

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

个人来说,我觉得将栈底想象成右边,元素从左边进行插入和获取会比较容易理解。

前序

( root ) ( left ) ( right ) ]

中序

[ left ] [ root ] [ right ]

后序

[ left ] [ right ] [ root ]

  1. 为什么使用栈,而不是其他数据结构来实现递归。

递归函数一般来说是需要作用于结构体里面的所有对象的,如果对树结构进行递归,那么递归应该对每一个节点都运行一次。(这里我们不讨论使用动态规划或者缓存来简化计算的情况)简单地来说,栈能够修改下一个执行的对象,例如当

( root ) ]

当我们从栈中获取元素 ( root ) 后,正常的下一个执行的对象应该是空的,但是如果我们在每次执行前对当前元素进行一些操作,例如,将当前节点的右支点和左支点分别压入栈中,那么我们在执行之前就能得到这样的栈,下一个执行对象就变成 root.left 了

( root.left) ( root.right ) ]
  1. 如何使用 stack