9.队列的挑战¶

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

挑战1：堆栈与队列¶

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

挑战2：分步图示¶

给出以下队列：

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

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

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

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

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

挑战3：轮到谁了？¶

打开启动项目，导航到挑战3的游戏页面，开始。

想象一下，你正在和你的朋友玩大富翁游戏。问题是，每个人总是忘记该轮到谁了创建一个大富翁组织者，总是告诉你该轮到谁了。下面是一个你可以遵守的协议：

protocol BoardGameManager {

  associatedtype Player
  mutating func nextPlayer() -> Player?
}

挑战4：反向队列¶

导航到挑战4的游戏页面开始。

实现一种方法来逆转队列的内容。

Tips

Stack数据结构已包含在Sources文件夹中。

extension QueueArray {

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

挑战5：双端队列¶

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

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

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

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

注意：¶

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

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

enum Direction {
  case front
  case back
}

protocol Deque {
  associatedtype Element
  var isEmpty: Bool { get }
  func peek(from direction: Direction) -> Element?
  mutating func enqueue(_ element: Element,
                        to direction: Direction) -> Bool
  mutating func dequeue(from direction: Direction) -> Element?
}

解决方案¶

挑战1的解决方案¶

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

队列的例子：

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

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

堆栈实例：

Stack of plates：把盘子放在彼此的上面，每次使用盘子时都把最上面的盘子拿开。这不是比抓取底部的那个更容易吗？
Undo functionality：想象一下在键盘上打字的情景。点击Ctrl-Z就可以撤消你最近输入的文字。

挑战2的解决方案¶

`Array`¶

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

链接列表¶

环形缓冲器¶

双层叠加¶

挑战3的解决方案¶

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

extension QueueArray: BoardGameManager {

  public typealias Player = T

  public mutating func nextPlayer() -> T? {
    guard let person = dequeue() else { // 1
      return nil
    }
    enqueue(person) // 2
    return person // 3
  }
}

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

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

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

var queue = QueueArray<String>()
queue.enqueue("Vincent")
queue.enqueue("Remel")
queue.enqueue("Lukiih")
queue.enqueue("Allison")
print(queue)

print("===== boardgame =======")
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)
queue.nextPlayer()
print(queue)

挑战4的解决方案¶

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

extension QueueArray {

  func reversed() -> QueueArray {
    var queue = self // 1
    var stack = Stack<T>() // 2
    while let element = queue.dequeue() { // 3
      stack.push(element)
    }
    while let element = stack.pop() { // 4
      queue.enqueue(element)
    }
    return queue // 5
  }
}

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

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

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

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

测试一下吧：

var queue = QueueArray<String>()
queue.enqueue("1")
queue.enqueue("21")
queue.enqueue("18")
queue.enqueue("42")

print("before: \(queue)")
print("after: \(queue.reversed())")

挑战5的解决方案¶

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

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

class DequeDoubleLinkedList<Element>: Deque {

  private var list = DoublyLinkedList<Element>()
  public init() {}

}

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

var isEmpty: Bool {
  list.isEmpty
}

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

func peek(from direction: Direction) -> Element? {
  switch direction {
  case .front:
    return list.first?.value
  case .back:
    return list.last?.value
  }
}

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

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

func enqueue(_ element: Element, to direction: Direction) -> Bool {
  switch direction {
  case .front:
    list.prepend(element)
  case .back:
    list.append(element)
  }
  return true
}

在Deque的前面或后面添加一个元素：

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

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

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

func dequeue(from direction: Direction) -> Element? {
  let element: Element?
  switch direction {
  case .front:
    guard let first = list.first else { return nil }
    element = list.remove(first)
  case .back:
    guard let last = list.last else { return nil }
    element = list.remove(last)
  }
  return element
}

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

Front：获取列表中的第一个（head）节点，并将其删除。
Back：类似地，得到列表中最后一个(tail)节点并将其删除。

与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)