原文鏈接： Swift Algorithm Club: Swift Stack Data Structure
翻譯： coderJoey
通過本教程盏袄，你將學習怎樣用swift實現(xiàn)堆棧數(shù)據(jù)結(jié)構(gòu)芳绩。作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)蛾绎，堆棧能解決很多程序中的問題昆箕。
開始吧
堆棧很像數(shù)組鸦列，但是其功能較數(shù)組而言有所限制。你只能通過push（壓人）來添加新元素到堆棧的頂部鹏倘，也只能通過pop來移除堆棧頂部的元素薯嗤，如果不進行移除操作的話，你也只能查看到堆棧最上面的元素纤泵。
這種數(shù)據(jù)結(jié)構(gòu)有什么用呢骆姐？在很多算法中，例如某個時刻你想添加一些新的對象到一個臨時鏈中捏题，然后不就之后你需要刪除掉這些對象玻褪，添加和刪除這些對象的順序有時候是很重要的。
堆棧進出棧順序是LIFO（ last-in first-out order：后進先出）公荧，也就是最后進棧的元素最先被移除带射。（這非常像數(shù)據(jù)結(jié)構(gòu)隊列（FIFO:先進先出））
接下來，你將用數(shù)組實現(xiàn)堆棧的內(nèi)部存儲操作循狰。雖然這不是很高效的做法窟社，但能讓你理解堆棧結(jié)構(gòu)的實現(xiàn)方式。
堆棧的相關(guān)操作
堆棧的功能范圍相對有限晤揣。 以堆疊的書籍為例桥爽，堆棧相應(yīng)的功能有：
Push
當你要添加元素到堆棧中時，你應(yīng)該將元素push到堆棧的最上面昧识。就像放一本書到一疊書上面。
Peek
按照設(shè)計規(guī)則盗扒，堆棧不允許查看除了堆棧的頂部元素的其它元素跪楞。 peek方法只允許你查看堆棧頂部的內(nèi)容。
Pop
就像下圖從一疊書中拿掉最上面的書本一樣侣灶，你只能通過pop移除掉堆棧中最上面的元素甸祭。
Swift 堆棧的實現(xiàn)
用Xcode創(chuàng)建一個新的playground！
開始褥影，先將下面的代碼寫到你的playground中：
struct Stack {
fileprivate var array: [String] = []
}
這里定義了一個擁有一個array屬性的堆棧池户，你將通過這個array屬性來實現(xiàn) push、 pop凡怎、 和 peek這些功能方法
Push
將對象壓入到堆棧中是比較簡單的校焦。把下面的方法加到stack實現(xiàn)中：
// 1
mutating func push(_ element: String) {
// 2
array.append(element)
}
push方法只有一個參數(shù)，即需要添加到棧頂?shù)脑亍?/p>
注意這里新元素是添加到數(shù)組的末尾而不是數(shù)組的開頭统倒。如果添加到數(shù)組的開始位置寨典，則是代價相當大的O(n)操作，因為這需要數(shù)組里面所有的元素在內(nèi)存中都進行移位操作房匆。添加在數(shù)組尾部的時間復雜度是** O(1)**耸成，不管數(shù)組的大小是多少报亩，它所需要的時間是固定的。
Pop
元素出棧也是很簡單的井氢。將下面的方法放到push方法下面：
// 1
mutating func pop() -> String? {
// 2
return array.popLast()
}
pop方法的返回值是可選類型String弦追，返回可選類型是為了處理堆棧為空的情況。如果你對一個內(nèi)容為空的堆棧進行pop操作的話花竞，返回值將是nil骗卜。
Swift 數(shù)組刪除最后一個元素的方法popLast。
Peek
查看堆棧的元素實質(zhì)就是查看棧頂?shù)脑刈蟀＿@也是相對比較容易實現(xiàn)的寇仓。Swift 數(shù)組有一個last屬性專門來訪問數(shù)組的最后一個元素。
func peek() -> String? {
return array.last
}
peek方法和pop方法類似烤宙，最大的區(qū)別是pop方法前面有關(guān)鍵字mutating遍烦。這是因為peek方法不會改變數(shù)組的內(nèi)容，所以沒有必要加關(guān)鍵字mutating了躺枕。
試一試
到現(xiàn)在為止服猪，你的Swift堆棧已經(jīng)可以進行一些測試了。將下面的代碼加到playground的底部：
// 1
var rwBookStack = Stack()
// 2
rwBookStack.push("3D Games by Tutorials")
// 3
rwBookStack.peek()
// 4
rwBookStack.pop()
// 5
rwBookStack.pop()
在playground的右面板上拐云，你能看到每一行的輸出結(jié)果：
初始化一個堆棧對象并賦值給變量rwBookStack罢猪。這里使用var將其定義為變量而不是常量，是因為等會你會改變堆棧的內(nèi)容叉瘩。
添加一個字符串到堆棧中膳帕。
查看堆棧內(nèi)容，也就是最后入棧的字符串“3D Games by Tutorials”薇缅。
移除棧頂?shù)膬?nèi)容危彩，也就是最后入棧的字符串“3D Games by Tutorials”。
由于你已經(jīng)移除了堆棧中的所有內(nèi)容泳桦，所以面板顯示為nil汤徽。
CustomStringConvertible
現(xiàn)在打印堆棧對象的話，很難看出堆棧是如何工作的灸撰。 幸運的是谒府，Swift有一個名為CustomStringConvertible的內(nèi)置協(xié)議，它允許你自定義打印內(nèi)容浮毯。 將下面的代碼寫到Stack實現(xiàn)的下面（不是里面）：
// 1
extension Stack: CustomStringConvertible {
// 2
var description: String {
// 3
let topDivider = "---Stack---\n"
let bottomDivider = "\n-----------\n"
// 4
let stackElements = array.reversed().joined(separator: "\n")
// 5
return topDivider + stackElements + bottomDivider
}
}
上面代碼做了什么：
實現(xiàn)一個Stack的擴展完疫，并遵守CustomStringConvertible協(xié)議。
根據(jù)CustomStringConvertible協(xié)議實現(xiàn)description屬性亲轨。
添加數(shù)據(jù)頭部和尾部的打印內(nèi)容趋惨。
你需要將數(shù)組里面的元素按照堆棧的樣式打印出來。 由于你是將元素添加到數(shù)組的尾部惦蚊，所以首先要做的是反轉(zhuǎn)數(shù)組器虾。然后用joined(separator:) 方法來拼接數(shù)組里面的元素讯嫂，元素之間用separator隔開。例如數(shù)組["3D Games by Tutorials", "tvOS Apprentice"] 拼接之后就變成了** "3D Games by Tutorials\ntvOS Apprentice" **兆沙。
最后將topDivider 欧芽、 stackElements 和 bottomDivider像三明治一樣的疊起來，作為堆棧的描述（打痈鹌浴）內(nèi)容千扔。
刪掉之前的測試代碼并添加下面的代碼到playground底部：
var rwBookStack = Stack()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)
在playground下面的控制臺將輸出：
---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------
泛型
目前為止，你的堆棧只能存儲strings库正。如果要創(chuàng)建一個堆棧來存儲整數(shù)曲楚，則必須實現(xiàn)一個面向整數(shù)的全新的堆棧。幸運的是Swift可以通過泛型來抽象我們需要儲存的數(shù)據(jù)褥符。將你的Stack改成下面的樣式：
struct Stack<Element> {
// ...
}
代碼中的尖括號將這個結(jié)構(gòu)體聲明為泛型龙誊，允許堆棧傳入Swift中的所有類型。 下一步喷楣，查找并將實例中的“String”類型替換為“Element”√舜螅現(xiàn)在你的Stack應(yīng)該是這樣：
struct Stack<Element> {
fileprivate var array: [Element] = []
mutating func push(_ element: Element) {
array.append(element)
}
mutating func pop() -> Element? {
return array.popLast()
}
func peek() -> Element? {
return array.last
}
}
最后，你還需要修改description屬性的內(nèi)容铣焊。只需要改一個地方逊朽，像下面這樣：
// 修改前
let stackElements = array.reversed().joined(separator: "\n")
// 修改后
let stackElements = array.map { "\($0)" }.reversed().joined(separator: "\n")
這里主要是將數(shù)組元素在拼接前轉(zhuǎn)換成String類型。由于你不確定數(shù)組元素的類型曲伊，所以這個轉(zhuǎn)換時必要的叽讳。
最后你要將創(chuàng)建的堆棧對象指定為String類型。
var rwBookStack = Stack<String>()
現(xiàn)在你的堆棧能夠指定為String熊昌、Int和其他任何類型了绽榛，甚至你自定義的類型像Person也是可以的！
收尾
這里還有兩個屬性是堆棧常常用到的：判斷堆棧是否為空和堆棧當前的元素個數(shù)婿屹。
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
何去何從
希望你對制作堆棧的這套教程感到滿意！
上面的代碼可點擊這里下載。你還可以去往這里查看最初的實現(xiàn)方式以及進行堆棧的進一步的討論。
