Swift算法俱乐部：Swift队列数据结构（Queue)
Swift算法俱乐部：Swift队列数据结构（Queue)
翻译自raywenderlich网站iOS教程Swift Algorithm Club系列
准备开始
队列（Queue)是一个列表，您只能在后面插入新项目并从前面删除项目。 这可确保入队的第一个元素也是首先出队的元素。 先到先出
在许多算法中，我们希望在某个时间点将项目添加到临时列表中，然后在以后再次将它们从列表中拉出。 添加和删除这些项目的顺序非常重要。
队列提供先进先出或先入先出的顺序。 首先插入的元素也是第一个出来的元素（和堆栈(Stack)非常类似，是LIFO或后进先出。）
这是一个栗子
理解队列的最简单方法是看看它是如何使用的。
想象一下你有一个队列。 以下是你如何入选一个数字：
queue.enqueue(10)队列现在是10。 然后，继续将下一个号码添加到队列中：
queue.enqueue(3)队列现在是10,3。 继续添加：
queue.enqueue(57)队列现在是10,3,57。 我们可以将队列中的第一个元素从队列中拉出：
queue.dequeue()将返回10，因为这是插入的第一个数字。 队列现在将是3，57。 每个项目都向上移动一个地方。
queue.dequeue()这将返回3.下一个出列将返回57，依此类推。 如果队列为空，则出队将返回零。
实现队列
在本节中，将实现一个存储Int值的简单通用队列。
创建一个新的playground，添加如下代码：
public struct Queue {
}playground还包含LinkedList的代码（可以通过转到查看 Project Navigators Show Project Navigator并打开Sources LinkedList来看到这一点。
入队（Enqueue）
队列需要入队方法。 我们使用项目中包含的LinkedList实现来实现队列。 在花括号之间添加以下内容：
// 1
fileprivate var list = LinkedList<Int>()
// 2
public mutating func enqueue(_ element: Int) {
list.append(element)
}- 添加了一个
fileprivateLinkedList变量，用于将这些项目存储在队列中。 - 已经添加了一个方法来排列项目。 这个方法会改变底层的LinkedList，所以明确地指定了在方法前加上
mutating关键字。
出列（Dequeue)
队列也需要一个出队方法。
// 1
public mutating func dequeque() -> Int? {
// 2
guard !list.isEmpty, let element = list.first else { return nil}
list.remove(element)
return element.value
}- 添加一个返回队列中第一个项目的出队方法。 返回类型可以为空来处理队列为空。
- 使用
guard语句处理队列为空。 如果这个队列是空的，那么guard将会进入else块。
查看（Peek）
队列还需要一个peek方法，它在队列的开始处返回该项目而不删除它。
public func peek() -> Int? {
return list.first?.value
}IsEmpty
队列可以是空的。 添加一个isEmpty属性，该属性将返回基于LinkedList的值：
public var isEmpty: Bool {
return list.isEmpty
}打印队列
让我们试试新队列。 在队列实现下面，将以下内容写入playground中：
var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)定义队列后，尝试将队列打印到控制台：
print(queue)输出如下：
Queue(list: [10, 3, 57])这输出的样式不是很好。 要显示更可读的输出字符串，可以使队列采用CustomStringConvertable协议。 为此，请在Queue类的实现下方添加以下内容：
// 1
extension Queue: CustomStringConvertible {
// 2
public var description: String {
// 3
return list.description
}
}- 声明
Queue类的扩展，让它遵循CustomStringConvertible协议。 该协议期望使用字符串类型实现带名称描述的计算属性。 - 声明了
description属性。 这是一个计算属性，它是一个返回String的只读属性。 - 返回基于
LinkedList的描述。
现在控制台的输出编程如下样式：
[10, 3, 57]Swift通用队列实现
此时，我们已经实现了一个存储Int值的通用队列，并提供了在Queue类中查看，排队和出列项目的功能。
在本节中，我们使用泛型从队列中抽象出类型需求。
将Queue类的实现更新为以下内容：
// 1
public struct Queue<T> {
// 2
fileprivate var list = LinkedList<T>()
// 3
public mutating func enqueue(_ element: T) {
list.append(element)
}
// 4
public mutating func dequeque() -> T? {
guard !list.isEmpty, let element = list.first else { return nil}
list.remove(element)
return element.value
}
// 5
public func peek() -> T? {
return list.first?.value
}
public var isEmpty: Bool {
return list.isEmpty
}
}修正测试代码如下：
var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
print(queue)还可以尝试使用不同类型的Queue：
var queue2 = Queue<String>()
queue2.enqueue("mad")
queue2.enqueue("lad")
if let first = queue2.dequeque() {
print(first)
}
print(queue2)以上是本人在raywenderlich学习时为方便自己，用翻译工具翻译之后做的一个记录。
本系列其他文章：