数据结构：堆栈
原文链接： Swift Algorithm Club: Swift Stack Data Structure
翻译： coderJoey
通过本教程，你将学习怎样用swift实现堆栈数据结构。作为基础数据结构，堆栈能解决很多程序中的问题。
开始吧
堆栈很像数组，但是其功能较数组而言有所限制。你只能通过push（压人）来添加新元素到堆栈的顶部，也只能通过pop来移除堆栈顶部的元素，如果不进行移除操作的话，你也只能查看到堆栈最上面的元素。
这种数据结构有什么用呢？在很多算法中，例如某个时刻你想添加一些新的对象到一个临时链中，然后不就之后你需要删除掉这些对象，添加和删除这些对象的顺序有时候是很重要的。
堆栈进出栈顺序是LIFO（ last-in first-out order：后进先出），也就是最后进栈的元素最先被移除。（这非常像数据结构队列（FIFO:先进先出））
我们将用RW的书来解析堆栈的工作原理
接下来，你将用数组实现堆栈的内部存储操作。虽然这不是很高效的做法，但能让你理解堆栈结构的实现方式。
堆栈的相关操作
堆栈的功能范围相对有限。 以堆叠的书籍为例，堆栈相应的功能有：
Push
当你要添加元素到堆栈中时，你应该将元素push到堆栈的最上面。就像放一本书到一叠书上面。
Peek
按照设计规则，堆栈不允许查看除了堆栈的顶部元素的其它元素。 peek方法只允许你查看堆栈顶部的内容。
不能看到底下的书籍
Pop
就像下图从一叠书中拿掉最上面的书本一样，你只能通过pop移除掉堆栈中最上面的元素。
Swift 堆栈的实现
用Xcode创建一个新的playground！
开始，先将下面的代码写到你的playground中：
struct Stack {
fileprivate var array: [String] = []
}
这里定义了一个拥有一个array属性的堆栈，你将通过这个array属性来实现 push、 pop、 和 peek这些功能方法
Push
将对象压入到堆栈中是比较简单的。把下面的方法加到stack实现中：
// 1
mutating func push(_ element: String) {
// 2
array.append(element)
}
-
push方法只有一个参数，即需要添加到栈顶的元素。
-
注意这里新元素是添加到数组的末尾而不是数组的开头。如果添加到数组的开始位置，则是代价相当大的O(n)操作，因为这需要数组里面所有的元素在内存中都进行移位操作。添加在数组尾部的时间复杂度是** O(1)**，不管数组的大小是多少，它所需要的时间是固定的。
Pop
元素出栈也是很简单的。将下面的方法放到push方法下面：
// 1
mutating func pop() -> String? {
// 2
return array.popLast()
}
-
pop方法的返回值是可选类型String，返回可选类型是为了处理堆栈为空的情况。如果你对一个内容为空的堆栈进行pop操作的话，返回值将是nil。
-
Swift 数组删除最后一个元素的方法popLast。
Peek
查看堆栈的元素实质就是查看栈顶的元素。这也是相对比较容易实现的。Swift 数组有一个last属性专门来访问数组的最后一个元素。
func peek() -> String? {
return array.last
}
peek方法和pop方法类似，最大的区别是pop方法前面有关键字mutating。这是因为peek方法不会改变数组的内容，所以没有必要加关键字mutating了。
试一试
到现在为止，你的Swift堆栈已经可以进行一些测试了。将下面的代码加到playground的底部：
// 1
var rwBookStack = Stack()
// 2
rwBookStack.push("3D Games by Tutorials")
// 3
rwBookStack.peek()
// 4
rwBookStack.pop()
// 5
rwBookStack.pop()
在playground的右面板上，你能看到每一行的输出结果：
-
初始化一个堆栈对象并赋值给变量rwBookStack。这里使用var将其定义为变量而不是常量，是因为等会你会改变堆栈的内容。
-
添加一个字符串到堆栈中。
-
查看堆栈内容，也就是最后入栈的字符串“3D Games by Tutorials”。
-
移除栈顶的内容，也就是最后入栈的字符串“3D Games by Tutorials”。
-
由于你已经移除了堆栈中的所有内容，所以面板显示为nil。
CustomStringConvertible
现在打印堆栈对象的话，很难看出堆栈是如何工作的。 幸运的是，Swift有一个名为CustomStringConvertible的内置协议，它允许你自定义打印内容。 将下面的代码写到Stack实现的下面（不是里面）：
// 1
extension Stack: CustomStringConvertible {
// 2
var description: String {
// 3
let topDivider = "---Stack---\n"
let bottomDivider = "\n-----------\n"
// 4
let stackElements = array.reversed().joined(separator: "\n")
// 5
return topDivider + stackElements + bottomDivider
}
}
上面代码做了什么：
-
实现一个Stack的扩展，并遵守CustomStringConvertible协议。
-
根据CustomStringConvertible协议实现description属性。
-
添加数据头部和尾部的打印内容。
-
你需要将数组里面的元素按照堆栈的样式打印出来。 由于你是将元素添加到数组的尾部，所以首先要做的是反转数组。然后用joined(separator:) 方法来拼接数组里面的元素，元素之间用separator隔开。例如数组["3D Games by Tutorials", "tvOS Apprentice"] 拼接之后就变成了** "3D Games by Tutorials\ntvOS Apprentice" **。
-
最后将topDivider 、 stackElements 和 bottomDivider像三明治一样的叠起来，作为堆栈的描述（打印）内容。
删掉之前的测试代码并添加下面的代码到playground底部：
var rwBookStack = Stack()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)
在playground下面的控制台将输出：
---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------
泛型
目前为止，你的堆栈只能存储strings。如果要创建一个堆栈来存储整数，则必须实现一个面向整数的全新的堆栈。幸运的是Swift可以通过泛型来抽象我们需要储存的数据。将你的Stack改成下面的样式：
struct Stack<Element> {
// ...
}
代码中的尖括号将这个结构体声明为泛型，允许堆栈传入Swift中的所有类型。 下一步，查找并将实例中的“String”类型替换为“Element”。现在你的Stack应该是这样：
struct Stack<Element> {
fileprivate var array: [Element] = []
mutating func push(_ element: Element) {
array.append(element)
}
mutating func pop() -> Element? {
return array.popLast()
}
func peek() -> Element? {
return array.last
}
}
最后，你还需要修改description属性的内容。只需要改一个地方，像下面这样：
// 修改前
let stackElements = array.reversed().joined(separator: "\n")
// 修改后
let stackElements = array.map { "\($0)" }.reversed().joined(separator: "\n")
这里主要是将数组元素在拼接前转换成String类型。由于你不确定数组元素的类型，所以这个转换时必要的。
最后你要将创建的堆栈对象指定为String类型。
var rwBookStack = Stack<String>()
现在你的堆栈能够指定为String、Int和其他任何类型了，甚至你自定义的类型像Person也是可以的！
收尾
这里还有两个属性是堆栈常常用到的：判断堆栈是否为空和堆栈当前的元素个数。
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
何去何从
希望你对制作堆栈的这套教程感到满意！
上面的代码可点击这里下载。你还可以去往这里查看最初的实现方式以及进行堆栈的进一步的讨论。
网友评论