原文链接： Swift Algorithm Club: Swift Queue Data Structure
翻译： coderJoey
通过本教程，你将学习怎样用Swift3实现队列数据结构。队列是一种非常流行的数据结构，而且用Swift实现也相当简单。
开始吧
队列 很像排队，先到的排在前面后来的排在队伍的后面。这能保证第一个入列的元素将第一个出列。
这种数据结构有什么用呢？在很多算法中，例如某个时刻你想添加一些新的对象到一个临时列表中，然后不就之后你需要删除掉这些对象，添加和删除这些对象的顺序有时候是很重要的。
队列的顺序是FIFO（ first-in first-out order：先进先出），也就是最先入列的元素最先被移除。（这非常像数据结构堆栈（LIFO:后进先出））
例子
理解队列最好的方式就是看它是如何工作的。
假设你现在有一个队列，下面是如何添加一个数字：
queue.enqueue(10)
队列现在变成了[10]，然后你再添加一个数字：
queue.enqueue(3)
队列变成了[10,3]，然后你又添加一个数字：
queue.enqueue(57)
队列变成了[10,3,57]，你现在将队列的最前面的元素删掉：
queue.dequeue()
这个方法将返回第一次插入的数字10，队列变成了[3,57]。每个元素都将向前移一位。
queue.dequeue()
这个方法将返回3，下一次dequeue将返回57。如果这个队列是空的，操作出列方法将返回nil。
实现队列
在本节中，你将实现一个存储Int类型的简单通用队列。
首先先下载queue starter project。playground项目中包含了一个空的Queue：
public struct Queue {
}
playground中也包含了一个链表类 LinkedList，你可以在View\Project Navigators\Show Project Navigator中打开Sources\LinkedList（或者用组合键command+1）
想知道链表是如何工作的？点击这里查看译文教程，或者点击Swift linked list 查看原文。
入列
队列需要一个enqueue函数进行入列操作。你将使用启动项目中包含的链表来实现队列。 在花括号之间添加以下内容：
// 1
fileprivate var list = LinkedList()
// 2
public mutating func enqueue(_ element: Int) {
list.append(element)
}
上面代码做了什么：
添加了私有的变量LinkedList，用来存储队列的元素。
添加了一个入列函数。该函数会使LinkedList内容发生改变，所以你需要在方法前添加mutating关键字。
出列
队列也需要一个dequeue函数进行出列操作。
// 1
public mutating func dequeue() -> Int? {
// 2
guard !list.isEmpty, let element = list.first else { return nil }
list.remove(element)
return element.value
}
上面代码做了什么：
添加一个返回值为队列第一个元素的dequeue方法，返回值类型nullable是为了处理队列为空的情况。该函数会使LinkedList内容发生改变，所以你需要在方法前添加mutating关键字。
用guard语句来处理队列为空的情况。如果队列为空。guard将执行else语句块代码。
查看
队列也需要一个peek函数来查看队列的第一个元素。与dequeue不同的是你不能将这个元素从队列中移除掉。
public func peek() -> Int? {
return list.first?.value
}
是否为空
队列是可以为空的。你需要在 LinkedList下边添加一个判断队列是否为空的isEmpty属性。
public var isEmpty: Bool {
return list.isEmpty
}
打印队列
现在我们使用下这个队列。在Queue实现下面，我们添加如下代码：
var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
定义队列后,我们试着将链表的内容打印到控制台:
print(queue)
你可以使用组合键 Command-Shift-Y唤起控制台。然而你看到的打印结果是：
Queue
这显然没什么用。要使打印的字符串更具可读性，你需要让LinkedList遵守CustomStringConvertable 协议。我们将下面的代码添加到Queue 类的下面。
// 1
extension Queue: CustomStringConvertible {
// 2
public var description: String {
// 3
return list.description
}
}
上面代码做了什么：
你声明了一个 Queue 类的扩展，而且遵守了CustomStringConvertable 协议。这个协议希望你实现String类型的description，这里的description为计算型属性（computed property）。
定义description属性，它的返回类型是String，而且是只读的。
将LinkedList的描述属性作为返回值。
现在打印Queue的内容，你将看到不错的结果：
"[10, 3, 57]"
泛型实现
到目前为止，你已经实现了一个存储Int值的通用队列， 并提供了在队列类中查看，入列和出列的功能函数。
在本节中，我们将使用泛型来实现抽象类型的队列。
如下更新Queue类：
// 1
public struct Queue<T> {
// 2
fileprivate var list = LinkedList<T>()
public var isEmpty: Bool {
return list.isEmpty
}
// 3
public mutating func enqueue(_ element: T) {
list.append(element)
}
// 4
public mutating func dequeue() -> 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
}
}
代码解析：
- 将Queue类的声明更改为泛型T。
- 你的目的是要让Queue类存储任何类型，所以要将LinkedList的类型定义为泛型T。
- 将enqueue类定义的类型更改为泛型T。
- 将dequeue类定义的类型更改为泛型T。
- 将peek类定义的类型更改为泛型T。
修改测试代码：
var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
当然你还可以测试其他不同的类型：
var queue2 = Queue<String>()
queue2.enqueue("mad")
queue2.enqueue("lad")
if let first = queue2.dequeue() {
print(first)
}
print(queue2)
何去何从
希望你对制作队列的这套教程感到满意！
上面的代码可点击 这里下载。你还可以去往 这里 查看其他的实现方式以及进行队列的进一步的讨论。
