队列
栈
这个话题已经有个辅导文章
栈类似于数组，但是限制了存取操作的灵活性。栈只允许使用者从栈顶 压入(push) 元素；从栈顶 弹出(pop) 元素；取得(peek) 栈顶元素，但不弹出。
这样的限制有什么意义呢？在很多算法的实现中，你可能需要将某些对象放到一个临时的列表中，之后再将其取出。通常加入和取出元素的顺序非常重要。
栈可以保证元素存入和取出的顺序是后进先出(last-in first-out, LIFO)的。栈中弹出的元素总是你最后放进去的那个。另外一个非常类似的数据结构是队列，它是一个先进先出(first-in, first-out, FIFO)的结构。
举例来说，我们先将一个数字压入栈中：
stack.push(10)栈现在是 [10]。压入下一个数字：
stack.push(3)栈现在是 [10, 3]。再压入一个数字：
stack.push(57)栈现在是 [10, 3, 57]。现在把栈顶的数字弹出来：
stack.pop()这行代码返回 57，因为它是我们最后压入的元素。现在栈又变成了 [10, 3]。
stack.pop()这行代码返回 3，以此类推。如果栈空了，弹栈操作将返回 nil，在有些实现中，会触发一个 stack underflow 错误消息。
栈在 Swift 中的实现非常容易。只需要包装一下自带的数组，将存取功能限制为 pop、push 和 查看栈的顶部元素。
public struct Stack<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}注意到，压栈操作是将新元素压入数组的尾部，而不是头部。在数组的头部插入元素是一个很耗时的操作，它的时间复杂度为 O(n)，因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1)；无论数组有多少元素，这个操作所消耗的时间都是一个常量。
关于栈的有趣知识：每次你调用函数或方法，CPU都会将函数返回地址压入到运行栈中。当这个函数执行结束的时候，CPU将返回地址从栈中取出，并据此返回到函数被调用的位置。所以，如果不断地调用太多的函数(例如死递归函数)，就会得到一个所谓的“栈溢出(stack overflow)” 错误，因为CPU运行栈没有空间了。
队列
这个话题已经有个辅导文章
队列的本质是一个列表，但只能从队尾添加元素，从队首移除元素。这保证了第一个入队的元素总是第一个出队。先到先得！
为什么要这样做呢？在很多算法的实现中，你可能需要将某些对象放到一个临时的列表中，之后再将其取出。通常加入和取出元素的顺序非常重要。
队列可以保证元素存入和取出的顺序是先进先出(first-in first-out, FIFO)的，第一个入队的元素总是第一个出队，公平合理！
另外一个非常类似的数据结构是栈，它是一个后进先出(last-in, first-out, 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，在有些实现中，会触发一个错误信息。
注意： 队列并不总是最好的选择，如果加入和删除元素的顺序无所谓的话，你可以选择使用栈来达到目的。栈更加简单快速。
代码
下面给出了一个简单粗暴的队列实现。它只是简单地包装了一下自带的数组，并提供了入队(enqueue)、出队(dequeue)和取得队首元素(peek)三个操作：
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 的内部实现中，数组的尾部总是有一些预设的空间可供使用。如果我们进行如下操作：
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 ]这只是简单的拷贝内存的工作，只需要固定的常量时间。
当然，数组尾部的未使用内存的大小是有限的，如果最后一块未使用内存也被占用的时候，再添加元素会使得数组重新调整大小来获取更多的空间。
重新调整的过程包括申请新的内存，将已有数据迁移到新内存中。这个操作的时间复杂度是 O(n)，所以是一个较慢的操作。但考虑到这种情况并不常见，所以，这个操作的时间复杂度依然是 O(1) 的，或者说是近似 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(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 变量用于存储队列首元素的下标值。
绝大多数的改进都是针对 dequeue() 函数，在将队首元素出队时，我们首先将 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
}这段代码计算了队首空余的元素占数组总元素的百分比，如果空余元素超过 25%，我们就进行一波清理。但是，如果队列的长度过小，我们也不想频繁地清理空间，所以在清理空间之前，队列中至少要有 50 个元素。
注意： 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(n) 变为了现在的 O(1)，只是因为我们在数组的使用策略上耍了一点小心机。
扩展阅读
事实上，队列还有很多种其他的实现方式，例如可以使用链表、环形缓冲区或是堆来实现。
队列有很多变体，包括双端队列，一个两端都可以出队和入队的队列；优先队列，一个有序的队列，最重要的元素排在队首。
双端队列(Deque)
出于某种原因，双端队列也被称为“deck”。
常规队列元素在后面添加（入队），从前面删除（出队）。 除了这些，双端队列还可以在后面出队，从前面入队，并且两端都可查看。
Swift中双端队列的一个非常基本的实现：
public struct Deque<T> {
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<Int>()
deque.enqueue(1)
deque.enqueue(2)
deque.enqueue(3)
deque.enqueue(4)
deque.dequeue() // 1
deque.dequeueBack() // 4
deque.enqueueFront(5)
deque.dequeue() // 5Deque的这种实现很简单但效率不高。几个操作是 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()没有这样的问题？
好吧，这些操作是在数组末尾操作的。在Swift中数组默认都是可调整大小的，它的实现方式是，在数组后面预留一定量的可用空间。
我们的初始数组[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<T> {
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 ]
|
headenqueueFront(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通过这种方式，我们可以在前面的快速入队、出队与保持合理的内存空间之间取得平衡。
注意： 我们不对非常小的数组执行修剪，仅保存几个字节的内存是没有必要的。
扩展阅读
其它可以实现双端队列的方法：双向链表，环形缓冲区，或方法相反的两个栈。
优先队列(Priority Queue)
优先队列是一种队列，其中最重要的元素始终位于前面。
优先队列可以分为：max-priority队列（最大元素优先）或min-priority队列（最小元素优先）。
为什么要使用优先队列？
优先队列对于需要处理（有大量）项目的算法以及反复需要识别哪个项目现在最大或最小 —— 或者是定义“最重要”的算法非常有用。
可以从优先队列中受益的算法示例：
事件驱动的模拟。 每个事件都有一个时间戳，您希望按照时间戳的顺序执行事件。 优先队列可以轻松找到需要模拟的下一个事件。
Dijkstra的图搜索算法使用优先队列来计算最低成本。
霍夫曼编码 用于数据压缩。 该算法构建压缩树。 它反复需要找到具有最小频率且尚未具有父节点的两个节点。
用于人工智能的A*寻路。
很多其他地方！
使用常规队列或普通旧数组，您需要反复扫描整个序列以查找下一个最大的项目。 优先队列针对此类事物进行了优化。
你可以用优先队列做什么？
优先队列的常见操作：
入队：在队列中插入一个新元素。
出队：删除并返回队列中最重要的元素。
查找最小值或查找最大值：返回最重要的元素但不删除它。
更改优先级：当您的算法决定元素已经在队列中时变得更重要时。
如何实现优先队列
有不同的方法来实现优先队列：
作为有序数组。 最重要的项目位于数组的末尾。 缺点：插入新项目很慢，因为它们必须按排序顺序插入。
作为平衡的二叉搜索树。 这对于制作双端优先队列非常有用，因为它可以有效地实现“查找最小值”和“查找最大值”。
作为堆。 堆是优先队列的自然数据结构。 实际上，这两个术语通常用作同义词。 堆比排序数组更有效，因为堆只需要部分排序。 所有堆操作都是O(log n)。
这是基于堆的Swift优先队列：
public struct PriorityQueue<T> {
fileprivate var heap: Heap<T>
public init(sort: (T, T) -> Bool) {
heap = Heap(sort: sort)
}
public var isEmpty: Bool {
return heap.isEmpty
}
public var count: Int {
return heap.count
}
public func peek() -> T? {
return heap.peek()
}
public mutating func enqueue(element: T) {
heap.insert(element)
}
public mutating func dequeue() -> T? {
return heap.remove()
}
public mutating func changePriority(index i: Int, value: T) {
return heap.replace(index: i, value: value)
}
}
正如你所看到的，没有什么可以做的。 如果你有堆，那么建立优先队列很容易，因为堆几乎是一个优先队列。
扩展阅读
环形缓冲区（Ring Buffer）
也称为循环缓冲区。
基于数组的队列的问题是在队列后面添加新项目很快，O(1)，但是从队列前面删除项目很慢，O(n)。删除速度很慢，因为它需要在内存中移动剩余的数组元素。
实现队列的更有效方法是使用环形缓冲区或循环缓冲区。 这是一个概念性地回绕到开头的数组，因此您永远不必删除任何项目。 所有操作都是O(1)。
原则上它是如何工作的。 我们有一个固定大小的数组，比如5项：
[ , , , , ]
r
w最初，数组为空，读（r）和写（w）指针位于开头。
让我们为这个数组添加一些数据。 我们将写入或叫“入队”，数字123：
[ 123, , , , ]
r
---> w每次添加数据时，写指针都向前移动一步。 让我们添加更多元素：
[ 123, 456, 789, 666, ]
r
-------------> w现在数组中还有一个空点，但是应用程序决定读取一些数据，而不是将另一个项送入队列。这是可能的，因为写指针位于读指针之前，这意味着数据可用于读取。 读取指针随着读取可用数据而前进：
[ 123, 456, 789, 666, ]
---> r w让我们再读两项：
[ 123, 456, 789, 666, ]
--------> r w现在应用程序决定再次写入并再入队两个数据项333和555：
[ 123, 456, 789, 666, 333 ]
r ---> w哎呀，写指针已到达数组的末尾，因此对象555没有更多的空间。现在怎么办？好吧，这就是为什么它是循环缓冲区：我们将写指针包装回到开头并写入剩余数据：
[ 555, 456, 789, 666, 333 ]
---> w r 我们现在可以阅读剩余的三个项目，666，333和555。
[ 555, 456, 789, 666, 333 ]
w --------> r 当然，当读指针到达缓冲区的末尾时，它也会回绕：
[ 555, 456, 789, 666, 333 ]
w
---> r现在缓冲区再次为空，因为读指针已经赶上了写指针。
这是Swift中一个非常基本的实现：
public struct RingBuffer<T> {
fileprivate var array: [T?]
fileprivate var readIndex = 0
fileprivate var writeIndex = 0
public init(count: Int) {
array = [T?](repeating: nil, count: count)
}
public mutating func write(_ element: T) -> Bool {
if !isFull {
array[writeIndex % array.count] = element
writeIndex += 1
return true
} else {
return false
}
}
public mutating func read() -> T? {
if !isEmpty {
let element = array[readIndex % array.count]
readIndex += 1
return element
} else {
return nil
}
}
fileprivate var availableSpaceForReading: Int {
return writeIndex - readIndex
}
public var isEmpty: Bool {
return availableSpaceForReading == 0
}
fileprivate var availableSpaceForWriting: Int {
return array.count - availableSpaceForReading
}
public var isFull: Bool {
return availableSpaceForWriting == 0
}
}RingBuffer对象有一个数组用于实际存储数据，readIndex和writeIndex变量用于指向数组的“指针”。 write()函数将新元素放入writeIndex中的数组中，read()函数返回readIndex中的元素。
但是，你说，如何继续工作下去？ 有几种方法可以实现这一点，我选择了一个稍微有争议的方法。 在这个实现中，writeIndex和readIndex总是递增，永远不会实际回绕。 相反，我们执行以下操作来查找数组的实际索引：
array[writeIndex % array.count]and:
array[readIndex % array.count]换句话说，我们分别获取读取索引和写入索引除以底层数组的大小的模数（或余数）。
这有点争议的原因是writeIndex和readIndex总是递增，所以理论上这些值可能变得太大而不适合整数，应用程序将崩溃。然而，快速的卫生巾计算应该可以消除这些担忧。
writeIndex和readIndex都是64位整数。 如果我们假设它们每秒递增1000次，这是很多，那么连续一年这样做需要ceil（log_2（365 * 24 * 60 * 60 * 1000））= 35位。 这留下了28位，因此在遇到问题之前应该给你大约2 ^ 28年。 那是很长一段时间。:-)
要使用此环形缓冲区，请将代码复制到playground并执行以下操作以模仿上面的示例：
var buffer = RingBuffer<Int>(count: 5)
buffer.write(123)
buffer.write(456)
buffer.write(789)
buffer.write(666)
buffer.read() // 123
buffer.read() // 456
buffer.read() // 789
buffer.write(333)
buffer.write(555)
buffer.read() // 666
buffer.read() // 333
buffer.read() // 555
buffer.read() // nil您已经看到环形缓冲区可以创建更优的队列，但它也有一个缺点：包装使得调整队列大小变得棘手。但如果一个固定大小的队列适合你的目的，那么你就牛掰了。
当数据生产者以不同于数据使用者读取数据的速率写入数组时，环形缓冲区也非常有用。这通常发生在文件或网络I/O上。环形缓冲区也是高优先级线程（例如音频渲染回调）与系统其他较慢部分之间通信的首选方式。
这里给出的实现不是线程安全的。它仅作为环形缓冲区如何工作的示例。也就是说，通过使用OSAtomicIncrement64()来改变读写指针，使单个读写器和单个编写器的线程安全应该是相当简单的。
制作一个非常快的环形缓冲区的一个很酷的技巧是使用操作系统的虚拟内存系统将相同的缓冲区映射到不同的内存页面。疯狂的东西，但值得研究是否需要在高性能环境中使用环形缓冲区。