Swift算法俱乐部：Swift栈(Stack)数据结构

翻译自raywenderlich网站iOS教程Swift Algorithm Club系列

堆栈(Stack)就像数组，但功能有限。

堆栈提供LIFO或后进先出。 最后推进的元素是即将被推出的第一个元素。 （非常类似的数据结构，队列是FIFO，或先进先出。）

开始了解堆栈

我们用下面这堆书来模拟堆栈的工作方式

堆栈操作

push:想添加一个元素到堆栈上时，你可以推入堆栈。 你可以把它看作是在书堆上添加一本书。

peek:根据设计，堆栈不允许您检查其内容，但堆栈的顶层元素除外。 peek方法允许您检查堆栈顶部的内容。

pop:当你想删除堆栈中的元素时，你从堆栈中弹出一个元素。 你可能会认为它是从书堆中拿走顶部的书籍。

Swift栈实现

打开一个playground开始实施Swift堆栈！

首先，将以下内容写入playground：

struct Stack {
    fileprivate var array: [String] = []
}

在这里已经声明了一个具有数组属性的Stack。 下面我们将与数组交互以实现push，pop和peek方法。

Push

将对象推入堆栈相对比较简单。 在Stack中添加以下方法：

// 1
mutating func push(_ element: String) {
    // 2
    array.append(element)
}

1. push方法接受一个参数，并将元素添加到栈顶。
2. 注意，push操作会将新元素放在数组的末尾，而不是开始。 在数组的开头插入代价很昂贵，因为它需要所有现有的数组元素在内存中移位。 最后加上O（1）; 无论数组大小如何，它总是需要相同的时间。

Pop

弹出堆栈也很简单。 只需在push方法下，在Stack中添加以下方法：

// 1
mutating func pop() -> String? {
    // 2
    return array.popLast()
}

1. pop方法返回一个可选的String。 返回类型是可选的，以处理堆栈空置的情况。 如果你尝试弹出一个空的堆栈，那么你会得到一个nil。
2. Swift数组有一个方便的方法(popLast)来删除它的最后一个元素 。

Peek

查看堆栈只能查看堆栈的顶层元素。 Swift数组有一个最后一个属性。

func peek() -> String? {
    return array.last
}

peek方法与pop方法非常相似。 除了名称之外，唯一的区别是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的右侧面板上，可以看到每行的结果：

1. 声明了一个rwBookStack属性，并用Stack来初始化它。 这需要是一个变量而不是一个常量，因为下面我们需要改变栈的内容。
2. 在堆栈中PUSH了一个字符串。
3. PEEK堆栈会看到“3D Games by Tutorials”，这是你PUSH堆栈的最后一个元素。
4. POP堆栈“3D Games by Tutorials”，这是推入堆栈的最后一个元素。
5. 当POP堆栈中的所有内容时，显示nil。

自定义字符串转换

目前，很难直观地看到堆栈中的元素。 但是Swift有一个名为CustomStringConvertible的内置协议，允许您定义如何以字符串表示对象。 在Stack实现下面写下以下内容（不是在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
    }
}

1. 要利用CustomStringConvertible，您可以创建一个扩展并采用CustomStringConvertible协议。
2. 实现description属性是CustomStringConvertible协议必须的。
3. 为了打印的美观加上----和换行
4. 由于您已将元素附加到数组后面，因此您需要先倒转数组。之后用joined(separator: "\n")方法简单地使用数组中的每个元素，并在每个元素之间使用分隔符将它们连接在一起。例如，数组[“3D Games by Tutorials”，“tvOS Apprentice”]将在加入后成为"3D Games by Tutorials\n tvOS Apprentice"。
5. 最后，将夹层元素夹在两个分隔符之间，并将结果作为堆栈的description返回

删除之前的测试代码并在playground底部写下以下内容：

var rwBookStack = Stack()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)

控制台显示堆栈的正确表示形式：

-----Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
----------

泛型

目前，Stack只能存储字符串。 如果想创建一个堆栈来存储整数，我们需要实现一个全新的堆栈。 幸运的是，Swift提供了更便捷的方法，首先，将Stack的声明更新为以下内容：

struct Stack<Element> {
  // ...
}

<>将结构声明为泛型，允许堆栈将其用于所有类型。 接下来，查找并更新您写下“String”的所有实例，并将其替换为“Element”。 Stack应该是这样的：

struct Stack<Element> {
    fileprivate var array: [Element] = []

    // 1
    mutating func push(_ element: Element) {
        // 2
        array.append(element)
    }

    // 1
    mutating func pop() -> Element? {
        // 2
        return array.popLast()
    }

    func peek() -> Element? {
        return array.last
    }
}

最后，你必须更新description属性。 只有一个改变。 更新以下行以匹配以下内容：

// previous
let stackElements = array.reversed().joined(separator: "\n")

// now
let stackElements = array.map { "\($0)" }.reversed().joined(separator: "\n")

上面是将它们连接在一起之前将数组中的元素转换为String。 由于您的堆栈现在是通用的，因此您无法确定要加入的值是字符串。

最后，找到初始化你的堆栈的行：

var rwBookStack = Stack<String>()

现在，Stack可以专用于所有类型，无论是String，Int，还是您创建的自定义类型，例如Person对象！

完成

还有两个其他属性通常与堆栈一起出现。 通常情况下，您想知道堆栈是否为空，以及当前堆栈中有多少元素。 在堆栈中添加以下计算属性：

var isEmpty: Bool {
  return array.isEmpty
}

var count: Int {
  return array.count
}

到此这个练习已经结束。

以上是本人在raywenderlich学习时为方便自己，用谷歌翻译做的一个记录。

本系列其他文章：

Swift算法俱乐部：Swift队列数据结构（Queue)