队列像一个列表，您只能在最后插入新元素，并从最前面删除元素。 这确保了您第一个入队的元素也是您出队的第一个元素。 先来后到！
为什么需要这个？ 好吧，在许多算法中，您希望在某个时间点将对象添加到临时列表，然后再次将其从此列表中删除。 通常，添加和删除这些对象的顺序很重要。
队列是先进先出的顺序。 您首先插入的元素也是第一个出队列的元素。 这只是公平！ （一个非常相似的数据结构，栈，是后入先出。）
例如，让我们向队列添加一个数字：
queue.enqueue(10)
队列现在是[10]。 将下一个数字添加到队列：
queue.enqueue(3)
队列现在是[10，3]。 再添加一个数字：
queue.enqueue(57)
队列现在是[10，3，57]。 让我们让队列第一个元素出列：
queue.dequeue()
这里返回10，因为这是我们插入的第一个数字。 队列现在是[3，57]。 每个元素的索引都向前移动了1。
queue.dequeue()
这返回3，下一个出列返回57，依此类推。 如果队列为空，则dequeue返回nil，或者在一些实现中提示出错误信息。
注意: 队列并不总是最好的选择。 如果项目从列表中添加和删除的顺序不重要，您可以使用栈而不是队列。 栈更简单，更快。
代码
这是一个在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 func peek() -> T? {
return array.first
}
}
这个队列实现了功能，但它不是最佳的。
入队是一个O（1）操作，因为添加到数组的末尾总是需要相同的时间量，而不管数组的大小。 这是最好的。
你可能想知道为什么将数据附加到数组是O（1），或者说是一个常量时间的操作。 这是因为Swift中的数组在结尾总是有一些空间。 如果我们做如下操作：
var queue = Queue<String()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")
那么数组看起来像这样：
[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]
其中xxx是保留但尚未填充的内存。 向阵列中添加新元素将覆盖下一个未使用的内存：
[ "Ada", "Steve", "Tim", "Grace", 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数组不支持这种功能。
思路是这样的：当我们将一个元素出列时，我们不会移动数组的其他元素，而是将出列的位置标记为空。在“Ada”出列之后，数组是：
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
在“Steve”出列之后，数组是：
[ xxx, xxx, "Tim", "Grace", xxx, xxx ]
这些空的内存永远不会被使用，是对空间的浪费。每隔一段时间，你可以将剩余的元素向前移动：
[ "Tim", "Grace", xxx, xxx, xxx, xxx ]
这样在内存中移动元素的过程是O（n）操作。但它很少发生，所以平均时间是O（n）。
新的队列代码：
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 func peek() ->T? {
if isEmpty {
return nil
} else {
return array[head]
}
}
}
现在数组中存储的是可选类型T?，而不是T，因为我们要标记数组元素为空。head变量是空元素的索引。
大多数的新代码在dequeue()中。一个元素出列时，首先将array[head]的值设为nil，达到从数组中删除改元素的目的。然后我们让head+1，使下一个元素会在队列的最前面。
出列前：
[ "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
}
如果空白的长度站到整个数组的25%以上，我们就把空白的部分去掉。但是如果数组元素数量不多，我们也不想一直修剪它。所以至少有50个元素才会去修剪它。
注意: 这只是一个例子，你需要根据你应用的实际情况来决定什么情况下修剪数组。
在playground里测试，代码：
var q = Queue<String>()
q.array // [] empty array
q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count // 3
q.dequeue() // "Ada"
q.array // [nil, {Some "Steve"}, {Some "Tim"}]
q.count // 2
q.dequeue() // "Steve"
q.array // [nil, nil, {Some "Tim"}]
q.count // 1
q.enqueue("Grace")
q.array // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count // 2
测试修剪数组，把这行代码：
if array.count > 50 && percentage > 0.25 {
替换为这行代码：
if head > 2 {
你再出队一个对象，数组就是这样的：
q.dequeue() // "Tim"
q.array // [{Some "Grace"}]
q.count // 1
队列前面的nil对象被删除，不再浪费空间。 新版本的队列比第一个更复杂，但是出队也是一个O（1）操作，因为我们对于如何使用数组有了更多的理解。
作者：Matthijs Hollemans -- Swift算法俱乐部
原文链接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Queue
网友评论