第4章：栈

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

煎饼
书籍
纸张
现金

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

好消息：一叠薄饼。坏消息：你只能吃最上面的煎饼。

栈操作

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

栈只有两个基本操作。

推送。将一个元素添加到栈的顶部。
pop。移除栈顶部的元素。

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

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

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

实施

打开本章的起始游戏场。在playground的Source文件夹中，创建一个名为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"))

    -----------
    """
  }
}

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

对于CustomDebugStringConvertible协议所要求的debugDescription中花哨的函数调用链，你正在做三件事。

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

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

推送和弹出操作

给你的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这样的协议会违背这个目标，因为它通过迭代器和下标暴露了所有的元素。在这种情况下，少即是多!

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

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

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。

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

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

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

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

关键点

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

上一章	目录	下一章