数据结构与算法四：Stacks

Stacks

栈在生活中无处不在，比如以下常见示例：

• 煎饼
• 书籍
• 纸
• 现金

堆栈数据结构在概念上与对象的物理堆栈相同。将 item 添加到堆栈时，会将其放置在堆栈的顶部。当从堆栈中移除一个 item 时，则始终会移除最顶层的item。

Stack operations

堆栈很有用，也非常简单。堆栈只有两个基本操作：

push： 添加一个元素到栈顶
pop： 移除栈顶元素

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

堆栈在所有编程学科中都被广泛使用。列举几个示例：

• iOS 使用导航堆栈将视图控制器 push 和 pop 到视图。
• 内存分配（Memory allocation）在架构层（architectural level）使用堆栈。局部变量（local variables）的内存也使用堆栈进行管理。
• 搜索算法，例如从迷宫中寻找路径，使用堆栈来促进回溯。

Implementation

创建一个名为 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 在一端提供恒定时间的插入和删除。这两个操作可以满足堆栈的 LIFO 特性。

CustomDebugStringConvertible 协议主要做三件事：

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

这可用于打印堆栈的调试信息。

push and pop operations

将以下两个操作添加到堆栈中：

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) 的时间复杂度。

Non-essential operations

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

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

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

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

Less is more

也许你会问，是否可以让堆栈采用 Swift collection protocols 呢？

堆栈的目的是限制访问数据的方式。采用诸如 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<String>。

我们可以更进一步，使堆栈可从数组 literal 初始化。 将此添加到您的堆栈实现中：

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

这将创建一个 Doubles 堆栈并弹出顶部值 4.0。同样，类型推断使我们不必键入更冗长的 Stack<Double>。

堆栈在搜索树和图的问题方面至关重要。想象一下，在迷宫中寻找出路，每次你来到一个左、右或直的决策点时，你都可以将所有可能的决策推到你的堆栈上。当遇到死胡同时，只需从堆栈中弹出并继续回溯，直到逃脱或遇到另一个死胡同。

Key points

• 堆栈是一种后进先出的数据结构。
• 堆栈非常简单，但堆栈是许多问题的关键数据结构。
• 堆栈的两个基本操作是添加元素的 push 方法和删除元素的 pop 方法。

2022.09.12 22:58
译于：上海 二联