跳转至

8.队列

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

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

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

常见操作

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

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

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

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

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

队列的例子

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

img

目前排队的有Ray、Brian、Sam和Mic。一旦Ray收到他的票，他就会从队列中移出。通过调用dequeue()，Ray被从队列的前端移除。

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

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

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

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

基于数组的实现

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

img

打开启动器操场。在QueueArray页面中，添加以下内容：

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

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

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

充分利用数组

在QueueArray中添加以下代码：

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

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

使用Array的功能，你可以免费获得以下东西：

  1. 检查队列是否为空。
  2. 返回队列中最前面的元素。

这些操作都是O(1)。

Enqueue

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

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

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

img

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

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

img

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

Dequeue

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

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

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

img

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

调试和测试

为了调试的目的，你要让你的queue采用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

这段代码将Ray、Brian和Eric放入队列中，然后删除Ray并偷看Brian，但并没有删除他。

优势和劣势

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

img

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

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

双链表的实现

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

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

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

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

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

Enqueue

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

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

img

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

Dequeue

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

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

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

img

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

检查队列的状态

与数组的实现类似，你可以使用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

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

优势和劣势

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

img

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

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

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

环形缓冲器的实现

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

下面是一个简单的例子，说明如何使用环形缓冲器来实现队列：

img

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

  1. read的指针跟踪队列的前面的情况。
  2. write指针跟踪下一个空位，这样你就可以覆盖已经被读取的现有元素。

让我们来排队一个项目：

img

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

img

请注意，write的指针又移动了两个位置，在read的指针之前。这意味着队列不是空的。

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

img

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

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

img

由于write的指针到达了终点，它只是再次绕到了起始索引。这就是为什么该数据结构被称为循环缓冲区。

最后，把剩下的两个项目去掉：

img

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

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

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

进入QueueRingBuffer操场页面。在该页面的Sources文件夹中，你会发现一个RingBuffer类。

Note

如果你想了解更多关于这个类的实现，请查看https://github.com/raywenderlich/swift-algorithm-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。注意，你必须包含一个count参数，因为环形缓冲区有一个固定的大小。

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

Enqueue

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

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

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

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

Dequeue

接下来添加以下内容：

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

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

调试和测试

要在操场上看到你的结果，请添加以下内容：

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。

优势和劣势

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

img

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

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

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

双堆栈的实现

打开QueueStack操场页面，开始添加一个通用的QueueStack，如下图：

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

使用两个堆栈的想法很简单。无论什么时候，当你获取一个元素时，它将被放在right堆栈中。

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

img

利用数组

实现队列的常见功能，从以下几个方面入手：

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

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

接下来，添加以下内容：

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

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

如果左边的堆栈是空的，右边的堆栈将被反转，放在左边的堆栈中。

在这种情况下，右堆栈的底部的元素在队列的下一个位置。注意，两个属性isEmpty和peek仍然是O(1)操作。

Enqueue

接下来添加下面的方法：

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

回想一下，right堆栈是用来排队的元素。

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

img

Dequeue

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

public mutating func dequeue() -> T? {
  if leftStack.isEmpty { // 1
    leftStack = rightStack.reversed() // 2
    rightStack.removeAll() // 3
  }
  return leftStack.popLast() // 4
}
  1. 检查左边的堆栈是否为空。
  2. 如果左边的堆栈是空的，把它设置为右边堆栈的反向。

img

  1. 使你的右边堆栈失效。因为你已经把所有的东西都转移到了左边，所以只要清除它就可以了。
  2. 从左边的堆栈中取出最后一个元素。

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

Note

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

调试和测试

要在操场上看到你的结果，请添加以下内容：

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进行偷看。

优势和劣势

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

img

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

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

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

比较下面的两张图片：

img

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

img

关键点

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