聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來，為方便大家閱讀。如果英語閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂部查看所有原文，以便快速學(xué)習(xí)。作者同時也在學(xué)習(xí)中，歡迎交流

排隊序列就是一個你只能在隊伍的最后面加入新的值，從最前面取出舊的值的一串序列。這樣的機(jī)制保證了最早進(jìn)入序列的值，同時也會是最早出來的，就像我們平時排隊辦理業(yè)務(wù)一樣，先到先服務(wù)！

為什么我們需要這樣的機(jī)制呢？實際上，很多算法都會出現(xiàn)類似情況，在某一時刻你只想添加某些元素到一個臨時列表里，然后過一會兒又將它們移除出去。這時候，你添加或者移除元素的順序會影響整個算法。

隊列可以提供先進(jìn)先出的順序（FIFO）。它每一次移除的元素，都是你最先放進(jìn)去的元素。這里有一個非常類似的數(shù)據(jù)結(jié)構(gòu)，堆棧Stack，屬于后進(jìn)先出的順序（LIFO）。

比如，我們將一個數(shù)字放進(jìn)隊列里。

queue.enqueue(10)

現(xiàn)在隊列的內(nèi)容為 [ 10 ]。 我們再放進(jìn)下一個數(shù)字：

queue.enqueue(3)

現(xiàn)在隊列的內(nèi)容變?yōu)?[ 10, 3 ]。我們繼續(xù)放入新的數(shù)字：

queue.enqueue(57)

現(xiàn)在隊列的內(nèi)容變?yōu)椋?0，3，57］。這回，我們將隊列里最先端的數(shù)字移除：

queue.dequeue

這里我們得到的返回值為10，因為它是我們最后放進(jìn)去的數(shù)字?，F(xiàn)在隊列的內(nèi)容變?yōu)椋?，57］。

queue.dequeue

這一次我們得到的返回值為3，我們可以繼續(xù)移除隊列的數(shù)據(jù)。如果隊列變?yōu)榭?，移除方程返回結(jié)果為nil，在一些執(zhí)行語句里面會返回錯誤信。

注意： 通常情況下隊列并不是最好的選擇。如果對于一個數(shù)組來說，元素的添加和移除過程不是很重要的話，這里我們建議使用堆棧Stack會是更好的選擇，因為堆棧Stack更簡單也更高效。

代碼

在swift中，隊列很容易創(chuàng)建。簡單的說它就是對一個數(shù)組進(jìn)行包裝，讓你能夠?qū)?shù)組添加，移除，查看數(shù)據(jù)。

public struct Queue<T> { 
    fileprivate 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 dequeue() -> T? { 
        if isEmpty {
           return nil 
        } else { 
           return array.removeFirst() 
        }
     } 
    public var front: T? { 
        return array.first 
    }
}

隊列算法運(yùn)算效率良好，但大多數(shù)情況下并不是最優(yōu)選擇。

插入隊列過程是一個O(1)運(yùn)算過程，因為每一次在隊列的最后一位插入新的數(shù)值消耗的時間是固定的，與隊列當(dāng)前的大小無關(guān)，這是隊列算法最棒的地方。

你可能會好奇，為什么添加數(shù)值到數(shù)組里面是一個O(1)運(yùn)算過程？因為在swift里，在一個數(shù)組的最末尾，swift都預(yù)留了一些空位備用。比如我們執(zhí)行以下代碼：

var  queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")

我們得到的數(shù)組應(yīng)該是這樣的：

["Ada", "Steve", "Tim", xxx, xxx , xxx]

這里的xxx是尚未填入數(shù)值的預(yù)留內(nèi)存。添加新的數(shù)值會重寫最近的一個xxx。

["Ada", "Steve", "Tim", "Grace", xxx , xxx]

這就相當(dāng)于將一部分內(nèi)存從一個地方復(fù)制到另一個地方，這是一個恒定運(yùn)算過程。

當(dāng)然，數(shù)組中的xxx個數(shù)是有限的。當(dāng)最后一個xxx被使用，你還想繼續(xù)添加數(shù)值，這個數(shù)組就需要重新調(diào)整大小，獲取更多的空間。

調(diào)整大小包括獲取新的內(nèi)存，同時將現(xiàn)有的數(shù)據(jù)復(fù)制到新的數(shù)組里面。這是一個O(n)過程，所以這個過程有點慢。但是，因為這種情況偶爾發(fā)生，所以總體上來說，隊列在添加新的數(shù)值到數(shù)組里的過程，所消耗的平均時間仍然接近O(1).

至于隊列取出過程，就不太一樣了。在取出數(shù)值的過程中，我們移除的是隊列最前端的數(shù)值，而不是最末端。這個過程基本上一直是O(n)運(yùn)算因為它需要將剩余的數(shù)據(jù)在內(nèi)存上進(jìn)行保留和移動。

在我們的例子中，取出第一個元素"Ada"其實是將"Steve"復(fù)制到"Ada"的位置，同時"Tim"被復(fù)制到原來"Steve"的位置，"Grace"被復(fù)制到運(yùn)來"Tim"的位置:

取出前      ["Ada", "Steve", "Tim", "Grace", xxx , xxx]
                                 /        /            /
                               /        /            / 
                             /        /            /
                           /        /            /
取出后      ["Steve", "Tim", "Grace", xxx , xxx，xxx]

將所有數(shù)據(jù)在內(nèi)存上進(jìn)行移動一直是O(n)運(yùn)算。所以在執(zhí)行隊列算法時候，插入數(shù)值的過程是簡單高效的，但是取出的過程卻有待提高。

更有效的隊列算法

為了讓隊列算法更加有效，我們可以在預(yù)留內(nèi)存位置上做文章，但是這次我們選擇在隊列的最前頭進(jìn)行內(nèi)存預(yù)留。這里我們需要自己寫代碼去實現(xiàn)，因為swift本身的邏輯并沒有支持我們提出來的想法。

想法如下：當(dāng)我們需要從隊列中取出元素的時候，我們不做數(shù)組元素的移動（慢），而是記住這個元素的位置，并且把它重寫為xxx（快）。在取出"Ada"之后，數(shù)組內(nèi)容如下：

[xxx, "Steve", "Tim", "Grace", xxx , xxx]

我們繼續(xù)取出"Steve"，數(shù)組變成：

[xxx, xxx, "Tim", "Grace", xxx , xxx]

因為在隊列算法中，最前端的預(yù)留內(nèi)存永遠(yuǎn)不會被用到，為了防止內(nèi)存浪費(fèi)，我們可以偶爾對數(shù)組重新進(jìn)行大小調(diào)整，即刪除前端預(yù)留內(nèi)存，將"Tim"等元素往前放：

["Tim", "Grace", xxx , xxx]

這個調(diào)整過程包含了內(nèi)存移動，所以這里是一個O(n)運(yùn)算。但是因為它只是偶爾發(fā)生，所以，總體來說，取出過程也變成了O(1)運(yùn)算。

一下代碼實現(xiàn)了上述所說的新隊列算法：

public struct Queue<T>{
   fileprivate var array = [T?]()
   fileprivate var head = 0

   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 dequeue() -> T? {
    guard head < array.count, let element = array[head] else { return nil }

    array[head] = nil
    head += 1

    let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

    return element
  }

  public var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

因為我們需要將數(shù)組的元素重寫為空，所以現(xiàn)在這里的數(shù)組儲存對象類型為T?，而不是T。變量head是數(shù)組里面最前面的對象的索引。

對比原來的代碼，我們對dequeuq()進(jìn)行了修改。當(dāng)我們?nèi)〕鰯?shù)值的時候，我們首先將array[head]改為nil，同時將head的數(shù)值增加，保證其表示下一個元素的索引。

取出前：

["Ada", "Steve", "Tim", "Grace", xxx , xxx]
  head

取出后：

[xxx, "Steve", "Tim", "Grace", xxx , xxx]
        head

當(dāng)然，如果我們從來不將前頭的這些空點移除掉，而是不停的添加新的數(shù)值，移除前端的數(shù)值，那數(shù)組的大小將會不斷變大，消耗的內(nèi)存跟著增加。所以我們必須周期性的對數(shù)組進(jìn)行調(diào)整。代碼為:

    let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

在數(shù)組大小超過50的前提下，我們計算了空點在數(shù)組中所占的比例，當(dāng)占比超過25%，我們就對數(shù)組進(jìn)行一次調(diào)整，避免內(nèi)存浪費(fèi)。這里的50可以自己調(diào)整。