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

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

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

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

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

queue.enqueue(10)

現(xiàn)在隊(duì)列的內(nèi)容為 [ 10 ]。 我們?cè)俜胚M(jìn)下一個(gè)數(shù)字：

queue.enqueue(3)

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

queue.enqueue(57)

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

queue.dequeue

這里我們得到的返回值為10，因?yàn)樗俏覀冏詈蠓胚M(jìn)去的數(shù)字?，F(xiàn)在隊(duì)列的內(nèi)容變?yōu)椋?，57］。

queue.dequeue

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

注意： 通常情況下隊(duì)列并不是最好的選擇。如果對(duì)于一個(gè)數(shù)組來說，元素的添加和移除過程不是很重要的話，這里我們建議使用堆棧Stack會(huì)是更好的選擇，因?yàn)?a href="http://m.itdecent.cn/p/3364cb39c962" target="_blank">堆棧Stack更簡(jiǎn)單也更高效。

代碼

在swift中，隊(duì)列很容易創(chuàng)建。簡(jiǎn)單的說它就是對(duì)一個(gè)數(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 
    }
}

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

插入隊(duì)列過程是一個(gè)O(1)運(yùn)算過程，因?yàn)槊恳淮卧陉?duì)列的最后一位插入新的數(shù)值消耗的時(shí)間是固定的，與隊(duì)列當(dāng)前的大小無關(guān)，這是隊(duì)列算法最棒的地方。

你可能會(huì)好奇，為什么添加數(shù)值到數(shù)組里面是一個(gè)O(1)運(yùn)算過程？因?yàn)樵趕wift里，在一個(gè)數(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ù)值會(huì)重寫最近的一個(gè)xxx。

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

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

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

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

至于隊(duì)列取出過程，就不太一樣了。在取出數(shù)值的過程中，我們移除的是隊(duì)列最前端的數(shù)值，而不是最末端。這個(gè)過程基本上一直是O(n)運(yùn)算因?yàn)樗枰獙⑹Ｓ嗟臄?shù)據(jù)在內(nèi)存上進(jìn)行保留和移動(dòng)。

在我們的例子中，取出第一個(gè)元素"Ada"其實(shí)是將"Steve"復(fù)制到"Ada"的位置，同時(shí)"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)行移動(dòng)一直是O(n)運(yùn)算。所以在執(zhí)行隊(duì)列算法時(shí)候，插入數(shù)值的過程是簡(jiǎn)單高效的，但是取出的過程卻有待提高。

更有效的隊(duì)列算法

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

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

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

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

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

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

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

這個(gè)調(diào)整過程包含了內(nèi)存移動(dòng)，所以這里是一個(gè)O(n)運(yùn)算。但是因?yàn)樗皇桥紶柊l(fā)生，所以，總體來說，取出過程也變成了O(1)運(yùn)算。

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

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]
    }
  }
}

因?yàn)槲覀冃枰獙?shù)組的元素重寫為空，所以現(xiàn)在這里的數(shù)組儲(chǔ)存對(duì)象類型為T?，而不是T。變量head是數(shù)組里面最前面的對(duì)象的索引。

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

取出前：

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

取出后：

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

當(dāng)然，如果我們從來不將前頭的這些空點(diǎn)移除掉，而是不停的添加新的數(shù)值，移除前端的數(shù)值，那數(shù)組的大小將會(huì)不斷變大，消耗的內(nèi)存跟著增加。所以我們必須周期性的對(duì)數(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的前提下，我們計(jì)算了空點(diǎn)在數(shù)組中所占的比例，當(dāng)占比超過25%，我們就對(duì)數(shù)組進(jìn)行一次調(diào)整，避免內(nèi)存浪費(fèi)。這里的50可以自己調(diào)整。