數(shù)據(jù)結(jié)構(gòu)：堆棧

通過本教程，你將學(xué)習(xí)怎樣用swift實(shí)現(xiàn)堆棧數(shù)據(jù)結(jié)構(gòu)。作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，堆棧能解決很多程序中的問題。

開始吧

堆棧很像數(shù)組，但是其功能較數(shù)組而言有所限制。你只能通過push（壓人）來添加新元素到堆棧的頂部，也只能通過pop來移除堆棧頂部的元素，如果不進(jìn)行移除操作的話，你也只能查看到堆棧最上面的元素。

這種數(shù)據(jù)結(jié)構(gòu)有什么用呢？在很多算法中，例如某個(gè)時(shí)刻你想添加一些新的對(duì)象到一個(gè)臨時(shí)鏈中，然后不就之后你需要?jiǎng)h除掉這些對(duì)象，添加和刪除這些對(duì)象的順序有時(shí)候是很重要的。

堆棧進(jìn)出棧順序是LIFO（ last-in first-out order：后進(jìn)先出），也就是最后進(jìn)棧的元素最先被移除。（這非常像數(shù)據(jù)結(jié)構(gòu)隊(duì)列（FIFO:先進(jìn)先出））

我們將用RW的書來解析堆棧的工作原理

接下來，你將用數(shù)組實(shí)現(xiàn)堆棧的內(nèi)部存儲(chǔ)操作。雖然這不是很高效的做法，但能讓你理解堆棧結(jié)構(gòu)的實(shí)現(xiàn)方式。

堆棧的相關(guān)操作

堆棧的功能范圍相對(duì)有限。 以堆疊的書籍為例，堆棧相應(yīng)的功能有：

Push

當(dāng)你要添加元素到堆棧中時(shí)，你應(yīng)該將元素push到堆棧的最上面。就像放一本書到一疊書上面。

Peek

按照設(shè)計(jì)規(guī)則，堆棧不允許查看除了堆棧的頂部元素的其它元素。 peek方法只允許你查看堆棧頂部的內(nèi)容。

不能看到底下的書籍

Pop

就像下圖從一疊書中拿掉最上面的書本一樣，你只能通過pop移除掉堆棧中最上面的元素。

Swift 堆棧的實(shí)現(xiàn)

用Xcode創(chuàng)建一個(gè)新的playground！
開始，先將下面的代碼寫到你的playground中：

struct Stack {
  fileprivate var array: [String] = []
}

這里定義了一個(gè)擁有一個(gè)array屬性的堆棧，你將通過這個(gè)array屬性來實(shí)現(xiàn) push、 pop、 和 peek這些功能方法

Push

將對(duì)象壓入到堆棧中是比較簡(jiǎn)單的。把下面的方法加到stack實(shí)現(xiàn)中：

// 1
mutating func push(_ element: String) {
  // 2
  array.append(element)
}

1. push方法只有一個(gè)參數(shù)，即需要添加到棧頂?shù)脑亍?/p>

2. 注意這里新元素是添加到數(shù)組的末尾而不是數(shù)組的開頭。如果添加到數(shù)組的開始位置，則是代價(jià)相當(dāng)大的O(n)操作，因?yàn)檫@需要數(shù)組里面所有的元素在內(nèi)存中都進(jìn)行移位操作。添加在數(shù)組尾部的時(shí)間復(fù)雜度是** O(1)**，不管數(shù)組的大小是多少，它所需要的時(shí)間是固定的。

Pop

元素出棧也是很簡(jiǎn)單的。將下面的方法放到push方法下面：

// 1
mutating func pop() -> String? {
  // 2
  return array.popLast()
}

1. pop方法的返回值是可選類型String，返回可選類型是為了處理堆棧為空的情況。如果你對(duì)一個(gè)內(nèi)容為空的堆棧進(jìn)行pop操作的話，返回值將是nil。

2. Swift 數(shù)組刪除最后一個(gè)元素的方法popLast。

Peek

查看堆棧的元素實(shí)質(zhì)就是查看棧頂?shù)脑亍＿@也是相對(duì)比較容易實(shí)現(xiàn)的。Swift 數(shù)組有一個(gè)last屬性專門來訪問數(shù)組的最后一個(gè)元素。

func peek() -> String? {
 return array.last
}

peek方法和pop方法類似，最大的區(qū)別是pop方法前面有關(guān)鍵字mutating。這是因?yàn)?strong>peek方法不會(huì)改變數(shù)組的內(nèi)容，所以沒有必要加關(guān)鍵字mutating了。

試一試

到現(xiàn)在為止，你的Swift堆棧已經(jīng)可以進(jìn)行一些測(cè)試了。將下面的代碼加到playground的底部：

// 1 
var rwBookStack = Stack()

// 2
rwBookStack.push("3D Games by Tutorials")
// 3
rwBookStack.peek()

// 4
rwBookStack.pop()
// 5
rwBookStack.pop()

在playground的右面板上，你能看到每一行的輸出結(jié)果：

1. 初始化一個(gè)堆棧對(duì)象并賦值給變量rwBookStack。這里使用var將其定義為變量而不是常量，是因?yàn)榈葧?huì)你會(huì)改變堆棧的內(nèi)容。

2. 添加一個(gè)字符串到堆棧中。

3. 查看堆棧內(nèi)容，也就是最后入棧的字符串“3D Games by Tutorials”。

4. 移除棧頂?shù)膬?nèi)容，也就是最后入棧的字符串“3D Games by Tutorials”。

5. 由于你已經(jīng)移除了堆棧中的所有內(nèi)容，所以面板顯示為nil。

CustomStringConvertible

現(xiàn)在打印堆棧對(duì)象的話，很難看出堆棧是如何工作的。 幸運(yùn)的是，Swift有一個(gè)名為CustomStringConvertible的內(nèi)置協(xié)議，它允許你自定義打印內(nèi)容。 將下面的代碼寫到Stack實(shí)現(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
  }
}

上面代碼做了什么：

1. 實(shí)現(xiàn)一個(gè)Stack的擴(kuò)展，并遵守CustomStringConvertible協(xié)議。

2. 根據(jù)CustomStringConvertible協(xié)議實(shí)現(xiàn)description屬性。

3. 添加數(shù)據(jù)頭部和尾部的打印內(nèi)容。

4. 你需要將數(shù)組里面的元素按照堆棧的樣式打印出來。 由于你是將元素添加到數(shù)組的尾部，所以首先要做的是反轉(zhuǎn)數(shù)組。然后用joined(separator:) 方法來拼接數(shù)組里面的元素，元素之間用separator隔開。例如數(shù)組["3D Games by Tutorials", "tvOS Apprentice"] 拼接之后就變成了** "3D Games by Tutorials\ntvOS Apprentice" **。

5. 最后將topDivider 、 stackElements 和 bottomDivider像三明治一樣的疊起來，作為堆棧的描述（打?。﹥?nèi)容。

刪掉之前的測(cè)試代碼并添加下面的代碼到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下面的控制臺(tái)將輸出：

---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------

泛型

目前為止，你的堆棧只能存儲(chǔ)strings。如果要?jiǎng)?chuàng)建一個(gè)堆棧來存儲(chǔ)整數(shù)，則必須實(shí)現(xiàn)一個(gè)面向整數(shù)的全新的堆棧。幸運(yùn)的是Swift可以通過泛型來抽象我們需要儲(chǔ)存的數(shù)據(jù)。將你的Stack改成下面的樣式：

struct Stack<Element> {
  // ...
}

代碼中的尖括號(hào)將這個(gè)結(jié)構(gòu)體聲明為泛型，允許堆棧傳入Swift中的所有類型。 下一步，查找并將實(shí)例中的“String”類型替換為“Element”?，F(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)容。只需要改一個(gè)地方，像下面這樣：

// 修改前
let stackElements = array.reversed().joined(separator: "\n")

// 修改后
let stackElements = array.map { "\($0)" }.reversed().joined(separator: "\n")

這里主要是將數(shù)組元素在拼接前轉(zhuǎn)換成String類型。由于你不確定數(shù)組元素的類型，所以這個(gè)轉(zhuǎn)換時(shí)必要的。
最后你要將創(chuàng)建的堆棧對(duì)象指定為String類型。

var rwBookStack = Stack<String>()

現(xiàn)在你的堆棧能夠指定為String、Int和其他任何類型了，甚至你自定義的類型像Person也是可以的！

收尾

這里還有兩個(gè)屬性是堆棧常常用到的：判斷堆棧是否為空和堆棧當(dāng)前的元素個(gè)數(shù)。

var isEmpty: Bool {
  return array.isEmpty
}

var count: Int {
  return array.count
}

何去何從

希望你對(duì)制作堆棧的這套教程感到滿意！
上面的代碼可點(diǎn)擊這里下載。你還可以去往這里查看最初的實(shí)現(xiàn)方式以及進(jìn)行堆棧的進(jìn)一步的討論。