Swift Algorithm Club:堆栈【译】

发表于

原文：https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack

堆栈

堆栈就像数组，不过功能有限。你只能通过Push添加一个新元素到堆栈的顶部，使用Pop从栈顶删除元素，可以不用Pop一个元素来查看栈顶的元素。

你为什么要这样做呢？是这样的，在很多算法中你想在某一时间段添加一些对象到一个临时数组，然后晚些时候又把这些对象从数组中拉出来。通常顺序是处决于你添加与删除对象情况。

一个堆栈给你一个后进先出或LIFO的顺序。最后Push进来的元素，第一个被Pop出来。（一个非常相似的数组结构，队列，先进先出 或者 FIFO）。

举个例子，让我们Push一个数字到堆栈：

1
stack.push(10)

这个堆栈现在是[10]。Push下一个数字：

1
stack.push(3)

这个堆栈现在是[10, 3]。再Push一个数字：

1
stack.push(57)

这个堆栈现在是[10, 3, 57]。让我们从栈顶Pop出一个数字：

1
stack.pop()

返回值为57。因为它是最近Push到栈中的。堆栈又变为[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
publich 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.popList()
  }
  
  public var top: T? {
    return array.last
  }
}

注意Push是将一个元素添加到数组尾部，而不是首部。插入到数组首部开销非常大的，为O(n)操作，因为这样操作必须挪动数组中所有已存在元素的内存地址。而添加到数组尾部是O(1)操作；这样做，不管理数组大小，所花时间都是同样的。

一个关于堆栈的有趣事实：你每次调用函数或方法时，CPU会把返回地址放置在堆栈上。当函数结束时，CPU会使用这个返回跳回到调用者。这就是为什么你调用太多函数方法时（举个例子在递归函数中它永远不结束）你会得到一叫“stack overflow” 就是CPU运行空间不足。

写自 Swift Algorithm Club 的 Matthijs Hollemans