Stack介绍

这个主题已经在这里进行了教程

堆栈就像一个数组，但功能有限。您只能push添加一个新的元素到堆栈的顶部，pop从顶部删除元素，并peek顶部元素而不弹出它。

你为什么想做这个？那么，在许多算法中，您希望在某个时间点将对象添加到临时列表中，然后再次将它们从列表中拉出。通常您添加和移除这些对象的顺序很重要。

堆栈为您提供LIFO或后进先出订单。您最后推出的元素是第一个与下一个流行音乐相关的元素。（一个非常相似的数据结构，queue是FIFO或先进先出。）

例如，让我们在堆栈上push一个数字：

stack.push(10)

现在是堆栈[ 10 ]。push一个号码：

stack.push(3)

现在是堆栈[ 10, 3 ]。再push一个号码：

stack.push(57)

现在是堆栈[ 10, 3, 57 ]。让我们从堆栈中pop最上面的数字：

stack.push(57)

这会返回57，因为那是我们推送的最近的数字。堆栈又是[ 10, 3 ]。

stack.push(57)

这将返回3，依此类推。如果堆栈为空，则弹出返回，nil或者在某些实现中它会给出错误消息（“stack underflow”）。

在Swift中很容易创建一个堆栈。它只是一个数组的封装器，它可以让你push，pop并查看堆栈的顶层元素：

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使用该返回地址跳回到调用者。这就是为什么如果你调用了太多的函数 - 例如在一个永不结束的递归函数中 - 当CPU堆栈空间不足时，你会得到所谓的“stack overflow”。

传送门