【译】Swift算法俱乐部-栈

Swift算法俱乐部

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。欢迎有兴趣学习算法和数据结构，有时间的小伙伴一起参与翻译，欢迎issue，或者直接提交pull request。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Stack

---

这个话题已经有个辅导文章

栈类似于数组，但是限制了存取操作的灵活性。栈只允许使用者从栈顶 压入(push) 元素；从栈顶 弹出(pop) 元素；取得(peek) 栈顶元素，但不弹出。

这样的限制有什么意义呢？在很多算法的实现中，你可能需要将某些对象放到一个临时的列表中，之后再将其取出。通常加入和取出元素的顺序非常重要。

栈可以保证元素存入和取出的顺序是后进先出(last-in first-out, LIFO)的。栈中弹出的元素总是你最后放进去的那个。另外一个非常类似的数据结构是队列，它是一个先进先出(first-in, first-out, FIFO)的结构。

举例来说，我们先将一个数字压入栈中：

stack.push(10)

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

stack.push(3)

栈现在是 [10, 3]。再压入一个数字：

stack.push(57)

栈现在是 [10, 3, 57]。现在把栈顶的数字弹出来：

stack.pop()

这行代码返回 57，因为它是我们最后压入的元素。现在栈又变成了 [10, 3]。

stack.pop()

这行代码返回 3，以此类推。如果栈空了，弹栈操作将返回 nil，在有些实现中，会触发一个 stack underflow 错误消息。

栈在 Swift 中的实现非常容易。只需要包装一下自带的数组，将存取功能限制为 pop、push 和 查看栈的顶部元素。

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
  }
}

注意到，压栈操作是将新元素压入数组的尾部，而不是头部。在数组的头部插入元素是一个很耗时的操作，它的时间复杂度为 O(n)，因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1)；无论数组有多少元素，这个操作所消耗的时间都是一个常量。

关于栈的有趣知识：每次你调用函数或方法，CPU都会将函数返回地址压入到运行栈中。当这个函数执行结束的时候，CPU将返回地址从栈中取出，并据此返回到函数被调用的位置。所以，如果不断地调用太多的函数(例如死递归函数)，就会得到一个所谓的“栈溢出(stack overflow)” 错误，因为CPU运行栈没有空间了。

作者：Matthijs Hollemans；译者：KSCO
校队：Andy Ron