第8章：队列

我们都很熟悉排队等候的情况。无论你是在排队购买你最喜欢的电影票，还是在等待打印机打印文件，这些现实生活中的场景都模仿了队列数据结构。

队列使用FIFO或先进先出的顺序，这意味着第一个加入的元素总是第一个被移除。当你需要保持元素的顺序以便以后处理时，队列就很方便。

在本章中，你将学习队列的所有常见操作，了解实现队列的各种方法，并看看每种方法的时间复杂性。

常见操作

让我们建立一个队列的协议。

public protocol Queue { 
  associatedtype Element 
  mutating func enqueue(_ element: Element) -> Bool 
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get } 
  var peek: Element? { get } 
}

var isEmpty: Bool { get } var peek: 元素？{ 得到 } }

该协议描述了一个队列的核心操作。

enqueue: 在队列的后面插入一个元素。如果操作成功，返回true。
dequeue: 删除队列前面的元素并返回。
isEmpty。检查队列是否为空。
peek（偷看）。返回队列前面的元素，但不删除它。

注意，队列只关心从前面删除和在后面插入。你不需要知道中间的内容是什么。如果你知道，你可能就会使用一个数组。

队列的例子

理解队列如何工作的最简单方法是看一个工作实例。想象一下，有一群人在排队买电影票。

目前排队的有雷、布莱恩、山姆和米克。一旦Ray收到他的票，他就会从队列中移出。通过调用dequeue()，Ray被从队列的前面移开。

调用peek将返回Brian，因为他现在在队伍的前面。

现在是Vicki，她刚刚加入了买票的队伍。通过调用enqueue("Vicki")，Vicki被添加到队列的后面。

在下面的章节中，你将学习以四种不同的方式创建队列。

使用一个数组
使用一个双链表
使用一个环形缓冲器
使用两个堆栈

基于数组的实现

Swift 标准库附带了一套核心的高度优化的原始数据结构，你可以用它来构建更高级别的抽象。其中之一是数组，这是一个存储连续、有序元素列表的数据结构。在本节中，你将使用数组来创建一个队列。
一个简单的Swift数组可以用来为队列建模。

打开启动器playground。在QueueArray页面，添加以下内容。

public struct QueueArray<T>: Queue { 
  private var array: [T] = [] 
  public init() {} 
}

在这里，你已经定义了一个采用Queue协议的通用QueueArray结构。请注意，编译器从类型参数T中推断出相关的类型Element。

接下来，你将完成QueueArray的实现以符合Queue协议。

充分利用数组

给QueueArray添加以下代码。

public var isEmpty: Bool { 
  array.isEmpty // 1 
}

public var peek: T? { 
  array.first // 2 
}

利用Array的特性，你可以免费得到以下东西。

检查队列是否为空。
返回队列中最前面的元素。这些操作都是O(1)。

入队

在队列的后面添加一个元素很容易。只要在数组中追加一个元素就可以了。添加以下内容。

public mutating func enqueue(_ element: T) -> Bool { 
  array.append(element) 
  return true 
}

平均来说，排队等候一个元素是一个O(1)操作。这是因为数组的后面有空的空间。

在上面的例子中，请注意，一旦你添加了Mic，数组就有两个空位。

添加多个元素后，数组最终会被填满。当你想使用超过分配的空间时，数组必须调整大小以腾出额外的空间。

你可能会觉得奇怪，尽管调整大小是一个O(1)操作，但排队却是一个O(n)操作。毕竟，调整大小需要数组分配新的内存，并将所有现有数据复制到新的数组中。关键是，这种情况并不经常发生。这是因为每次空间用完后，容量都会翻倍。因此，如果你计算出操作的摊销成本（平均成本），排队只是O（1）。也就是说，在进行复制时，最坏情况下的性能是O(n)。

出队

从前面删除一个项目需要多做一点工作。添加以下内容。

public mutating func dequeue() -> T? { 
  isEmpty ? nil : array.removeFirst() 
}

如果队列是空的，dequeue只是返回nil。如果不是，它从数组的前面移除元素并返回。

从队列的前面移除一个元素是一个O(n)操作。要出队，你要从数组的开头删除元素。这总是一个线性时间的操作，因为它要求数组中所有剩余的元素都在内存中移位。

调试和测试

为了调试的目的，你要让你的队列采用CustomStringConvertible协议。在页面的底部添加以下内容。

extension QueueArray: CustomStringConvertible { 
  public var description: String { 
    String(describing: array) 
  } 
}

是时候尝试一下你刚刚实施的队列了! 在页面的底部添加以下内容。

var queue = QueueArray<String>()
queue.enqueue("Ray") 
queue.enqueue("Brian") 
queue.enqueue("Eric") 
queue 
queue.dequeue() 
queue 
queue.peek

这段代码把雷、布莱恩和埃里克放在队列中，然后删除雷并偷看布莱恩，但并没有删除他。

优势和劣势

下面是对基于数组的队列实现的算法和存储复杂性的总结。除了dequeue()需要线性时间，大多数操作都是恒定时间。存储空间也是线性的。

你已经看到了通过利用Swift数组来实现基于数组的队列是多么容易。平均而言，由于有O(1)追加操作，Enqueue的速度非常快。

这个实现有一些不足之处。从队列的前面删除一个项目可能是低效的，因为删除会导致所有元素向上移动一个。这对非常大的队列来说是有影响的。一旦数组满了，它就必须调整大小，可能会有未使用的空间。这可能会随着时间的推移增加你的内存占用。有可能解决这些缺点吗？让我们看看基于链接列表的实现，并将其与QueueArray进行比较。

双重链接列表的实现

切换到QueueLinkedListplayground页面。在该页面的Sources文件夹中，你会注意到一个DoublyLinkedList类。你应该已经从第6章 "链接列表 "中熟悉了链接列表。双重链接列表是一个简单的链接列表，其中的节点也引用前一个节点。

首先，在页面的最末端添加一个通用的QueueLinkedList，如下所示。

public class QueueLinkedList<T>: Queue {
  private var list = DoublyLinkedList<T>()
  public init() {}
}

这个实现类似于QueueArray，但你创建的不是一个数组，而是一个DoublyLinkedList。

接下来，让我们开始符合Queue协议。

阙值

要将一个元素添加到队列的后面，只需添加以下内容。

public func enqueue(_ element: T) -> Bool { 
  list.append(element) 
  return true 
}

在幕后，双链表将更新其尾部节点的上一个和下一个引用到新节点上。这是一个O(1)操作。

出队

要从队列中删除一个元素，请添加以下内容。

public func dequeue() -> T? { 
  guard !list.isEmpty, let element = list.first else { 
    return nil 
  } 
  return list.remove(element) 
}

这段代码检查列表是否为空，队列的第一个元素是否存在。如果不存在，它将返回 nil。否则，它将删除并返回队列中最前面的元素。

从列表的前面删除也是一个O(1)操作。与数组的实现相比，你没有必要一个一个地转移元素。相反，在上图中，你只需更新链接列表前两个节点之间的下一个和上一个指针。

检查队列的状态

与数组的实现类似，你可以使用 DoublyLinkedList 的属性实现 peek 和 isEmpty。添加以下内容。

public var peek: T? { 
 list.first?.value 
}

public var isEmpty: Bool { 
 list.isEmpty 
}

调试和测试

为了调试的目的，你可以在页面的底部添加以下内容。

extension QueueLinkedList: CustomStringConvertible { 
  public var description: String { 
    String(describing: list) 
  } 
}

这种一致性利用了DoublyLinkedList对CustomStringConvertible协议的默认实现。

这就是使用链接列表实现队列的全部内容了在playground的QueueLinkedList页面，你可以试试这个例子。

var queue = QueueLinkedList<String>()
queue.enqueue("Ray") 
queue.enqueue("Brian") 
queue.enqueue("Eric") 
queue 
queue.dequeue() 
queue 
queue.peek

这个测试代码产生的结果与你的QueueArray实现相同。

优势和劣势

让我们总结一下基于双链接列表的队列实现的算法和存储复杂性。

QueueArray的一个主要问题是，排队一个项目需要线性时间。通过链接列表的实现，你把它减少到一个常数操作，即O(1)。你所需要做的就是更新节点的上一个和下一个指针。

QueueLinkedList的主要弱点在表格中并不明显。尽管有O(1)的性能，但它的开销却很高。每个元素都必须有额外的存储空间用于前向和后向引用。此外，每次创建一个新元素时，都需要进行相对昂贵的动态分配。相比之下，QueueArray做了一个更快的批量分配。

你能消除分配开销和主O(1)脱队吗？如果你不必担心你的队列增长超过一个固定的大小，你可以使用像环形缓冲器这样的不同方法。例如，你可能有一个有五个玩家的大富翁游戏。你可以使用一个基于环形缓冲器的队列来跟踪下一个轮子是谁。接下来你会看到一个环形缓冲器的实现。

环形缓冲器的实现

环形缓冲器，也被称为圆形缓冲器，是一个固定大小的数组。这种数据结构在结束时没有更多的项目需要移除时，会战略性地绕到开头。

我们来看看一个简单的例子，看看如何用环形缓冲器来实现队列。

你首先创建一个固定大小为4的环形缓冲区，环形缓冲区有两个指针，用来跟踪两件事。

读取指针跟踪队列的前面。
写指针跟踪下一个可用的槽，这样你就可以覆盖已经读过的现有元素。

让我们来锁定一个项目。

每当你向队列中添加一个项目时，写指针就会递增一个。让我们再添加几个元素。

请注意，写指针又移动了两个位置，并且领先于读指针。这意味着队列不是空的。

接下来，让我们去排队两个项目。

去排队相当于读取一个环形缓冲区。注意读指针如何移动了两次。

现在，再排一个项目来填满队列。

因为写指针到达了终点，所以它只是再次绕到了起始索引。这就是为什么该数据结构被称为环形缓冲区。

最后，把剩下的两个项目去阙。

读取指针也会被包到开头。

作为最后的观察，注意到只要读和写指针在同一个索引上，队列就是空的。

现在你对环形缓冲区如何组成队列有了更好的理解，让我们来实现一个队列吧!

转到QueueRingBuffer的游戏页面。在该页面的Sources文件夹中，你会注意到一个RingBuffer类。

注意：如果你想了解更多关于这个类的实现，请查看https://github.com/raywenderlich/swiftalgorithm-club/tree/master/Ring%20Buffer 上的完整演练。

在QueueRingBuffer页面中，添加以下内容。

public struct QueueRingBuffer<T>: Queue { 
  private var ringBuffer: RingBuffer<T>

  public init(count: Int) { 
    ringBuffer = RingBuffer<T>(count: count) 
  }

  public var isEmpty: Bool { 
    ringBuffer.isEmpty 
  }

  public var peek: T? { 
    ringBuffer.first 
  }

}

这里，你定义了一个通用的QueueRingBuffer。注意，你必须包含一个计数参数，因为环形缓冲区有一个固定的大小。

为了符合 Queue 协议，你还创建了两个属性 isEmpty 和 peek。你没有暴露ringBuffer，而是提供了辅助变量来访问队列的前端，并检查队列是否为空。这两个都是O(1)操作。

入队

接下来，添加下面这个方法。

public mutating func enqueue(_ element: T) -> Bool { 
  ringBuffer.write(element) 
}

要将一个元素追加到队列中，你只需在ringBuffer上调用write(_:)。这将使写指针增加1。

由于队列有一个固定的大小，你现在必须返回true或false来表示元素是否被成功添加。enqueue(_:) 仍然是一个O(1)操作。

出队

接下来添加以下内容。

public mutating func dequeue() -> T? { 
  ringBuffer.read() 
}

要从队列的前面删除一个项目，你只需在ringBuffer上调用read()。在幕后，它检查ringBuffer是否为空，如果是，则返回nil。如果不是，它会从缓冲区的前面返回一个项目，并将读取指针增加1。

调试和测试

要在playground上看到你的结果，请添加以下内容。

extension QueueRingBuffer: CustomStringConvertible { 
  public var description: String { 
    String(describing: ringBuffer) 
  } 
}

这段代码通过委托给底层的环形缓冲区来创建一个队列的字符串表示。

这就是它的全部内容了! 通过在页面底部添加以下内容来测试你的基于环形缓冲区的队列。

var queue = QueueRingBuffer<String>(count: 10) queue.enqueue("Ray") 
queue.enqueue("Brian") 
queue.enqueue("Eric") 
queue 
queue.dequeue() 
queue 
queue.peek

这段测试代码的工作原理就像前面的例子一样，对Ray进行排队，对Brian进行偷看。

优势和劣势

环形缓冲区的实现是如何比较的？让我们看一下算法和存储复杂性的总结。

基于环形缓冲区的队列的enqueue和dequeue的时间复杂度与链接列表的实现相同。唯一的区别是空间复杂度。环形缓冲区有一个固定的大小，这意味着enqueue会失败。

到目前为止，你已经看到了三种实现方式：一个简单的数组、一个双链表和一个环形缓冲器。

尽管它们看起来非常有用，但你接下来要看的是一个使用两个堆栈实现的队列。你将看到它的空间定位性是如何远远优于链表的。它也不像环形缓冲器那样需要一个固定的大小。

双层堆栈的实现

打开QueueStackplayground页面，首先添加一个通用QueueStack，如下图所示。

public struct QueueStack<T> : Queue { 
  private var leftStack: [T] = [] 
  private var rightStack: [T] = [] 
  public init() {} 
}

使用两个堆栈的想法很简单。无论何时，当你排队等待一个元素时，它就会进入右边的堆栈。

当你需要取消一个元素时，你就把右边的堆栈倒过来，放在左边的堆栈里，这样你就可以用先进先出的顺序来检索这些元素了。

充分利用数组

实现队列的常见功能，从下面开始。

public var isEmpty: Bool { 
  leftStack.isEmpty && rightStack.isEmpty 
}

要检查队列是否是空的，要检查左堆栈和右堆栈都是空的。这意味着没有任何元素可以去排队，也没有新的元素被排队。

接下来，添加以下内容。

public var peek: T? { 
  !leftStack.isEmpty ? leftStack.last : rightStack.first 
}

你知道peeking看的是最上面的元素。如果左边的堆栈不是空的，这个堆栈顶部的元素就在队列的前面。

如果左边的堆栈是空的，右边的堆栈将被颠倒过来，放在左边的堆栈中。在这种情况下，右堆栈底部的元素就在队列的下一个位置。注意，isEmpty和peek这两个属性仍然是O(1)操作。

入队

接下来添加下面这个方法。

public mutating func enqueue(_ element: T) -> Bool { 
  rightStack.append(element) 
  return true 
}

回顾一下，右边的堆栈是用来排队等候元素的。

你只需通过追加到数组来推送到栈中。之前，通过实现QueueArray，你知道追加一个元素是一个O(1)操作。

出队

从一个基于两栈的队列实现中删除一个项目是很棘手的。添加以下方法。

public mutating func dequeue() -> T? { 
  if leftStack.isEmpty { // 1 
    leftStack = rightStack.reversed() // 2 
    rightStack.removeAll() // 3 
  } 
  return leftStack.popLast() // 4 
}

检查左边的堆栈是否为空。
如果左堆栈是空的，将其设置为右堆栈的反向。
使你的右堆栈无效。因为你已经把所有的东西都转移到了左边，所以只需清除它。
从左边堆栈中取出最后一个元素。

记住，只有当左边的堆栈是空的时候，你才会转移右边堆栈中的元素!

注意：是的，反转数组的内容是一个O(n)操作。整体的去排队成本仍然是摊销的O(1)。想象一下，在左边和右边的堆栈中都有大量的项目。如果你取消所有的元素，首先它将从左堆栈中移除所有的元素，然后只反向复制右堆栈一次，然后继续从左堆栈中移除元素。

调试和测试

要在playground上看到你的结果，请添加以下内容。

extension QueueStack: CustomStringConvertible { 
  public var description: String { 
    String(describing: leftStack.reversed() + rightStack) 
  } 
}

在这里，你只需将左堆栈与右堆栈的反向结合起来，并打印所有的元素。

让我们尝试一下双堆栈的实现。

var queue = QueueStack<String>()
queue.enqueue("Ray") 
queue.enqueue("Brian") 
queue.enqueue("Eric") 
queue 
queue.dequeue() 
queue 
queue.peek

像之前所有的例子一样，这段代码对Ray、Brian和Eric进行排队，对Ray进行排队，然后对Brian进行窥视。

优势和劣势

让我们来看看基于双栈的实现的算法和存储复杂性的总结。

与基于数组的实现相比，通过利用两个堆栈，你能够将dequeue(_:)变成一个摊销的O(1)操作。

此外，你的双栈实现是完全动态的，没有基于环形缓冲区的队列实现那样的固定大小限制。当右队列需要反转或耗尽容量时，最坏情况下的性能是O(n)。由于每次发生时都会翻倍，因此容量耗尽的情况并不经常发生。

最后，它在空间定位方面战胜了链表。这是因为数组元素在内存块中是彼此相邻的。所以大量的元素会在第一次访问时被加载到缓存中。即使数组需要O(n)，对于简单的复制操作，它是一个非常快的O(n)发生在接近内存带宽的地方。

比较下面的两张图片。

一个链接列表，其中的元素不在连续的内存块中。这种非局部性可能会导致更多的缓存缺失，这将增加访问时间。

关键点

队列采取FIFO策略；先添加的元素也必须先删除。
Enqueue将一个元素插入到队列的后面。
Dequeue删除队列前面的元素。
阵列中的元素被布置在连续的内存块中，而链表中的元素则比较分散，有可能出现缓存丢失的情况。
基于Ring-buffer-queue的实现适用于具有固定大小的队列。
与其他数据结构相比，利用两个堆栈可以将dequeue(_:)的时间复杂度提高到摊销的O(1)操作。
双堆栈的实现在存储区域性方面胜过了链接列表。

上一章	目录	下一章