队列(Queue)是一种先入先出(First in First Out，简称FIFO)的数据结构。想象一下，在排队买饭的时候，站在队列最前边的人买完饭之后出去了，然后排在他后面的人接着上前买饭，直到最后一个人也买完饭走了，这是队列最形象的一个例子(当然，这里不考虑插队这种败人品的bug)。我们来看一下队列结构示意图：
根据队列的特点，通常情况下，我们需要实现下面这些属性和方法：
- enqueue()：将元素添加到队列的末尾；
- dequeue()：删除队列中第一个元素，并且将其返回；
- peek()：返回队列中第一个元素，但是不会将其从队列中删除；
- clear()：清空队列中的元素；
- count：返回队列中元素的个数；
- isEmpty()：判断队列是否为空，如果是，则返回true，否则返回false；
- isFull()：判断队列是否已满，如果是，则返回true，否则返回false。
- capacity：用来查看或者设置队列容量的属性。
补充一点，数组的count属性和capacity属性是有区别的。count属性用来返回数组中元素的个数，而capacity属性是用来返回数组的存储空间的。
1、队列的应用
队列的应用场景也非常的多，比如说你需要按照接收顺序来处理相关的数据。举一个典型的例子，为了解决计算机和打印机之间速度不匹配的问题，通常需要设置一个打印数据的缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据，此时缓冲区的逻辑实现就要用到队列。
2、队列的实现
和上一篇文章Stack的实现一样，在实现队列时，我们依然要用到数组和泛型语法。数组用来存储数据元素，而泛型语法在具体的实现时提供必要的灵活性。接下来，我们要依次实现enqueue()、dequeue()、peek()、isEmpty()、isFull()、clear()方法及count属性：
// 定义一个队列结构
public struct Queue<T> {
// 数组用来存储数据元素
fileprivate var data = [T]()
// 构造方法，用于构建一个空的队列
public init() {}
// 构造方法，用于从序列中创建队列
public init<S: Sequence>(_ elements: S) where
S.Iterator.Element == T {
data.append(contentsOf: elements)
}
// 将类型为T的数据元素添加到队列的末尾
public mutating func enqueue(element: T) {
data.append(element)
}
// 移除并返回队列中第一个元素
// 如果队列不为空，则返回队列中第一个类型为T的元素；否则，返回nil。
public mutating func dequeue() -> T? {
return data.removeFirst()
}
// 返回队列中的第一个元素，但是这个元素不会从队列中删除
// 如果队列不为空，则返回队列中第一个类型为T的元素；否则，返回nil。
public func peek() -> T? {
return data.first
}
// 清空队列中的数据元素
public mutating func clear() {
data.removeAll()
}
// 返回队列中数据元素的个数
public var count: Int {
return data.count
}
// 返回或者设置队列的存储空间
public var capacity: Int {
get {
return data.capacity
}
set {
data.reserveCapacity(newValue)
}
}
// 检查队列是否已满
// 如果队列已满，则返回true；否则，返回false
public func isFull() -> Bool {
return count == data.capacity
}
// 检查队列是否为空
// 如果队列为空，则返回true；否则，返回false
public func isEmpty() -> Bool {
return data.isEmpty
}
}
上面的代码定义了一个基本的队列，下面来演示一下将数据元素添加到队列，以及从队列中删除数据元素的基本操作：
// 声明一个存储String类型数据的队列
var queue = Queue<String>()
// 将风尘四侠添加到队列中
queue.enqueue(element: "LeBron James")
queue.enqueue(element: "Carmelo Anthony")
queue.enqueue(element: "Dwyane Wade")
queue.enqueue(element: "Chris Paul")
// 从队列中取出LeBron James，并将其删除
let x = queue.dequeue()
// 从队列中取出Carmelo Anthony，但是不要从队列中删除
let y = queue.peek()
// 删除队列中的第一个元素(此时返回的应该是Carmelo Anthony)
let z = queue.dequeue()
关于上面队列的代码，其功能还是相当简单的，我们只是将一个数组包装成了一个队列，但是距离真正的队列还有一段距离。另外需要强调一点，此时队列的存储容量是由数组自己动态调整来实现的，我们并没有对其进行干预。
3、通过协议来扩展队列的功能
要想让在上面定义的Queue类型看起来更像一个队列，我们还需要利用一些便利协议来扩展其功能。首先，我们先给它扩展CustomStringConvertible协议和CustomDebugStringConvertible协议，这会让我们在打印队列时，控制台会输出简介漂亮的格式：
// 让打印队列时输出简介的格式
extension Queue: CustomStringConvertible, CustomDebugStringConvertible {
// 控制打印队列时的文本输出
public var description: String {
return data.description
}
// 控制打印队列时的文本输出，主要用于调试
public var debugDescription: String {
return data.debugDescription
}
}
如果我们没有实现上面的代码，在打印队列时，控制台会显示下面的字符串：
Queue<String>(data: ["LeBron James", "Carmelo Anthony", "Dwyane Wade", "Chris Paul"])
但是，当我们实现了上面的扩展，再打印队列时，控制台会显示下面这样的字符串：
["LeBron James", "Carmelo Anthony", "Dwyane Wade", "Chris Paul"]
从对比中我们可以看到，实现上面的扩展之后，控制台打印出来的字符串看起来更加的友好。
接着，我们要让队列可以使用字面语法(也就是快速声明语法)来初始化一个实例。为此，必须让队列遵守ExpressibleByArrayLiteral协议。要实现这个功能，还要给Queue增加一个新的构造器，该构造器可以初始化出一个序列，让序列中包含所有初始化的元素：
/// 构造方法，用于从序列中创建队列(添加到Queue的类型定义中)
public init<S: Sequence>(_ elements: S) where
S.Iterator.Element == T {
data.append(contentsOf: elements)
}
// 让队列支持通过快速声明来创建实例
extension Queue: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: T...) {
self.init(elements)
}
}
// 使用快速语法声明一个队列
var myQueue : Queue = [5, 8, 1, 6, 9, 11]
print(myQueue)
除了按照字面意思快速声明一个队列之外，我们可能还希望像集合类型一样，可以在队列中使用for...in循环语句。为此，必须让我们定义的Queue遵守Sequence协议，这样它就可以返回一个懒加载的序列：
// 扩展队列的for...in循环功能
extension Queue: Sequence {
// 从序列中返回一个迭代器
public func generate() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements: data.lazy))
}
}
写完上面的代码之后，Playground可能会报Type 'Queue<T>' does not conform to protocol 'Sequence'的错误，主要原因是我们在上面用到了IndexingIterator。IndexingIterator定义在Collection协议中，并且是继承自_IndexableBase协议。而_IndexableBase协议在Swift 4中将会被移除，所以我们不用鸟它：
为了实现for...in循环的功能，同时解决编译器报错，我们需要遵守Collection协议。除此之外，集合类型中另外一个非常有用的协议是MutableCollection，它允许你使用下标来检索和设置队列中的元素。通过下标的使用，我们可以指定队列中元素的索引。不过，在使用索引之前，我们还需要对它的合法性进行验证，为此需要实现一个checkIndex()方法：
// 现在Queue的定义中添加一个方法，用于检查索引的合法性
fileprivate func checkIndex(index: Int) {
if index < 0 || index > count {
fatalError("Index out of range")
}
}
/** 接下来是对Queue进行扩展 **/
// 根据索引返回指定的位置
extension Queue: Collection {
// i的值必须比endIndex小
public func index(after i: Int) -> Int {
// 返回i后面的索引
return data.index(after: i)
}
}
// 实现下标功能
extension Queue: MutableCollection {
// 队列的起始索引
public var startIndex: Int {
return 0
}
// 队列末尾索引
public var endIndex: Int {
return count - 1
}
// 获取或者设置下标
public subscript(index: Int) -> T {
get {
checkIndex(index: index)
return data[index]
}
set {
checkIndex(index: index)
data[index] = newValue
}
}
}
实现完上面的代码之后，我们不仅可以使用for...in循环来遍历队列，还可以获取队列中指定位置的索引：
// 遍历队列中的元素
for el in myQueue {
print(el)
}
// 获取队列中指定下标后面的索引
myQueue.index(after: 0)
// 获取队列中第一个元素的索引
myQueue.startIndex
// 获取队列中最后一个元素的索引
myQueue.endIndex
最后，为了便于阅读和理解，我们还是按照习惯，将所有的代码整理到一起：
// 定义一个队列结构
public struct Queue<T> {
// 数组用来存储数据元素
fileprivate var data = [T]()
// 构造方法，用于构建一个空的队列
public init() {}
// 构造方法，用于从序列中创建队列
public init<S: Sequence>(_ elements: S) where
S.Iterator.Element == T {
data.append(contentsOf: elements)
}
// 将类型为T的数据元素添加到队列的末尾
public mutating func enqueue(element: T) {
data.append(element)
}
// 移除并返回队列中第一个元素
// 如果队列不为空，则返回队列中第一个类型为T的元素；否则，返回nil。
public mutating func dequeue() -> T? {
return data.removeFirst()
}
// 返回队列中的第一个元素，但是这个元素不会从队列中删除
// 如果队列不为空，则返回队列中第一个类型为T的元素；否则，返回nil。
public func peek() -> T? {
return data.first
}
// 清空队列中的数据元素
public mutating func clear() {
data.removeAll()
}
// 返回队列中数据元素的个数
public var count: Int {
return data.count
}
// 返回或者设置队列的存储空间
public var capacity: Int {
get {
return data.capacity
}
set {
data.reserveCapacity(newValue)
}
}
// 检查队列是否已满
// 如果队列已满，则返回true；否则，返回false
public func isFull() -> Bool {
return count == data.capacity
}
// 检查队列是否为空
// 如果队列为空，则返回true；否则，返回false
public func isEmpty() -> Bool {
return data.isEmpty
}
// 确保队列中的索引是合法的
fileprivate func checkIndex(index: Int) {
if index < 0 || index > count {
fatalError("Index out of range")
}
}
}
/**************** 队列的基本操作 ****************/
// 声明一个存储String类型数据的队列
var queue = Queue<String>()
// 将风尘四侠添加到队列中
queue.enqueue(element: "LeBron James")
queue.enqueue(element: "Carmelo Anthony")
queue.enqueue(element: "Dwyane Wade")
queue.enqueue(element: "Chris Paul")
// 打印队列
print(queue)
// 从队列中取出LeBron James，并将其删除
let x = queue.dequeue()
// 从队列中取出Carmelo Anthony，但是不要从队列中删除
let y = queue.peek()
// 删除队列中的第一个元素(此时返回的应该是Carmelo Anthony)
let z = queue.dequeue()
/**************** 利用协议来扩展队列的功能 ****************/
// 让打印队列时输出简介的格式
extension Queue: CustomStringConvertible, CustomDebugStringConvertible {
// 控制打印队列时的文本输出
public var description: String {
return data.description
}
// 控制打印队列时的文本输出，主要用于调试
public var debugDescription: String {
return data.debugDescription
}
}
// 让队列支持通过快速声明来创建实例
extension Queue: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: T...) {
self.init(elements)
}
}
// 使用快速语法声明一个队列
var myQueue : Queue = [5, 8, 1, 6, 9, 11]
print(myQueue)
// 扩展队列的for...in循环功能
extension Queue: Sequence {
// 从序列中返回一个迭代器
public func generate() -> AnyIterator<T> {
return AnyIterator(IndexingIterator(_elements: data.lazy))
}
}
// 根据索引返回指定的位置
extension Queue: Collection {
// i的值必须比endIndex小
public func index(after i: Int) -> Int {
// 返回i后面的索引
return data.index(after: i)
}
}
// 实现下标功能
extension Queue: MutableCollection {
// 队列的起始索引
public var startIndex: Int {
return 0
}
// 队列末尾索引
public var endIndex: Int {
return count - 1
}
// 获取或者设置下标
public subscript(index: Int) -> T {
get {
checkIndex(index: index)
return data[index]
}
set {
checkIndex(index: index)
data[index] = newValue
}
}
}
// 编译器有bug，遍历显示有错，但是仍然可以成功遍历
for el in myQueue {
print(el)
}
// 获取队列中指定下标后面的索引
myQueue.index(after: 0)
// 获取队列中第一个元素的索引
myQueue.startIndex
// 获取队列中最后一个元素的索引
myQueue.endIndex
好了，Swift队列数据结构的基本实现就先整理到这里，在下一篇中，我们将会继续学习环形缓冲区的相关知识。
