本文是对 翻译的一篇文章。
是 网站出品的用 Swift 实现算法和数据结构的开源项目，目前在 GitHub 上有 18000+ ⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是 iOSer 学习算法和数据结构不错的资源。?是我对 Swift Algorithm Club，边学习边翻译的项目。
由于能力有限，如发现错误或翻译不妥，请指正，欢迎 pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习?。当然也欢迎加⭐️，?????。
本文的翻译原文和代码可以查看?
双端队列(Deque)
出于某种原因，双端队列也被称为“deck”。
常规元素在后面添加（入队），从前面删除（出队）。 除了这些，双端队列还可以在后面出队，从前面入队，并且两端都可查看。
Swift中双端队列的一个非常基本的实现：
public struct Deque{ private 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 enqueueFront(_ element: T) { array.insert(element, atIndex: 0) } public mutating func dequeue() -> T? { if isEmpty { return nil } else { return array.removeFirst() } } public mutating func dequeueBack() -> T? { if isEmpty { return nil } else { return array.removeLast() } } public func peekFront() -> T? { return array.first } public func peekBack() -> T? { return array.last }}复制代码
这个实现的内部使用数组。 入队和出列只是在数组的前面或后面，添加或删除元素。
在 playground 中使用：
var deque = Deque ()deque.enqueue(1)deque.enqueue(2)deque.enqueue(3)deque.enqueue(4)deque.dequeue() // 1deque.dequeueBack() // 4deque.enqueueFront(5)deque.dequeue() // 5复制代码
Deque的这种实现很简单但效率不高。几个操作是 O(n)，特别是enqueueFront()和dequeue()。这个实现只是为了说明双端队列的作用原理。
更高效的版本
dequeue()和enqueueFront()的时间复杂度是O(n)，原因是它们在数组的前面（开始）工作。如果删除数组前面的元素，那么所有剩余的元素都需要在内存中移位。
假设双端队列的数组包含以下元素：
[ 1, 2, 3, 4 ]复制代码
然后dequeue()将从数组中删除1，元素2，3和4将向前移动一个位置：
[ 2, 3, 4 ]复制代码
这是一个**O(n)**操作，因为所有数组元素都需要在内存中移动一个位置。
同样，在数组的前面插入一个元素也是昂贵的，因为它要求所有其他元素必须向后移动一个位置。 因此enqueueFront(5)会将数组更改为：
[ 5, 2, 3, 4 ]复制代码
首先，将元素2，3和4在内存中向后移动一个位置，然后将新元素5插入到曾经是2的位置。
为什么enqueue()和dequeueBack()没有这样的问题？
我们的初始数组[1, 2, 3, 4]实际上在内存中看起来像这样：
[ 1, 2, 3, 4, x, x, x ]复制代码
其中x表示数组中尚未使用的空间。 调用enqueue(6)只是将新元素复制到下一个未使用的空间：
[ 1, 2, 3, 4, 6, x, x ]复制代码
dequeueBack()函数使用array.removeLast()删除元素。这不会缩小数组的内存，只会将array.count减1。这里没有涉及昂贵的内存拷贝。因此在数组末尾的操作很快，复杂度是O(1)。
数组可能会用尽末尾预留的未使用空间。 在这种情况下，Swift将分配一个新的更大的数组，并复制所有数据。这是一个O(n)操作，但因为它只是偶尔发生一次，所以在数组末尾添加新元素的平均值仍然是O(1)。
当然，我们可以在数组的开头使用相同的技巧。 这将使我们的双端队列在 开头 的操作也高效。 我们的数组将如下所示：
[ x, x, x, 1, 2, 3, 4, x, x, x ]复制代码
现在在数组的开头还有一大块可用空间，这样，在数组前面添加或删除元素的操作也是O(1)。
这是Deque的新版本：
public struct Deque{ private var array: [T?] private var head: Int private var capacity: Int private let originalCapacity:Int public init(_ capacity: Int = 10) { self.capacity = max(capacity, 1) originalCapacity = self.capacity array = [T?](repeating: nil, count: capacity) head = capacity } 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 enqueueFront(_ element: T) { // this is explained below } public mutating func dequeue() -> T? { // this is explained below } public mutating func dequeueBack() -> T? { if isEmpty { return nil } else { return array.removeLast() } } public func peekFront() -> T? { if isEmpty { return nil } else { return array[head] } } public func peekBack() -> T? { if isEmpty { return nil } else { return array.last! } } }复制代码
这看起来与之前的代码基本相同 —— enqueue() 和 dequeueBack() 没有改变 —— 但也有一些重要的区别。 数组现在存储类型为T？的对象而不是T，因为我们数组元素可能会被标记为空。
init方法分配一个包含一定数量的nil值的新数组。 在数组开头处添加了空白空间，默认情况下，会创建10个空白空间。
head是数组中最前面对象的索引。 由于队列当前是空的，head指向数组末尾后面的索引。
[ x, x, x, x, x, x, x, x, x, x ] | head复制代码
为了将对象放在前面，我们将head向左移动一个位置，然后将新对象复制到索引head处。 例如，enqueueFront(5)结果：
[ x, x, x, x, x, x, x, x, x, 5 ] | head复制代码
enqueueFront(7)的结果:
[ x, x, x, x, x, x, x, x, 7, 5 ] | head复制代码
等等......head继续向左移动并始终指向队列中的第一个元素。enqueueFront()现在的操作是O(1)，因为它只涉及将元素复制到数组中，这是一个恒定时间操作。
代码：
public mutating func enqueueFront(element: T) { head -= 1 array[head] = element }复制代码 向队列后面添加元素方式没有改变（与之前的代码完全相同）。 例如，enqueue(1)结果：
[ x, x, x, x, x, x, x, x, 7, 5, 1, x, x, x, x, x, x, x, x, x ] | head复制代码
如果您将另一个对象入队，它将被添加到后面的下一个空白空间。 例如，enqueue(2)：
[ x, x, x, x, x, x, x, x, 7, 5, 1, 2, x, x, x, x, x, x, x, x ] | head复制代码
注意： 当你
print(deque.array)时，你不会在数组后面看到那些空白空间。 这是因为Swift会将它们隐藏起来。 只显示数组前面的空白空间。
dequeue()方法与enqueueFront()是相反操作，它读取head处的元素，将设置为nil，然后将head移动到右边的一个位置：
public mutating func dequeue() -> T? { guard head < array.count, let element = array[head] else { return nil } array[head] = nil head += 1 return element }复制代码 有一个很小的问题......如果在前面添加了很多对象，会在某些时候用尽前面的空白空间。 当这发生在数组的后面时，Swift会自动调整它的大小。 但是在数组的前面我们必须自己处理这种情况，在enqueueFront()中有一些额外的逻辑：
public mutating func enqueueFront(element: T) { if head == 0 { capacity *= 2 let emptySpace = [T?](repeating: nil, count: capacity) array.insert(contentsOf: emptySpace, at: 0) head = capacity } head -= 1 array[head] = element }复制代码 如果head等于0，则前面没有剩余空间。 当发生这种情况时，我们在数组中添加了一大堆新的nil元素。 这是一个O(n)操作，但由于这个操作不是在每次enqueueFront()调用时都会发生，所以每次对enqueueFront()单独调用的时间复杂度，仍然可以认为是O(1)。
注意： 每次发生这种情况时，我们会将容量乘以2，因此如果您的队列会越来越大，调整大小的次数也就越少。 这也是Swift数组在后面自动执行的操作方式。
我们必须为dequeue()做类似的事情。 如果你大部分时间将很多元素从前面入队，并且大多数时候也从前面出队，那么你最终可能会得到一个如下所示的数组：
[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, 1, 2, 3 ] | head复制代码
当你调用enqueueFront()时，只会使用前面的空白空间。 但是如果在前面入队的操作很少发生，那么就会有很多闲置的空白空间。 所以让我们在dequeue()中添加一些代码来清理它：
public mutating func dequeue() -> T? { guard head < array.count, let element = array[head] else { return nil } array[head] = nil head += 1 if capacity >= originalCapacity && head >= capacity*2 { let amountToRemove = capacity + capacity/2 array.removeFirst(amountToRemove) head -= amountToRemove capacity /= 2 } return element }复制代码 回想一下capacity是队列前面的空白空间的原始数量。 如果head向右移动的次数超过了容量的两倍(译注：head >= capacity*2)，那么就该修剪掉这些空白空间了。 我们将它降低到约25%。
注意： 通过将
capacity与originalCapacity进行比较，双端队列将至少保持其原始容量。
例如：
[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, 1, 2, 3 ] | | capacity head复制代码
修剪后：
[ x, x, x, x, x, 1, 2, 3 ] | head capacity复制代码
通过这种方式，我们可以在前面的快速入队、出队与保持合理的内存空间之间取得平衡。
注意： 我们不对非常小的数组执行修剪，仅保存几个字节的内存是没有必要的。
扩展阅读
其它可以实现双端队列的方法：，，或方法相反的两个。
作者：Matthijs Hollemans
翻译：校对：