4.堆栈¶

堆栈无处不在。以下是一些常见的例子，你会把东西堆起来：

煎饼
书本
纸张
现金

stack数据结构在概念上与物理的物体堆栈相同。当你向堆栈中添加一个项目时，你把它放在堆栈的顶部。当你从一个堆栈中删除一个项目时，你总是删除最上面的项目。

堆栈操作¶

堆栈是有用的，也是极其简单的。建立堆栈的主要目的是强制你如何访问你的数据。

对于堆栈来说，只有两个基本操作：

push：将一个元素添加到堆栈的顶部。
pop：删除堆栈顶部的元素。

将接口限制在这两种操作上，意味着你只能从数据结构的一侧添加或删除元素。在计算机科学中，堆栈被称为LIFO（后进先出）数据结构。最后被推入的元素是第一个被弹出的。

堆栈在编程的所有学科中都有突出的应用。举几个例子：

iOS使用导航堆栈将视图控制器推入和移出视图。
内存分配在架构层面上使用堆栈。本地变量的内存也是使用堆栈管理的。
搜索和征服算法，如寻找走出迷宫的路径，使用堆栈来促进回溯。

实施¶

打开本章的起始Playground。在你的Playground的Sources文件夹中，创建一个名为Stack.swift的文件。在该文件中，写下以下内容：

public struct Stack<Element> {

  private var storage: [Element] = []

  public init() { }
}

extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

在这里，你已经定义了你的Stack的后备存储。为你的堆栈选择正确的存储类型是很重要的。数组是一个明显的选择，因为它通过append和popLast在一端提供持续的插入和删除。这两个操作的使用将促进堆栈的LIFO性质。

对于CustomDebugStringConvertible协议所要求的debugDescription中的花式函数调用链，你要做三件事：

创建一个数组，通过storage.map { "\($0)" }将元素映射到String。
创建一个新的数组，使用reversed()来反转之前的数组。
通过使用joined(separator:)将数组扁平化为一个字符串。你用换行符"\n"来分隔数组中的元素。

这将创建一个可打印的Stack类型表示，你可以用来调试。

`push`和`pop`操作¶

给你的Stack添加以下两个操作：

public mutating func push(_ element: Element) {
  storage.append(element)
}

@discardableResult
public mutating func pop() -> Element? {
  storage.popLast()
}

相当直截了当! 在Playground的页面上，写下以下内容：

example(of: "using a stack") {
  var stack = Stack<Int>()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.push(4)

  print(stack)

  if let poppedElement = stack.pop() {
    assert(4 == poppedElement)
    print("Popped: \(poppedElement)")
  }
}

你应该看到以下输出：

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4

push和pop都有O(1)的时间复杂度。

非必要的操作¶

有几个不错的操作可以使堆栈更容易使用。在Stack.swift中，给Stack添加以下内容：

public func peek() -> Element? {
 storage.last
}

public var isEmpty: Bool {
  peek() == nil
}

一个堆栈接口通常包括一个peek操作。peek的概念是在不改变堆栈内容的情况下查看堆栈的顶部元素。

少即是多¶

你可能已经想知道你是否可以为堆栈采用Swift的收集协议。栈的目的是限制访问你的数据的方式的数量。采用诸如Collection这样的协议会违背这个目标，因为它通过迭代器和下标暴露了所有的元素。在这种情况下，少即是多!

你可能想利用一个现有的数组并将其转换为堆栈，以保证访问顺序。当然，也可以循环浏览数组元素，并push每个元素。

然而，由于你可以写一个初始化器来设置底层的私有存储。在你的堆栈实现中添加以下内容：

public init(_ elements: [Element]) {
  storage = elements
}

现在，将这个例子添加到主Playground：

example(of: "initializing a stack from an array") {
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
}

这段代码创建了一个字符串的堆栈，并弹出了最上面的元素"D"。注意，Swift编译器可以从数组中推断出元素的类型，所以你可以使用Stack，而不是更粗略的Stack<String>。

你可以更进一步，让你的堆栈可以从一个数组字头初始化。把这个添加到你的堆栈实现中：

extension Stack: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    storage = elements
  }
}

现在回到主Playground页面并添加：

example(of: "initializing a stack from an array literal") {
  var stack: Stack = [1.0, 2.0, 3.0, 4.0]
  print(stack)
  stack.pop()
}

这将创建一个Double的堆栈，并弹出最上面的值4.0。同样，类型推理使你不必输入更多的Stack<Double>。

堆栈对于搜索树和图的问题至关重要。想象一下，在一个迷宫中寻找你的路。每次你走到左、右或直的决定点时，你可以把所有可能的决定推到你的堆栈中。当你遇到死胡同时，只需从堆栈中跳出，继续往回走，直到你逃脱或遇到另一个死胡同。

关键点¶

堆栈是一个LIFO，即后进先出的数据结构。
尽管如此简单，堆栈是许多问题的关键数据结构。
栈的两个基本操作是添加元素的push方法和删除元素的pop方法。