原文鏈接： Swift Algorithm Club: Swift Queue Data Structure
翻譯： coderJoey
通過本教程伟件，你將學(xué)習(xí)怎樣用Swift3實現(xiàn)隊列數(shù)據(jù)結(jié)構(gòu)富拗。隊列是一種非常流行的數(shù)據(jù)結(jié)構(gòu)慌申，而且用Swift實現(xiàn)也相當(dāng)簡單饲化。
開始吧
隊列 很像排隊吃引，先到的排在前面后來的排在隊伍的后面灸芳。這能保證第一個入列的元素將第一個出列痹仙。
這種數(shù)據(jù)結(jié)構(gòu)有什么用呢期升？在很多算法中惊奇，例如某個時刻你想添加一些新的對象到一個臨時列表中，然后不就之后你需要刪除掉這些對象播赁，添加和刪除這些對象的順序有時候是很重要的颂郎。
隊列的順序是FIFO（ first-in first-out order：先進先出），也就是最先入列的元素最先被移除容为。（這非常像數(shù)據(jù)結(jié)構(gòu)堆棧（LIFO:后進先出））
例子
理解隊列最好的方式就是看它是如何工作的乓序。
假設(shè)你現(xiàn)在有一個隊列寺酪，下面是如何添加一個數(shù)字：
queue.enqueue(10)
隊列現(xiàn)在變成了[10]，然后你再添加一個數(shù)字：
queue.enqueue(3)
隊列變成了[10,3]替劈，然后你又添加一個數(shù)字：
queue.enqueue(57)
隊列變成了[10,3,57]寄雀，你現(xiàn)在將隊列的最前面的元素刪掉：
queue.dequeue()
這個方法將返回第一次插入的數(shù)字10，隊列變成了[3,57]抬纸。每個元素都將向前移一位咙俩。
queue.dequeue()
這個方法將返回3，下一次dequeue將返回57湿故。如果這個隊列是空的阿趁，操作出列方法將返回nil。
實現(xiàn)隊列
在本節(jié)中坛猪，你將實現(xiàn)一個存儲Int類型的簡單通用隊列脖阵。
首先先下載queue starter project。playground項目中包含了一個空的Queue：
public struct Queue {
}
playground中也包含了一個鏈表類 LinkedList墅茉，你可以在View\Project Navigators\Show Project Navigator中打開Sources\LinkedList（或者用組合鍵command+1）
想知道鏈表是如何工作的命黔？點擊這里查看譯文教程，或者點擊Swift linked list 查看原文就斤。
入列
隊列需要一個enqueue函數(shù)進行入列操作悍募。你將使用啟動項目中包含的鏈表來實現(xiàn)隊列。 在花括號之間添加以下內(nèi)容：
// 1
fileprivate var list = LinkedList()
// 2
public mutating func enqueue(_ element: Int) {
list.append(element)
}
上面代碼做了什么：
添加了私有的變量LinkedList洋机，用來存儲隊列的元素坠宴。
添加了一個入列函數(shù)。該函數(shù)會使LinkedList內(nèi)容發(fā)生改變绷旗，所以你需要在方法前添加mutating關(guān)鍵字喜鼓。
出列
隊列也需要一個dequeue函數(shù)進行出列操作。
// 1
public mutating func dequeue() -> Int? {
// 2
guard !list.isEmpty, let element = list.first else { return nil }
list.remove(element)
return element.value
}
上面代碼做了什么：
添加一個返回值為隊列第一個元素的dequeue方法衔肢，返回值類型nullable是為了處理隊列為空的情況庄岖。該函數(shù)會使LinkedList內(nèi)容發(fā)生改變，所以你需要在方法前添加mutating關(guān)鍵字角骤。
用guard語句來處理隊列為空的情況隅忿。如果隊列為空。guard將執(zhí)行else語句塊代碼邦尊。
查看
隊列也需要一個peek函數(shù)來查看隊列的第一個元素硼控。與dequeue不同的是你不能將這個元素從隊列中移除掉。
public func peek() -> Int? {
return list.first?.value
}
是否為空
隊列是可以為空的胳赌。你需要在 LinkedList下邊添加一個判斷隊列是否為空的isEmpty屬性。
public var isEmpty: Bool {
return list.isEmpty
}
打印隊列
現(xiàn)在我們使用下這個隊列匙隔。在Queue實現(xiàn)下面疑苫，我們添加如下代碼：
var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
定義隊列后,我們試著將鏈表的內(nèi)容打印到控制臺:
print(queue)
你可以使用組合鍵 Command-Shift-Y喚起控制臺。然而你看到的打印結(jié)果是：
Queue
這顯然沒什么用。要使打印的字符串更具可讀性捍掺，你需要讓LinkedList遵守CustomStringConvertable 協(xié)議撼短。我們將下面的代碼添加到Queue 類的下面。
// 1
extension Queue: CustomStringConvertible {
// 2
public var description: String {
// 3
return list.description
}
}
上面代碼做了什么：
你聲明了一個 Queue 類的擴展挺勿，而且遵守了CustomStringConvertable 協(xié)議曲横。這個協(xié)議希望你實現(xiàn)String類型的description，這里的description為計算型屬性（computed property）不瓶。
定義description屬性禾嫉，它的返回類型是String，而且是只讀的蚊丐。
將LinkedList的描述屬性作為返回值熙参。
現(xiàn)在打印Queue的內(nèi)容，你將看到不錯的結(jié)果：
"[10, 3, 57]"
泛型實現(xiàn)
到目前為止麦备，你已經(jīng)實現(xiàn)了一個存儲Int值的通用隊列孽椰， 并提供了在隊列類中查看，入列和出列的功能函數(shù)凛篙。
在本節(jié)中黍匾，我們將使用泛型來實現(xiàn)抽象類型的隊列。
如下更新Queue類：
// 1
public struct Queue<T> {
// 2
fileprivate var list = LinkedList<T>()
public var isEmpty: Bool {
return list.isEmpty
}
// 3
public mutating func enqueue(_ element: T) {
list.append(element)
}
// 4
public mutating func dequeue() -> T? {
guard !list.isEmpty, let element = list.first else { return nil }
list.remove(element)
return element.value
}
// 5
public func peek() -> T? {
return list.first?.value
}
}
代碼解析：
- 將Queue類的聲明更改為泛型T呛梆。
- 你的目的是要讓Queue類存儲任何類型锐涯，所以要將LinkedList的類型定義為泛型T。
- 將enqueue類定義的類型更改為泛型T削彬。
- 將dequeue類定義的類型更改為泛型T全庸。
- 將peek類定義的類型更改為泛型T。
修改測試代碼：
var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
當(dāng)然你還可以測試其他不同的類型：
var queue2 = Queue<String>()
queue2.enqueue("mad")
queue2.enqueue("lad")
if let first = queue2.dequeue() {
print(first)
}
print(queue2)
何去何從
希望你對制作隊列的這套教程感到滿意融痛！
上面的代碼可點擊 這里下載壶笼。你還可以去往 這里 查看其他的實現(xiàn)方式以及進行隊列的進一步的討論。
