Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
Deque.playground
Deque-Optimized.swift
Deque-Simple.swift
README.markdown
README_en.markdown

README.markdown

双端队列(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()       // 5

Deque的这种实现很简单但效率不高。几个操作是 O(n),特别是enqueueFront()dequeue()。这个实现只是为了说明双端队列的作用原理。

更高效的版本

dequeue()enqueueFront()的时间复杂度是O(n),原因是它们在数组的前面(开始)工作。如果删除数组前面的元素,那么所有剩余的元素都需要在内存中移位。

假设双端队列的数组包含以下元素:

[ 1, 2, 3, 4 ]

然后dequeue()将从数组中删除1,元素234将向前移动一个位置:

[ 2, 3, 4 ]

这是一个**O(n)**操作,因为所有数组元素都需要在内存中移动一个位置。

同样,在数组的前面插入一个元素也是昂贵的,因为它要求所有其他元素必须向后移动一个位置。 因此enqueueFront(5)会将数组更改为:

[ 5, 2, 3, 4 ]

首先,将元素234在内存中向后移动一个位置,然后将新元素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 ]
                             |
                             head

enqueueFront(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%。

注意: 通过将capacityoriginalCapacity进行比较,双端队列将至少保持其原始容量。

例如:

[ 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

通过这种方式,我们可以在前面的快速入队、出队与保持合理的内存空间之间取得平衡。

注意: 我们不对非常小的数组执行修剪,仅保存几个字节的内存是没有必要的。

扩展阅读

其它可以实现双端队列的方法:双向链表环形缓冲区,或方法相反的两个

双端队列功能齐全的Swift实现

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron