目錄

• 基本性質(zhì)
• 棧和隊(duì)列的基本操作
• 雙端隊(duì)列和優(yōu)先級(jí)隊(duì)列
• 深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)
• 遞歸函數(shù)與系統(tǒng)函數(shù)棧
• 實(shí)現(xiàn)一個(gè)特殊的棧，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上，再實(shí)現(xiàn)返回棧中最小元素的操作
  • 如何保存最小值
• 僅用棧結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)
  • 如何保證棧結(jié)構(gòu)能夠先進(jìn)先出
  • 何時(shí)進(jìn)行傾倒操作
• 僅用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)
• 實(shí)現(xiàn)一個(gè)棧的逆序，不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)，只能使用棧本身的功能
  • 移除棧底元素，并將其返回
• 將棧中的元素排序

基本性質(zhì)

• 棧---先進(jìn)后出

• 隊(duì)列---先進(jìn)先出

• 棧和隊(duì)列通常都有數(shù)組和鏈表兩種實(shí)現(xiàn)方式

數(shù)組相對(duì)容易，鏈表需要進(jìn)行一些指針操作

棧和隊(duì)列的基本操作

• pop操作

彈出棧頂元素

• top或peek操作

只訪問而不彈出棧頂元素

• push操作

從棧頂壓入一個(gè)元素

• size操作

返回當(dāng)前棧中元素個(gè)數(shù)

對(duì)于隊(duì)列，push是在隊(duì)列頭部加入一個(gè)元素，pop是在尾部彈出一個(gè)元素。

棧和隊(duì)列的基本操作，時(shí)間復(fù)雜度都是O(1) 。

雙端隊(duì)列和優(yōu)先級(jí)隊(duì)列

• 雙端隊(duì)列

首尾都可以壓入和彈出元素

• 優(yōu)先級(jí)隊(duì)列

彈出時(shí)，根據(jù)元素的優(yōu)先級(jí)決定彈出的順序。
具體實(shí)現(xiàn)上為一個(gè)堆結(jié)構(gòu)，而不是線性表結(jié)構(gòu)。

深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

• 深度優(yōu)先遍歷(前序遍歷)。使用棧的結(jié)構(gòu)

先嘗試將左元素入棧，若棧頂元素為空則將棧頂推出然后嘗試遍歷右節(jié)點(diǎn)。直到棧為空則遍歷結(jié)束。

func preorderTraversal(root: TreeNode?) -> [Int] {
  var res = [Int]()
  var stack = [TreeNode]() //遍歷用的棧
  var node = root//遍歷的根節(jié)點(diǎn)

  while !stack.isEmpty || node != nil {
    if node != nil {
      res.append(node!.val)  //將當(dāng)前節(jié)點(diǎn)的值記錄
      stack.append(node!) //將當(dāng)前節(jié)點(diǎn)加入棧中
      node = node!.left //嘗試遍歷當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
    } else {
      node = stack.removeLast().right  //將棧頂節(jié)點(diǎn)推出，并嘗試遍歷其父元素的右節(jié)點(diǎn)。
    }
  }

  return res
}

遍歷的結(jié)果為：1，2，4，5，3，6，7

• 廣度優(yōu)先遍歷。使用隊(duì)列結(jié)構(gòu)

從root節(jié)點(diǎn)開始依次入隊(duì)，當(dāng)從隊(duì)列推出一個(gè)元素時(shí)，嘗試將其兩個(gè)子元素依次加入加入隊(duì)列。直到隊(duì)列為空遍歷結(jié)束。

遍歷的結(jié)果為：1，2，3，4，5，6，7

遞歸函數(shù)與系統(tǒng)函數(shù)棧

平時(shí)使用的遞歸函數(shù)實(shí)際上是有系統(tǒng)負(fù)責(zé)向系統(tǒng)函數(shù)棧中進(jìn)行壓棧
遞歸過程可以看作是遞歸函數(shù)依次進(jìn)入函數(shù)棧的處理過程
所有用遞歸函數(shù)可以做的過程，都可以用非遞歸的方式實(shí)現(xiàn)。

實(shí)現(xiàn)一個(gè)特殊的棧，在實(shí)現(xiàn)棧的基本功能的基礎(chǔ)上，再實(shí)現(xiàn)返回棧中最小元素的操作

【要求】

1. pop、push、getMin操作的時(shí)間復(fù)雜度都是O(1)。
2. 設(shè)計(jì)的棧類型可以使用現(xiàn)成的棧結(jié)構(gòu)。

如何保存最小值
需要兩個(gè)棧，StackData以及StackMin。StackData負(fù)責(zé)正常壓棧，StackMin負(fù)責(zé)記錄當(dāng)前最小值。
當(dāng)進(jìn)行push操作時(shí)，當(dāng)前元素與StackMin棧頂元素進(jìn)行比較，將較小的數(shù)壓入StackMin。

當(dāng)進(jìn)行pop操作時(shí)，StackData以及StackMin同時(shí)進(jìn)行pop。
當(dāng)進(jìn)行g(shù)etmin操作時(shí)，由StackMin負(fù)責(zé)進(jìn)行peek。

時(shí)間復(fù)雜度為O(1)，額外空間復(fù)雜度為O(N)

僅用棧結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列結(jié)構(gòu)

需要兩個(gè)棧結(jié)構(gòu)實(shí)現(xiàn)。一個(gè)棧作為壓入棧(StackPush)負(fù)責(zé)承接push元素，一個(gè)棧作為彈出棧(StackPop)負(fù)責(zé)彈出pop元素。

• 如何保證棧結(jié)構(gòu)能夠先進(jìn)先出

通過將StackPush的數(shù)據(jù)倒入StackPop中，來將StackPush中數(shù)據(jù)的順序顛倒，保證先進(jìn)先出。

這個(gè)傾倒操作需要有兩個(gè)注意的點(diǎn)：

1. StackPop棧為空。
2. 每次需要將StackPush棧所有的數(shù)據(jù)全部倒入StackPop棧。

• 何時(shí)進(jìn)行傾倒操作

當(dāng)任何StackPush或者StackPop棧內(nèi)的數(shù)據(jù)改變時(shí)，可以嘗試傾倒操作。

僅用隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)

需要兩個(gè)隊(duì)列實(shí)現(xiàn)。
當(dāng)進(jìn)行pop操作時(shí)，將當(dāng)前使用的CurrentQueue中元素推入輔助隊(duì)列HelpQueue，僅保留隊(duì)尾元素返回給用戶。
然后將CurrentQueue與HelpQueue的指針互換，保證push操作時(shí)，CurrentQueue始終為有內(nèi)容的隊(duì)列。

實(shí)現(xiàn)一個(gè)棧的逆序，不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)，只能使用棧本身的功能

• 移除棧底元素，并將其返回

通過遞歸的方式，每層保存相應(yīng)的棧頂元素。獲取到棧底元素后再依次壓入棧中

/// 移除棧底元素，并將其返回
///
/// - Parameter stack: 棧
/// - Returns:棧底元素
func getLast(stack : Stack) -> Int {
    let value = stack.pop() //獲得當(dāng)前棧頂元素
    if stack.isEmpty() { //如果棧為空
        return value //當(dāng)前元素則為棧底元素
    }else {
        let last = getLast(stack)
        stack.push(value)
        return last
    }
}

將棧中的元素排序

【要求】

1. 值允許申請(qǐng)一個(gè)棧
2. 可以申請(qǐng)變量
3. 不能申請(qǐng)額外的數(shù)據(jù)結(jié)構(gòu)

原棧為stack，輔助棧為help。
從stack棧中pop出來的元素計(jì)作current
若current小于help棧頂元素，則直接壓入棧中。
若current大于help棧頂元素，則將help棧頂推出并壓入stack。
重復(fù)，直到stack中元素為0。然后將help倒回給stack

參考資料

左神牛課網(wǎng)算法課