Stack in Swift

栈 像是一个有限功能的数组，你只可以通过’push’在栈顶添加一个新的元素，用 pop 从栈顶移除这个元素，同时 peek (一瞥)栈顶元素而不弹出（意为只能对栈顶元素执行存取操作）。

为什么我们需要这么做？在很多算法中你想将一个元素加入到一个临时列表里，与此同时你希望稍后将它们拉去出来，通常你添加或删除这些元素的顺序是被关心的问题。

栈结构给了你一个后进先出的顺序（ LIFO ）即 last-in first-out 。 你最后一个push进去的元素就是你在下一次第一个pop出来的元素。（另一个比较相似的结构是 队列（queue） ， 它是FIFO先进先出的。）

举个栗子，以下代码将一个数字’push’到栈中：

    stack.push(10)

现在，当前栈是[10]。接下来在push下一个数字：

  	  stack.push(3)

当前栈变为[10， 3]。 再push一个新的数字：

	  stack.push(57)

当前栈是[10, 3, 57]。让我们弹出栈顶元素：

	  stack.pop()

这会返回57，因为它是我们最后一次被push的，现在栈的状态又变回了[10，3]

	  stack.pop()

这将继续返回3。如果栈为空，pop动作返回nil，再另一些实现方式里会抛出错误信息(“stack underflow”)。

在Swift中，栈很容易被创建。它只是数组的包装。 public struct Stack { 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 func peek() -> T? {
    return array.last
  }
}

注意push将元素放在数组尾部而不是开始，在数组开头插入元素代价很大，复杂度是 O(n) ，因为这需要在内存中移动数组中的所有元素。而在尾部添加的复杂度为 O(1) ；栈总是花费相同的时间，而无视数组大小或规模（我认为是稳定性）。

一个有趣的事实是：每次你调用一个方法或者函数，CPU会将返回地址放入一个栈。当函数结束，CPU使用这个返回地址跳回调用者。这就是为什么如果你调用太多函数—例如永不结束的递归函数—你得到一个所谓的栈溢出（stack overflow）错误，原因是CPU栈空间已被用尽。