声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
排队序列就是一个你只能在队伍的最后面加入新的值，从最前面取出旧的值的一串序列。这样的机制保证了最早进入序列的值，同时也会是最早出来的，就像我们平时排队办理业务一样，先到先服务！
为什么我们需要这样的机制呢？实际上，很多算法都会出现类似情况，在某一时刻你只想添加某些元素到一个临时列表里，然后过一会儿又将它们移除出去。这时候，你添加或者移除元素的顺序会影响整个算法。
队列可以提供先进先出的顺序（FIFO）。它每一次移除的元素，都是你最先放进去的元素。这里有一个非常类似的数据结构，堆栈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，我们可以继续移除队列的数据。如果队列变为空，移除方程返回结果为nil，在一些执行语句里面会返回错误信。
注意： 通常情况下队列并不是最好的选择。如果对于一个数组来说，元素的添加和移除过程不是很重要的话，这里我们建议使用堆栈Stack会是更好的选择，因为堆栈Stack更简单也更高效。
代码
在swift中，队列很容易创建。简单的说它就是对一个数组进行包装，让你能够对数组添加，移除，查看数据。
public struct Queue<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
队列算法运算效率良好，但大多数情况下并不是最优选择。
插入队列过程是一个O(1)运算过程，因为每一次在队列的最后一位插入新的数值消耗的时间是固定的，与队列当前的大小无关，这是队列算法最棒的地方。
你可能会好奇，为什么添加数值到数组里面是一个O(1)运算过程？因为在swift里，在一个数组的最末尾，swift都预留了一些空位备用。比如我们执行以下代码：
var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")
我们得到的数组应该是这样的：
["Ada", "Steve", "Tim", xxx, xxx , xxx]
这里的xxx是尚未填入数值的预留内存。添加新的数值会重写最近的一个xxx。
["Ada", "Steve", "Tim", "Grace", xxx , xxx]
这就相当于将一部分内存从一个地方复制到另一个地方，这是一个恒定运算过程。
当然，数组中的xxx个数是有限的。当最后一个xxx被使用，你还想继续添加数值，这个数组就需要重新调整大小，获取更多的空间。
调整大小包括获取新的内存，同时将现有的数据复制到新的数组里面。这是一个O(n)过程，所以这个过程有点慢。但是，因为这种情况偶尔发生，所以总体上来说，队列在添加新的数值到数组里的过程，所消耗的平均时间仍然接近O(1).
至于队列取出过程，就不太一样了。在取出数值的过程中，我们移除的是队列最前端的数值，而不是最末端。这个过程基本上一直是O(n)运算因为它需要将剩余的数据在内存上进行保留和移动。
在我们的例子中，取出第一个元素"Ada"其实是将"Steve"复制到"Ada"的位置，同时"Tim"被复制到原来"Steve"的位置，"Grace"被复制到运来"Tim"的位置:
取出前 ["Ada", "Steve", "Tim", "Grace", xxx , xxx]
/ / /
/ / /
/ / /
/ / /
取出后 ["Steve", "Tim", "Grace", xxx , xxx，xxx]
将所有数据在内存上进行移动一直是O(n)运算。所以在执行队列算法时候，插入数值的过程是简单高效的，但是取出的过程却有待提高。
更有效的队列算法
为了让队列算法更加有效，我们可以在预留内存位置上做文章，但是这次我们选择在队列的最前头进行内存预留。这里我们需要自己写代码去实现，因为swift本身的逻辑并没有支持我们提出来的想法。
想法如下：当我们需要从队列中取出元素的时候，我们不做数组元素的移动（慢），而是记住这个元素的位置，并且把它重写为xxx（快）。在取出"Ada"之后，数组内容如下：
[xxx, "Steve", "Tim", "Grace", xxx , xxx]
我们继续取出"Steve"，数组变成：
[xxx, xxx, "Tim", "Grace", xxx , xxx]
因为在队列算法中，最前端的预留内存永远不会被用到，为了防止内存浪费，我们可以偶尔对数组重新进行大小调整，即删除前端预留内存，将"Tim"等元素往前放：
["Tim", "Grace", xxx , xxx]
这个调整过程包含了内存移动，所以这里是一个O(n)运算。但是因为它只是偶尔发生，所以，总体来说，取出过程也变成了O(1)运算。
一下代码实现了上述所说的新队列算法：
public struct Queue<T>{
fileprivate var array = [T?]()
fileprivate var head = 0
public var isEmpty : Bool {
return count == 0
}
public var count: Int {
return array.count - head
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
guard head < array.count, let element = array[head] else { return nil }
array[head] = nil
head += 1
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
return element
}
public var front: T? {
if isEmpty {
return nil
} else {
return array[head]
}
}
}
因为我们需要将数组的元素重写为空，所以现在这里的数组储存对象类型为T?，而不是T。变量head是数组里面最前面的对象的索引。
对比原来的代码，我们对dequeuq()进行了修改。当我们取出数值的时候，我们首先将array[head]改为nil，同时将head的数值增加，保证其表示下一个元素的索引。
取出前：
["Ada", "Steve", "Tim", "Grace", xxx , xxx]
head
取出后：
[xxx, "Steve", "Tim", "Grace", xxx , xxx]
head
当然，如果我们从来不将前头的这些空点移除掉，而是不停的添加新的数值，移除前端的数值，那数组的大小将会不断变大，消耗的内存跟着增加。所以我们必须周期性的对数组进行调整。代码为:
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
在数组大小超过50的前提下，我们计算了空点在数组中所占的比例，当占比超过25%，我们就对数组进行一次调整，避免内存浪费。这里的50可以自己调整。
