聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過(guò)來(lái)曙旭，為方便大家閱讀茧球。如果英語(yǔ)閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂(lè)部查看所有原文，以便快速學(xué)習(xí)危喉。作者同時(shí)也在學(xué)習(xí)中宋渔，歡迎交流
排隊(duì)序列就是一個(gè)你只能在隊(duì)伍的最后面加入新的值，從最前面取出舊的值的一串序列辜限。這樣的機(jī)制保證了最早進(jìn)入序列的值皇拣，同時(shí)也會(huì)是最早出來(lái)的，就像我們平時(shí)排隊(duì)辦理業(yè)務(wù)一樣薄嫡，先到先服務(wù)氧急！
為什么我們需要這樣的機(jī)制呢？實(shí)際上毫深，很多算法都會(huì)出現(xiàn)類似情況吩坝，在某一時(shí)刻你只想添加某些元素到一個(gè)臨時(shí)列表里，然后過(guò)一會(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ù)字〗盐現(xiàn)在隊(duì)列的內(nèi)容變?yōu)椋?，57］妙痹。
queue.dequeue
這一次我們得到的返回值為3铸史，我們可以繼續(xù)移除隊(duì)列的數(shù)據(jù)。如果隊(duì)列變?yōu)榭涨右粒瞥匠谭祷亟Y(jié)果為nil琳轿，在一些執(zhí)行語(yǔ)句里面會(huì)返回錯(cuò)誤信。
注意： 通常情況下隊(duì)列并不是最好的選擇。如果對(duì)于一個(gè)數(shù)組來(lái)說(shuō)崭篡，元素的添加和移除過(guò)程不是很重要的話挪哄，這里我們建議使用堆棧Stack會(huì)是更好的選擇，因?yàn)?a href="http://www.reibang.com/p/3364cb39c962" target="_blank">堆棧Stack更簡(jiǎn)單也更高效媚送。
代碼
在swift中中燥，隊(duì)列很容易創(chuàng)建。簡(jiǎn)單的說(shuō)它就是對(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ì)列過(guò)程是一個(gè)O(1)運(yùn)算過(guò)程涵防，因?yàn)槊恳淮卧陉?duì)列的最后一位插入新的數(shù)值消耗的時(shí)間是固定的闹伪，與隊(duì)列當(dāng)前的大小無(wú)關(guān)，這是隊(duì)列算法最棒的地方壮池。
你可能會(huì)好奇偏瓤，為什么添加數(shù)值到數(shù)組里面是一個(gè)O(1)運(yùn)算過(guò)程？因?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ì)重寫(xiě)最近的一個(gè)xxx证舟。
["Ada", "Steve", "Tim", "Grace", xxx , xxx]
這就相當(dāng)于將一部分內(nèi)存從一個(gè)地方復(fù)制到另一個(gè)地方，這是一個(gè)恒定運(yùn)算過(guò)程窗骑。
當(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)過(guò)程互订，所以這個(gè)過(guò)程有點(diǎn)慢吱肌。但是，因?yàn)檫@種情況偶爾發(fā)生仰禽，所以總體上來(lái)說(shuō)氮墨，隊(duì)列在添加新的數(shù)值到數(shù)組里的過(guò)程纺蛆，所消耗的平均時(shí)間仍然接近O(1).
至于隊(duì)列取出過(guò)程，就不太一樣了规揪。在取出數(shù)值的過(guò)程中桥氏，我們移除的是隊(duì)列最前端的數(shù)值，而不是最末端猛铅。這個(gè)過(guò)程基本上一直是O(n)運(yùn)算因?yàn)樗枰獙⑹Ｓ嗟臄?shù)據(jù)在內(nèi)存上進(jìn)行保留和移動(dòng)字支。
在我們的例子中，取出第一個(gè)元素"Ada"其實(shí)是將"Steve"復(fù)制到"Ada"的位置奸忽，同時(shí)"Tim"被復(fù)制到原來(lái)"Steve"的位置堕伪，"Grace"被復(fù)制到運(yùn)來(lái)"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ù)值的過(guò)程是簡(jiǎn)單高效的，但是取出的過(guò)程卻有待提高疙筹。
更有效的隊(duì)列算法
為了讓隊(duì)列算法更加有效富俄，我們可以在預(yù)留內(nèi)存位置上做文章，但是這次我們選擇在隊(duì)列的最前頭進(jìn)行內(nèi)存預(yù)留而咆。這里我們需要自己寫(xiě)代碼去實(shí)現(xiàn)霍比，因?yàn)閟wift本身的邏輯并沒(méi)有支持我們提出來(lái)的想法。
想法如下：當(dāng)我們需要從隊(duì)列中取出元素的時(shí)候暴备，我們不做數(shù)組元素的移動(dòng)（慢）悠瞬，而是記住這個(gè)元素的位置，并且把它重寫(xiě)為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)整過(guò)程包含了內(nèi)存移動(dòng)对省，所以這里是一個(gè)O(n)運(yùn)算蝗拿。但是因?yàn)樗皇桥紶柊l(fā)生，所以蒿涎，總體來(lái)說(shuō)哀托，取出過(guò)程也變成了O(1)運(yùn)算。
一下代碼實(shí)現(xiàn)了上述所說(shuō)的新隊(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ě)為空劳秋，所以現(xiàn)在這里的數(shù)組儲(chǔ)存對(duì)象類型為T?仓手，而不是T胖齐。變量head是數(shù)組里面最前面的對(duì)象的索引。
對(duì)比原來(lái)的代碼嗽冒，我們對(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)然贬蛙，如果我們從來(lái)不將前頭的這些空點(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ù)組大小超過(guò)50的前提下岔擂，我們計(jì)算了空點(diǎn)在數(shù)組中所占的比例，當(dāng)占比超過(guò)25%浪耘，我們就對(duì)數(shù)組進(jìn)行一次調(diào)整乱灵，避免內(nèi)存浪費(fèi)。這里的50可以自己調(diào)整七冲。
