第9章：队列进阶

你认为你已经掌握了队列的知识？在本章中，你将探索与队列有关的五个不同问题。这将有助于巩固你对数据结构的基本知识。

挑战1：堆栈与队列

解释堆栈和队列之间的区别。为每种数据结构提供两个现实生活中的例子。

挑战2：分步示意图

给出以下队列。

提供分步图，说明以下一系列命令如何影响队列。

enqueue("R") 
enqueue("O") 
dequeue() 
enqueue("C") 
dequeue() 
dequeue() 
enqueue("K")

对下列队列的实现进行这样的处理。

基于数组的
链接列表
环形缓冲区
基于堆栈

假设数组和环形缓冲区的初始大小都是5。

挑战3：轮到谁了？

打开启动器项目，导航到挑战3的游戏页面，开始。想象一下，你正在和你的朋友玩大富翁游戏。问题是，每个人总是忘记该轮到谁了! 创建一个大富翁组织者，总是告诉你该轮到谁了。下面是一个你可以遵守的协议。

协议BoardGameManager {

protocol BoardGameManager {
  associatedtype Player 
  mutating func nextPlayer() -> Player?
}

挑战4：反转队列

导航到挑战4的游戏页面开始。实现一个方法来逆转队列的内容。

Hint: The Stack data structure has been included in the Sources folder.

extension QueueArray {
  func reversed() -> QueueArray { 
    var queue = self 
    // Solution here.
    return queue 
  }
}

挑战5: 双端队列

双端队列--又称deque--顾名思义，是一种可以从前面或后面添加或删除元素的队列。

一个队列（FIFO顺序）允许你在后面添加元素，并从前面删除它们。
堆栈（LIFO顺序）允许你向后面添加元素，并从后面删除它们。

Deque可以同时被认为是一个队列和一个栈。

我们提供了一个简单的Deque协议来帮助你建立你的数据结构。我们提供了一个枚举方向来帮助描述你是在deque的前面还是后面添加或删除一个元素。你可以使用任何你喜欢的数据结构来构建一个Deque。

注意。

在DoubleLinkedList.swift中增加了一个额外的属性和函数。

增加了一个名为last的属性，以帮助获得双链接列表的尾部元素。
增加了一个叫做 prepend(_:) 的函数，帮助你在双链接列表的前面增加一个元素。

解决方案

挑战1的解决方案

队列有一个先入先出的行为。先进来的东西必须先出来。队列中的物品从后面插入，从前面取出。

排队的例子。

电影院里的排队。你会讨厌人们在电影院买票时插队!
打印机。多个人可以以类似先来后到的方式从一台打印机上打印文件。

堆栈有一个后进先出的行为。堆栈上的物品从顶部插入，从顶部取出。

堆栈的例子。

盘子的堆叠。把盘子放在彼此的上面，每次使用盘子的时候都把最上面的盘子拿掉。这不是比抓取底部的那个更容易吗？
撤销功能。想象一下在键盘上打字的情景。点击Ctrl-Z将撤消你最近输入的文字。

挑战2的解决方案

阵列

请记住，每当数组满了，你试图添加一个新的元素时，就会创建一个新的数组，其容量是现有元素的两倍，被复制过来。

链表

环形缓冲区

双栈

挑战3的解决方案

创建一个棋盘游戏管理员是很简单的。你所关心的就是轮到谁了。一个队列数据结构是采用BoardGameManager协议的最佳选择

扩展QueueArray。BoardGameManager {

采用这个协议有两个要求。你首先将typealias设置为等于参数类型T。接下来，你实现nextPlayer，其工作原理如下。

通过调用dequeue获得下一个玩家。如果队列是空的，返回nil。
对同一个人进行enqueue，将该玩家放在队列的最后。
返回下一个玩家。

时间复杂度取决于你选择的队列实现。对于基于数组的队列，总体上是_O(n)的时间复杂度。dequeue需要_O(n)的时间，因为每次删除第一个元素时，它必须将元素向左移动。测试一下吧。

挑战4的解决方案

队列使用先入先出，而堆栈使用后入先出。你可以用堆栈来帮助扭转队列的内容。通过将队列的所有内容插入堆栈，一旦你从堆栈中弹出每一个元素，你就可以将顺序颠倒过来!

你选择什么队列的实现并不重要。只要它符合Queue协议，你就可以把它泛化为任何队列!

对于这个解决方案，你可以通过添加一个反转函数来扩展QueueArray。它的工作方式如下。

创建一个队列的副本。
创建一个堆栈。
将队列中的所有元素脱队到堆栈中。
从堆栈中弹出所有的元素，并把它们插入队列中。
返回你的反转队列!

时间复杂度总体为O(n)。你在元素中循环两次。一次是将元素从队列中移除，另一次是将元素从堆栈中移除。

测试一下吧。

挑战5的解决方案

Deque是由队列和堆栈数据结构的常见操作组成的。有许多方法可以实现Deque。你可以用一个循环缓冲器、两个堆栈、一个数组或一个双链表来构建一个。下面的解决方案使用了双链表来构建一个Deque。

首先设置双链表deque，如下所示。

class DequeDoubleLinkedList<Element>: Deque {
  private var list = DoublyLinkedList<Element>()
  public init() {}
}

现在你必须符合Deque协议。首先，通过检查链接列表是否为空来实现isEmpty。这是一个O(1)操作。

var isEmpty: Bool { 
  list.isEmpty 
}

接下来，你需要一种方法，从 Deque 的前面或后面看值。

要从前面或后面peek(_:)元素，请检查列表的第一个和最后一个值。这是一个O(1)操作，因为你需要查看列表的头和尾。

现在你需要一种方法来将元素添加到Deque的前面或后面。

func enqueue(_ element: Element, to direction: Direction) -> Bool {

  switch direction { 
  case .front:
    list.prepend(element) 
  case .back:
    list.append(element) 
  }
  return true
}

将一个元素添加到Deque的前面或后面。

前面：将一个元素预置到列表的前面。在内部，链表将更新新节点作为链表的头。
后部：将一个元素追加到列表的后部。同样地，链表将更新新节点作为链表的尾部。

这些都是O(1)操作，因为你所要做的就是更新节点的头部或尾部的上一个和下一个指针。

现在我们有了添加元素的方法，那么删除元素的方法呢？

从 Deque 的前面或后面删除一个元素很简单。由于双链表引用了头和尾，你可以抓住它们的节点并断开节点的上一个和下一个指针。

前面。获取列表中的第一个（头）节点并将其删除。
后面。类似地，获得列表中最后一个（尾部）节点并将其删除。

与enqueue(_:)类似，这是一个O(1)操作。

最后，添加以下CustomStringConvertible，以便你可以测试你的Deque。

extension DequeDoubleLinkedList: CustomStringConvertible {

  public var description: String { 
    String(describing: list) 
  }
}

这就是建立一个Deque的全部内容! 添加下面的代码来测试你的实现。

let deque = DequeDoubleLinkedList<Int>()

deque.enqueue(1, to: .back) 
deque.enqueue(2, to: .back) 
deque.enqueue(3, to: .back) 
deque.enqueue(4, to: .back)

print(deque)

deque.enqueue(5, to: .front)

print(deque)

deque.dequeue(from: .back) 
deque.dequeue(from: .back) 
deque.dequeue(from: .back) 
deque.dequeue(from: .front) 
deque.dequeue(from: .front) 
deque.dequeue(from: .front)

print(deque)

上一章	目录	下一章