Swift数据结构和算法03_栈
前言
有需要的同学可以订阅专栏：Swift数据结构和算法专题
代码地址：Swift数据结构和算法代码
正文
栈数据结构在概念上与对象的物理堆栈相同。将项目添加到栈时，会将其放置在栈的顶部。当我们从堆栈中移除一个项目时，我们始终会移除最顶层的项目。
栈操作
栈很有用，也非常简单。构建栈的主要目标是强制执行我们访问数据的方式。
栈只有两个基本操作：
• push：向栈顶添加一个元素。
• pop：移除栈顶元素。
将接口限制为这两个操作意味着我们只能从数据结构的一侧添加或删除元素。在计算机科学中，栈被称为 LIFO（后进先出）数据结构。最后推入的元素是最先弹出的元素。
堆栈在所有编程学科中都被广泛使用。列举几个：
• iOS 使用导航栈将视图控制器推入和弹出视图。
• 内存分配在架构级别使用栈。局部变量的内存也使用栈进行管理。
• 搜索算法，例如从迷宫中寻找路径，使用栈来促进回溯。
执行
打开本章的starter 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”分隔数组的元素。
这将创建可用于调试的可打印表示的栈。
push和pop操作
将以下两个操作添加到我们的栈中：
public mutating func push(_ element: Element) {
storage.append(element)
}
@discardableResult
public mutating func pop() -> Element? {
storage.popLast()
}
继续添加以下内容来测试一下：
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 中，将以下内容添加到栈：
public func peek() -> Element? {
storage.last
}
public var isEmpty: Bool {
peek() == nil
}
栈接口通常包括 peek 操作。 peek 的想法是在不改变其内容的情况下查看栈的顶部元素。
少即是多
我们可能想知道是否可以为栈采用 Swift collection协议。栈的目的是限制访问数据的方式数量Collection 之类的协议会违背这个目标，因为它会通过迭代器和下标公开所有元素。在这种情况下，少即是多！
我们可能希望获取现有数组并将其转换为堆栈以保证访问顺序。当然，可以循环遍历数组元素并推送每个元素。
但是，因为我们可以编写一个设置底层私有存储的初始化程序。将以下内容添加到我们的栈实现中：
public init(_ elements: [Element]) {
storage = elements
}
现在，将此示例添加到main 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
}
}
现在回到main 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>。栈对于搜索树和图的问题至关重要。想象一下在迷宫中寻找出路。每次你来到一个左、右或直的决策点时，我们都可以将所有可能的决策推到你的栈上。当我们遇到死胡同时，只需从堆栈中弹出并继续回溯，直到我们逃脱或遇到另一个死胡同。
关键点
• 栈是一种后进先出,后进先出的数据结构。
• 尽管非常简单，但栈是许多问题的关键数据结构。
• 栈仅有的两个基本操作是用于添加元素的push 方法和用于移除元素的pop 方法。
栈进阶
堆栈是一种简单的数据结构，具有惊人的大量应用程序。打开启动项目开始。在其中，我们会发现以下问题。
问题1：反转数组
创建一个函数，该函数使用栈以相反的顺序打印数组的内容。
问题2：平衡括号
检查平衡括号。给定一个字符串，检查是否有 ( 和 ) 字符，如果字符串中的括号是平衡的，则返回 true。例如：
// 1
h((e))llo(world)() // 平衡的括号
// 2
(hello world // 不平衡的括号
问题1解决方案
堆栈的主要用例之一是便于回溯。如果我们将一系列值压入栈，则顺序弹出堆栈将以相反的顺序为我们提供值。
func printInReverse<T>(_ array: [T]) {
var stack = Stack<T>()
for value in array {
stack.push(value)
}
while let value = stack.pop() {
print(value)
}
}
将节点压入堆栈的时间复杂度为 O(n)。弹出堆栈以打印值的时间复杂度也是 O(n)。总的来说，这个算法的时间复杂度是O(n)。
由于我们在函数内部分配容器（栈），因此还会产生 O(n) 空间复杂度成本。
注意：我们应该在生产代码中反转数组的方法是调用标准库提供的
reversed()方法。对于Array，这个方法在时间和空间上都是O(1)。这是因为它是惰性的，并且只会在原始集合中创建反向视图。如果我们遍历项目并打印出所有元素，则可以预见的是，它会在时间上使其成为 O(n)，而在空间中保持 O(1)。
问题2解决方案
要检查字符串中是否存在平衡括号，我们需要遍历字符串的每个字符。当我们遇到左括号时，我们可以将其压入栈。反之亦然，如果遇到右括号，则应弹出栈。
代码如下所示：
func checkParentheses(_ string: String) -> Bool {
var stack = Stack<Character>()
for character in string {
if character == "(" {
stack.push(character)
} else if character == ")" {
if stack.isEmpty {
return false
} else {
stack.pop()
}
}
}
return stack.isEmpty
}
该算法的时间复杂度为 O(n)，其中 n 是字符串中的字符数。由于使用了栈数据结构，该算法还会产生 O(n) 的空间复杂度成本。
| 上一章 | 目录 | 下一章 |
|---|
