0x00 棧

棧是一種操作受限的線性表，只允許一端插入和刪除數(shù)據(jù)，相比數(shù)組和鏈表，棧的操作只有限制

事實(shí)上，在功能上數(shù)組和鏈表確實(shí)可以替代棧，棧的底層一般也是數(shù)組或鏈表實(shí)現(xiàn)的，但是

特定的數(shù)據(jù)結(jié)構(gòu)是對(duì)特定場(chǎng)景的抽象，而且數(shù)組或鏈表暴露了太多的接口，操作上靈活自由，但使用起來(lái)也比較不可控，很容易出錯(cuò)

當(dāng)某個(gè)數(shù)據(jù)只涉及在一端插入或刪除數(shù)據(jù)，并且滿足先進(jìn)后出、后進(jìn)先出的特性，我們就應(yīng)首選棧

0x01 棧實(shí)現(xiàn)

• 數(shù)組實(shí)現(xiàn)

// n:棧的大小 items:棧中的元素 count:棧中元素的個(gè)數(shù)
case class ArrayStack(n:Int,items:Array[String]) {
  // 棧中元素個(gè)數(shù)
  var count=0
  // 入棧
  def push(item:String): Boolean ={
    // 棧滿了，返回false
    if (count == n){
      return false
    }
    items(count) = item
    count += 1
    true
  }
  // 出棧
  def pop(): String ={
    // 棧為空 返回null
    if (count == 0){
      return null
    }
    count -= 1
    items(count)
  }
  // 清空棧
  def clear(): Unit ={
    count = 0
  }
}

• 鏈表實(shí)現(xiàn)

class LinkedStack {
  
  var head:Option[Node] = None
  var size:Int = 0
  // 入棧
  def push(value:Int): Boolean ={
    head = Option(Node(value,head))
    size += 1
    true
  }
  // 出棧
  def pop(): Option[Node] ={
    if (size==0){
      return None
    }
    val item = head
    head = head.get.next
    size -=1
    item
  }
  // 清空棧
  def clear(): Unit ={
    size = 0
    head = None
  }
}

0x02 應(yīng)用

• 函數(shù)調(diào)用棧

操作系統(tǒng)給每個(gè)線程分配了獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成棧這種數(shù)據(jù)結(jié)構(gòu)，用來(lái)保存函數(shù)調(diào)用的臨時(shí)變量，當(dāng)一個(gè)函數(shù)調(diào)用完成，就全部彈棧，然后執(zhí)行下一個(gè)函數(shù)，以此來(lái)維護(hù)函數(shù)調(diào)用鏈

• 四則運(yùn)算

我們?nèi)顺Ｒ?jiàn)的四則運(yùn)算，例如 1-3*4+4/2 對(duì)于電腦來(lái)說(shuō)并不好識(shí)別執(zhí)行的先后順序，一般會(huì)使用棧來(lái)計(jì)算，專欄中介紹了一種依靠?jī)蓚€(gè)棧實(shí)現(xiàn)的方式，還有一種逆波蘭表達(dá)式也叫后綴表達(dá)式的方法求解

1、兩個(gè)棧實(shí)現(xiàn)

一個(gè)棧存儲(chǔ)數(shù)字，一個(gè)棧存儲(chǔ)運(yùn)算符，從左到右遍歷運(yùn)算式，如果是數(shù)字就壓棧，如果是運(yùn)算符，就與運(yùn)算符棧的棧頂元素比較，如果比棧頂運(yùn)算符優(yōu)先級(jí)高，就壓棧，如果優(yōu)先級(jí)低或相同，則從數(shù)字棧取兩個(gè)數(shù)字，從棧頂取一個(gè)操作符計(jì)算，并將結(jié)果壓入數(shù)字棧，然后繼續(xù)比較棧頂運(yùn)算符和當(dāng)前運(yùn)算符的優(yōu)先級(jí)

github代碼

不包含括號(hào)的版本，如果包含小括號(hào)，可以把右括號(hào)優(yōu)先級(jí)設(shè)為最小，左括號(hào)優(yōu)先級(jí)設(shè)為最大，然后特殊處理一下左右括號(hào)
// 只有+-*/ 不包含括號(hào)
def caculate(express:String): Long ={
    val addInt = '+'.toInt
    val minusInt = '-'.toInt
    val multiInt = '*'.toInt
    val divideInt = '/'.toInt
    val symbolMap = Map(addInt->1,minusInt->1,multiInt->2,divideInt->2)
    val numStack = new LinkedStack
    val symbolStack = new LinkedStack
    // 前一個(gè)是否是數(shù)字
    var preIfNum = true
    // 數(shù)字棧棧頂放一個(gè)0 表達(dá)式第一個(gè)一定是數(shù)字，這樣不用對(duì)頭做特殊處理
    numStack.push(0)
    for (s <- express){
      var i = s.toInt - 48
      // 0-9
      if(i >= 0 && i<=9){
        // 如果前一個(gè)字符也是數(shù)字，那么將前一個(gè)*10加上當(dāng)前數(shù)字然后入棧
        if (preIfNum){
          i += 10*numStack.pop().get.data
        }
        numStack.push(i)
        preIfNum=true
      }else{
        preIfNum = false
        var preSymbol = symbolStack.pop()
        while (preSymbol.isDefined){
          // 如果當(dāng)前的運(yùn)算符優(yōu)先級(jí)小于等于上一個(gè)運(yùn)算符，則計(jì)算上一個(gè)運(yùn)算符
          if (symbolMap(preSymbol.get.data) >= symbolMap(s.toInt)){
            val a = numStack.pop().get.data
            val b = numStack.pop().get.data
            val res = preSymbol.get.data match {
              case `addInt` => b+a
              case `minusInt` => b-a
              case `multiInt` => b*a
              case `divideInt` => b/a
            }
            numStack.push(res)
            preSymbol = symbolStack.pop()
          }else{
            // 放回彈出的上一個(gè)運(yùn)算符，跳出循環(huán)
            symbolStack.push(preSymbol.get.data)
            preSymbol = None
          }
        }
        // 將當(dāng)前運(yùn)算符放入棧
        symbolStack.push(s.toInt)
      }
    }
    // 計(jì)算棧中剩下的數(shù)據(jù)
    var symbol = symbolStack.pop()
    while (symbol.isDefined){
      val a = numStack.pop().get.data
      val b = numStack.pop().get.data
      val res = symbol.get.data match {
        case `addInt` => b+a
        case `minusInt` => b-a
        case `multiInt` => b*a
        case `divideInt` => b/a
      }
      numStack.push(res)
      symbol = symbolStack.pop()
    }
    numStack.pop().get.data
 }

2、逆波蘭表達(dá)式

逆波蘭表達(dá)式又叫后綴表達(dá)式，這種方法是先將我們常見(jiàn)的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，例如：(2+3)*5 => 2 3 + 5 * 運(yùn)算符在兩個(gè)計(jì)算數(shù)字后面，這樣方便計(jì)算機(jī)程序判斷計(jì)算，使用一個(gè)棧就可以完成，詳細(xì)代碼見(jiàn)GitHub代碼的caculate3方法

參考中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

• 括號(hào)匹配

常見(jiàn)的算法題中還有括號(hào)匹配，小括號(hào)、中括號(hào)、打括號(hào)，任意組合，判斷是夠匹配，例如：[{()}([])]匹配，可以通過(guò)棧來(lái)實(shí)現(xiàn)
GitHub

 def isValid(s:String): Boolean ={
    val bracket = Map('('->')','['->']','{'->'}')
    val stack = mutable.Stack[Char]()
    for (c <- s){
      if (bracket.contains(c)){
        stack.push(c)
      }else{
        if(stack.isEmpty || c != bracket(stack.pop())){
          return false
        }
      }
    }
    if (stack.nonEmpty){
      return false
    }
    true
 }

0x03 課后思考

1、我們?cè)谥v棧的應(yīng)用時(shí)，講到用函數(shù)調(diào)用棧來(lái)保存臨時(shí)變量，為什么函數(shù)調(diào)用要用棧來(lái)保存臨時(shí)變量，用其他數(shù)據(jù)結(jié)構(gòu)行不行？

保存臨時(shí)變量可以用很多種數(shù)據(jù)結(jié)構(gòu)，使用棧只是因?yàn)榉舷冗M(jìn)后出的場(chǎng)景，對(duì)于函數(shù)調(diào)用來(lái)說(shuō)，從調(diào)用函數(shù)進(jìn)入被調(diào)用函數(shù)，最主要的變化是作用域，所以只要能保證進(jìn)入調(diào)用函數(shù)后能方便的切換作用域就可以，而當(dāng)進(jìn)入被調(diào)用函數(shù)時(shí)，使用棧存儲(chǔ)新的函數(shù)變量，當(dāng)函數(shù)調(diào)用完成，將棧頂復(fù)位，正好可以直接回到調(diào)用函數(shù)

2、java內(nèi)存管理中有堆棧的概念，棧內(nèi)存用來(lái)存儲(chǔ)局部變量和方法調(diào)用，堆內(nèi)存用來(lái)存儲(chǔ)java中的對(duì)象，java中的棧和我們數(shù)據(jù)結(jié)構(gòu)中的棧是不是一回事？如果不是為什么也稱為棧呢？

按我的理解，java內(nèi)存管理中的棧和?？梢允且换厥拢?yàn)閮?nèi)存管理中的棧也是一種組織內(nèi)存數(shù)據(jù)的方式，滿足先進(jìn)后出的實(shí)現(xiàn)，但是，可能提供了更多的功能，所以可以認(rèn)為是一回事

節(jié)選專欄評(píng)論區(qū)小鄧的評(píng)論：

課后思考問(wèn)題2是多次困擾我的一個(gè)問(wèn)題：內(nèi)存管理上的“?！焙蛿?shù)據(jù)結(jié)構(gòu)上的“?！钡降资遣皇且换厥?。
按出題套路而言，問(wèn)“如果不是，給出理由”的問(wèn)題答案大多是“不是”。高贊留言里有的說(shuō)是，有的說(shuō)不是，我簡(jiǎn)單翻了翻三大本厚書(shū)《C#圖接教程》、《算法》、《深入理解計(jì)算機(jī)基礎(chǔ)》，再去翻了翻相關(guān)博客和知乎，我的回答是“不是”。
（1）首先，在內(nèi)存管理和數(shù)據(jù)結(jié)構(gòu)上，都有“堆”和“?！边@兩個(gè)概念。
（2）內(nèi)存管理上的“堆”和“?！?，強(qiáng)調(diào)的是數(shù)據(jù)的生命周期（分配釋放是否有次序要求）；數(shù)據(jù)結(jié)構(gòu)上的“堆”和“?！?，強(qiáng)調(diào)的是數(shù)據(jù)的組織。
（3）內(nèi)存管理上的“?！狈蠑?shù)據(jù)結(jié)構(gòu)的“?！钡奶攸c(diǎn)，即LIFO，兩者同名可以接受。
（4）數(shù)據(jù)結(jié)構(gòu)上的“堆”定義：它是一種數(shù)組對(duì)象，它可以被視為一科完全二叉樹(shù)結(jié)構(gòu)；應(yīng)用場(chǎng)景包括堆排序，優(yōu)先隊(duì)列等。和內(nèi)存管理的“堆”定義不同（這里我不是很確定，沒(méi)有看過(guò)內(nèi)存管理上堆的實(shí)現(xiàn)細(xì)節(jié)）。

參考：
（1）數(shù)據(jù)結(jié)構(gòu)之“堆”：http://www.cnblogs.com/Jason-Damon/archive/2012/04/18/2454649.html
（2）專題 | 堆、棧簡(jiǎn)介：https://zhuanlan.zhihu.com/p/45597548
（3）知乎| 為什么c++中要分為heap（堆）和stack（棧）? - Milo Yip的回答：https://www.zhihu.com/question/281940376/answer/424990646