隊(duì)列像一個(gè)列表，您只能在最后插入新元素，并從最前面刪除元素。 這確保了您第一個(gè)入隊(duì)的元素也是您出隊(duì)的第一個(gè)元素。 先來后到！

為什么需要這個(gè)？ 好吧，在許多算法中，您希望在某個(gè)時(shí)間點(diǎn)將對(duì)象添加到臨時(shí)列表，然后再次將其從此列表中刪除。 通常，添加和刪除這些對(duì)象的順序很重要。

隊(duì)列是先進(jìn)先出的順序。 您首先插入的元素也是第一個(gè)出隊(duì)列的元素。 這只是公平！ （一個(gè)非常相似的數(shù)據(jù)結(jié)構(gòu)，棧，是后入先出。）

例如，讓我們向隊(duì)列添加一個(gè)數(shù)字：

queue.enqueue(10)

隊(duì)列現(xiàn)在是[10]。 將下一個(gè)數(shù)字添加到隊(duì)列：

queue.enqueue(3)

隊(duì)列現(xiàn)在是[10，3]。 再添加一個(gè)數(shù)字：

queue.enqueue(57)

隊(duì)列現(xiàn)在是[10，3，57]。 讓我們讓隊(duì)列第一個(gè)元素出列：

queue.dequeue()

這里返回10，因?yàn)檫@是我們插入的第一個(gè)數(shù)字。 隊(duì)列現(xiàn)在是[3，57]。 每個(gè)元素的索引都向前移動(dòng)了1。

queue.dequeue()

這返回3，下一個(gè)出列返回57，依此類推。 如果隊(duì)列為空，則dequeue返回nil，或者在一些實(shí)現(xiàn)中提示出錯(cuò)誤信息。

注意: 隊(duì)列并不總是最好的選擇。 如果項(xiàng)目從列表中添加和刪除的順序不重要，您可以使用棧而不是隊(duì)列。 棧更簡單，更快。

代碼

這是一個(gè)在Swift中非常簡單的隊(duì)列實(shí)現(xiàn)。 它只是一個(gè)數(shù)組的包裝，可以讓你入列，出列和查看最前面的元素：

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 func peek() -> T? {
        return array.first
    }
}

這個(gè)隊(duì)列實(shí)現(xiàn)了功能，但它不是最佳的。

入隊(duì)是一個(gè)O（1）操作，因?yàn)樘砑拥綌?shù)組的末尾總是需要相同的時(shí)間量，而不管數(shù)組的大小。 這是最好的。

你可能想知道為什么將數(shù)據(jù)附加到數(shù)組是O（1），或者說是一個(gè)常量時(shí)間的操作。 這是因?yàn)镾wift中的數(shù)組在結(jié)尾總是有一些空間。 如果我們做如下操作：

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

那么數(shù)組看起來像這樣：

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

其中xxx是保留但尚未填充的內(nèi)存。 向陣列中添加新元素將覆蓋下一個(gè)未使用的內(nèi)存：

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

這只是將存儲(chǔ)器從一個(gè)地方復(fù)制到另一個(gè)地方，即常量時(shí)間操作。

當(dāng)然，在陣列的末端只有有限數(shù)量的這種未使用的內(nèi)存。 當(dāng)最后一個(gè)xxx被使用，并且您想要添加另一個(gè)元素，數(shù)組需要調(diào)整大小，以騰出更多的空間。

數(shù)組要調(diào)整大小，需要?jiǎng)?chuàng)建心數(shù)組，分配新的內(nèi)存空間，把現(xiàn)有數(shù)組的數(shù)據(jù)復(fù)制到新數(shù)組中。這是一個(gè)O（n）操作，相對(duì)比較慢。但他只是每隔一段時(shí)間發(fā)生一次，因此將新元素添加到數(shù)組末尾的平均時(shí)間是O（1）。

出列的操作則不同。要出列，我們要?jiǎng)h除數(shù)組開頭的元素，而不是結(jié)尾。這總是一個(gè)O（n）操作，因?yàn)槭Ｓ嗟脑匾跀?shù)組中向前移動(dòng)一位。

在示例中，第一個(gè)元素“Ada”出列，“Steve”替換為“Ada”，“Tim”替換為“Steve”，“Grace”替換為“Tim”：

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

在內(nèi)存中移動(dòng)移動(dòng)所有元素總是O（n）操作。所以我們剛剛簡單的實(shí)現(xiàn)隊(duì)列，入列是高效的，但出列還有待改進(jìn)...

一個(gè)更高效的隊(duì)列

為了使出列更高效，我們可以使用同樣的技巧，在數(shù)組前面保留一些額外的可用空間。 我們不得不自己編寫這個(gè)代碼，因?yàn)閮?nèi)置的Swift數(shù)組不支持這種功能。

思路是這樣的：當(dāng)我們將一個(gè)元素出列時(shí)，我們不會(huì)移動(dòng)數(shù)組的其他元素，而是將出列的位置標(biāo)記為空。在“Ada”出列之后，數(shù)組是：

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

在“Steve”出列之后，數(shù)組是：

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

這些空的內(nèi)存永遠(yuǎn)不會(huì)被使用，是對(duì)空間的浪費(fèi)。每隔一段時(shí)間，你可以將剩余的元素向前移動(dòng)：

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

這樣在內(nèi)存中移動(dòng)元素的過程是O（n）操作。但它很少發(fā)生，所以平均時(shí)間是O（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 func peek() ->T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

現(xiàn)在數(shù)組中存儲(chǔ)的是可選類型T?，而不是T，因?yàn)槲覀円獦?biāo)記數(shù)組元素為空。head變量是空元素的索引。

大多數(shù)的新代碼在dequeue()中。一個(gè)元素出列時(shí)，首先將array[head]的值設(shè)為nil，達(dá)到從數(shù)組中刪除改元素的目的。然后我們讓head+1，使下一個(gè)元素會(huì)在隊(duì)列的最前面。

出列前：

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

出列后:

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

這就像一個(gè)奇怪的收銀臺(tái)：人們排隊(duì)結(jié)賬但不向收銀臺(tái)走過去，而是收銀臺(tái)移動(dòng)。

當(dāng)然，如果我們從來沒有刪除隊(duì)列前面那些空的部分，我們不斷的入列和出列元素，那么對(duì)列將繼續(xù)增長。因此，要定期修剪數(shù)組，我們執(zhí)行以下操作：

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

如果空白的長度站到整個(gè)數(shù)組的25%以上，我們就把空白的部分去掉。但是如果數(shù)組元素?cái)?shù)量不多，我們也不想一直修剪它。所以至少有50個(gè)元素才會(huì)去修剪它。

注意: 這只是一個(gè)例子，你需要根據(jù)你應(yīng)用的實(shí)際情況來決定什么情況下修剪數(shù)組。

在playground里測(cè)試，代碼：

var q = Queue<String>()
q.array                   // [] empty array

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2

測(cè)試修剪數(shù)組，把這行代碼：

    if array.count > 50 && percentage > 0.25 {

替換為這行代碼：

    if head > 2 {

你再出隊(duì)一個(gè)對(duì)象，數(shù)組就是這樣的：

q.dequeue()         // "Tim"
q.array             // [{Some "Grace"}]
q.count             // 1

隊(duì)列前面的nil對(duì)象被刪除，不再浪費(fèi)空間。 新版本的隊(duì)列比第一個(gè)更復(fù)雜，但是出隊(duì)也是一個(gè)O（1）操作，因?yàn)槲覀儗?duì)于如何使用數(shù)組有了更多的理解。

作者：Matthijs Hollemans -- Swift算法俱樂部

原文鏈接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Queue