【译】数据结构与算法——栈

发表于 更新于 分类于

栈类似一个功能受限的数组。仅可以将新元素从栈的顶端 push（压入） ，或着从顶端 pop（弹出） ，如果不弹出元素，那么只能看到栈顶元素。

那为什么要这么做呢？这是因为，在众多算法问题中，经常会遇到将某些元素添加到一个临时的列表中，而后又将它们移除，且顺序不能乱的情况。

而栈恰好满足了这种后进先出（LIFO）的顺序需求。最后一个压入栈的元素也最先出被弹出。（另一个类似的数据结构是队列(queue)，它是先进先出）
例如，压入一个数：

1
stack.push(10)

现在栈是 [ 10 ]。压入下一个数：

1
stack.push(3)

此时栈是 [ 10, 3 ]。在压入一个数：

1
stack.push(57)

栈变成了 [ 10, 3, 57 ] 。现在我们来弹出最顶端的数：

1
stack.pop()

返回了 57，正是我们刚刚压入的数。现在栈又变成了[ 10, 3 ]。

1
stack.pop()

这一次返回 3，以此类推。如果栈空了，会返回 nil 或者在其它一些实现中返回错误消息 “栈下溢出(stack underflow)”。

通过 Swift 创建栈非常简单。对数组进行封装以满足 push，pop，以及读取栈顶元素等操作即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public struct Stack<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

  public mutating func push(_ element: T) {
    array.append(element)
  }

  public mutating func pop() -> T? {
    return array.popLast()
  }

  public var top: T? {
    return array.last
  }
}

注意，push 是新元素添加到数组的末尾，而不是开头。在开头插入元素是一个非常昂贵的操作，时间复杂度为 **O(n)**，之所以如此，是因为需要将数组中已有的元素在内存中做整体移动。而尾部追加的时间杂度是 **O(1)**；它总是消耗固定的时间，与数组的大小无关。

有趣的栈：每次调用函数或方法，CPU都会将返回地址放入栈中。一旦抵达函数结尾，CPU 就会通过返回地址跳回到调用者。这也是为什么当你调用太多函数，例如：无限递归，会导致“栈溢出”，因为 CPU 的栈的空间已经耗尽了。

最后

该系列文章翻译自 Raywenderlich 的开源项目：swift-algorithm-club，意在帮助有一定算法基础的同学进行回顾，如果你才接触算法，那么建议移步阅读详细教程

由 Matthijs Hollemans 为 Swift 算法社区撰写

由 William Han 翻译