0x00 棧

棧是一種操作受限的線(xiàn)性表柜裸，只允許一端插入和刪除數(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ù)，并且滿(mǎn)足先進(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 ={
    // 棧滿(mǎn)了，返回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è)線(xiàn)程分配了獨(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ì)算，專(zhuān)欄中介紹了一種依靠?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)中的棧是不是一回事荤牍？如果不是為什么也稱(chēng)為棧呢峰尝？

按我的理解破加，java內(nèi)存管理中的棧和椖晨穑可以是一回事，因?yàn)閮?nèi)存管理中的棧也是一種組織內(nèi)存數(shù)據(jù)的方式啥酱，滿(mǎn)足先進(jìn)后出的實(shí)現(xiàn)爹凹，但是，可能提供了更多的功能懈涛，所以可以認(rèn)為是一回事

節(jié)選專(zhuān)欄評(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)的“椈冢”的特點(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）專(zhuān)題 | 堆、棧簡(jiǎn)介：https://zhuanlan.zhihu.com/p/45597548
（3）知乎| 為什么c++中要分為heap（堆）和stack（棧）? - Milo Yip的回答：https://www.zhihu.com/question/281940376/answer/424990646