隊列像一個列表，您只能在最后插入新元素行您，并從最前面刪除元素剪廉。 這確保了您第一個入隊的元素也是您出隊的第一個元素斗蒋。 先來后到泉沾！

為什么需要這個跷究？ 好吧俊马，在許多算法中柴我，您希望在某個時間點將對象添加到臨時列表屯换，然后再次將其從此列表中刪除。 通常嘉抓，添加和刪除這些對象的順序很重要抑片。

隊列是先進先出的順序敞斋。 您首先插入的元素也是第一個出隊列的元素植捎。 這只是公平焰枢！ （一個非常相似的數(shù)據(jù)結(jié)構(gòu)济锄，棧霍转，是后入先出避消。）

例如沾谓，讓我們向隊列添加一個數(shù)字：

queue.enqueue(10)

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

queue.enqueue(3)

隊列現(xiàn)在是[10爬虱，3]跑筝。 再添加一個數(shù)字：

queue.enqueue(57)

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

queue.dequeue()

這里返回10笤虫，因為這是我們插入的第一個數(shù)字祖凫。 隊列現(xiàn)在是[3遭庶，57]罚拟。 每個元素的索引都向前移動了1赐俗。

queue.dequeue()

這返回3阻逮，下一個出列返回57叔扼，依此類推瓜富。 如果隊列為空，則dequeue返回nil价捧，或者在一些實現(xiàn)中提示出錯誤信息结蟋。

注意: 隊列并不總是最好的選擇嵌屎。 如果項目從列表中添加和刪除的順序不重要舔稀，您可以使用棧而不是隊列。 棧更簡單汞斧，更快粘勒。

代碼

這是一個在Swift中非常簡單的隊列實現(xiàn)。 它只是一個數(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
    }
}

這個隊列實現(xiàn)了功能仇穗，但它不是最佳的纹坐。

入隊是一個O（1）操作恰画，因為添加到數(shù)組的末尾總是需要相同的時間量跨晴，而不管數(shù)組的大小怀骤。 這是最好的蒋伦。

你可能想知道為什么將數(shù)據(jù)附加到數(shù)組是O（1），或者說是一個常量時間的操作。 這是因為Swift中的數(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)存。 向陣列中添加新元素將覆蓋下一個未使用的內(nèi)存：

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

這只是將存儲器從一個地方復(fù)制到另一個地方哗讥，即常量時間操作。

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

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

出列的操作則不同缚窿。要出列，我們要刪除數(shù)組開頭的元素焰扳，而不是結(jié)尾倦零。這總是一個O（n）操作，因為剩余的元素要在數(shù)組中向前移動一位吨悍。

在示例中扫茅，第一個元素“Ada”出列，“Steve”替換為“Ada”育瓜，“Tim”替換為“Steve”葫隙，“Grace”替換為“Tim”：

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

在內(nèi)存中移動移動所有元素總是O（n）操作。所以我們剛剛簡單的實現(xiàn)隊列爆雹，入列是高效的停蕉，但出列還有待改進...

一個更高效的隊列

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

思路是這樣的：當我們將一個元素出列時蚓挤，我們不會移動數(shù)組的其他元素磺送，而是將出列的位置標記為空。在“Ada”出列之后灿意，數(shù)組是：

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

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

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

這些空的內(nèi)存永遠不會被使用，是對空間的浪費缤剧。每隔一段時間馅袁，你可以將剩余的元素向前移動：

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

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

現(xiàn)在數(shù)組中存儲的是可選類型T?，而不是T抵窒，因為我們要標記數(shù)組元素為空弛针。head變量是空元素的索引。

大多數(shù)的新代碼在dequeue()中李皇。一個元素出列時削茁，首先將array[head]的值設(shè)為nil，達到從數(shù)組中刪除改元素的目的掉房。然后我們讓head+1茧跋，使下一個元素會在隊列的最前面。

出列前：

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

出列后:

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

這就像一個奇怪的收銀臺：人們排隊結(jié)賬但不向收銀臺走過去卓囚，而是收銀臺移動厌衔。

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

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

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

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

在playground里測試，代碼：

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

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

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

替換為這行代碼：

    if head > 2 {

你再出隊一個對象巧鸭，數(shù)組就是這樣的：

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

隊列前面的nil對象被刪除，不再浪費空間麻捻。 新版本的隊列比第一個更復(fù)雜纲仍，但是出隊也是一個O（1）操作，因為我們對于如何使用數(shù)組有了更多的理解贸毕。

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

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