數(shù)據(jù)結(jié)構(gòu)與算法系列（一）棧：如何實現(xiàn)有效括號的判斷？

有效括號，我想很多人對LeetCode上的這道題很熟悉吧？

1.開篇問題：有效的括號

有效的括號題目描述

假如現(xiàn)在要你來解這道題，你會想到怎樣的解法了？

這就要用到我們今天要講的“?！边@種數(shù)據(jù)結(jié)構(gòu)。帶著這個問題，我們來學(xué)習(xí)今天的內(nèi)容。

2.如何理解“?！?？

關(guān)于棧，有一個非常貼切的游戲--漢諾塔。玩這個游戲的時候，我們都是從下往上一個一個放；取的時候，我們也是從上往下一個一個地依次取，不能從中間任意抽出。后進(jìn)者先出，先進(jìn)者后出，這就是典型的“?！苯Y(jié)構(gòu)。

漢諾塔

3.如何實現(xiàn)棧

從剛才棧的定義里，我們可以看出，棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個數(shù)據(jù)和從棧頂刪除一個數(shù)據(jù)。理解了棧的定義之后，我們來看一看如何用代碼實現(xiàn)一個棧。
【本文使用 swift語言來編寫代碼，讀者朋友們不要因為編程語言不同而有畏難情緒，重要的是思維和邏輯，語言只是表達(dá)方式。你可以用你自己熟悉的語言來表達(dá)你的邏輯，可以先試著寫一寫】

class Stack {
    //初始化數(shù)組
    var datas = [Int]()
    //出棧操作
    func pop() -> Int? {
        return datas.popLast()
    }
    //入棧操作
    func push(obj: Int) {
        datas.append(obj)
    }
    //棧頂對象
    func top() -> Int? {
        return datas.last
    }
}

4.棧在實際開發(fā)過程中的應(yīng)用

棧在函數(shù)調(diào)用中的應(yīng)用

class Calculate {

  func calculate() {
      let a = 3
      let b = 5
      var result = 0
      result = add(x: a, y: b)
      print(result)
  }

  func add(x: Int, y: Int) -> Int {
      var sum= 0
      sum = x + y
      return sum
  }
}

從代碼中我們可以看出，calculate() 函數(shù)調(diào)用了 add() 函數(shù)，傳入臨時變量a和b，獲取計算結(jié)果，最后打印 result 的值。為了讓你清晰地看到這個過程對應(yīng)的函數(shù)棧里出棧、入棧的操作，我畫了一張圖。圖中顯示的是，在執(zhí)行到 add() 函數(shù)時，函數(shù)調(diào)用棧的情況。

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

遞歸

在算法中，經(jīng)常會使用的一個思想就是遞歸思想。很著名的就是斐波那契數(shù)列[2]

F(0) =0，
F(1) =1，
F(n) = F(n-1)+F(n-2)（n≥2，n∈N*）

計算F(n)時需要先計算F(n-1)和F(n-2)，
計算F(n-1)時需要先計算F(n-2)和F(n-3)，
計算F(n-2)時需要先計算F(n-2)和F(n-3)
···
最后的效果是，會有很多中間值壓入棧中，這也是為什么，當(dāng) n很大的時候，會非常消耗內(nèi)存。所以在實際的開發(fā)中，掌握這些底層的開發(fā)基礎(chǔ)，會有助你選擇合適的技術(shù)方案。

5.概念區(qū)分：數(shù)據(jù)結(jié)構(gòu)堆棧 VS 內(nèi)存中的堆棧

在學(xué)習(xí)計算機(jī)基礎(chǔ)的時候，我們知道內(nèi)存中有棧區(qū)和堆區(qū)。那它與數(shù)據(jù)結(jié)構(gòu)中的堆棧有什么區(qū)別了，它們是同一個概念嗎？

內(nèi)存中的堆棧和數(shù)據(jù)結(jié)構(gòu)堆棧不是一個概念，可以說內(nèi)存中的堆棧是真實存在的物理區(qū)，數(shù)據(jù)結(jié)構(gòu)中的堆棧是抽象的數(shù)據(jù)存儲結(jié)構(gòu)。
內(nèi)存空間在邏輯上分為三部分：代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)和動態(tài)數(shù)據(jù)區(qū)，動態(tài)數(shù)據(jù)區(qū)又分為棧區(qū)和堆區(qū)。
代碼區(qū)：存儲方法體的二進(jìn)制代碼。高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度（內(nèi)存調(diào)度）、低級調(diào)度（進(jìn)程調(diào)度）控制代碼區(qū)執(zhí)行代碼的切換。
靜態(tài)數(shù)據(jù)區(qū)：存儲全局變量、靜態(tài)變量、常量，常量包括final修飾的常量和String常量。系統(tǒng)自動分配和回收。
棧區(qū)：存儲運(yùn)行方法的形參、局部變量、返回值。由系統(tǒng)自動分配和回收。
堆區(qū)：new一個對象的引用或地址存儲在棧區(qū)，指向該對象存儲在堆區(qū)中的真實數(shù)據(jù)。

6.解答開篇

好了，我想現(xiàn)在你已經(jīng)完全理解了棧的概念。我們再回來看看開篇的思考題，如何實現(xiàn)有效括號的判斷？其實使用棧的思想就可以非常完美的解決這個問題。

我們開始分析：

• 1.如果開始就是右括號)、]、}，很明顯不合法，直接返回false
• 2.如果是左括號 (、[、{，就壓棧。如果是右括號)、]、}，在stack有值的情況下與棧定元素匹配，匹配通過則棧頂元素出棧，否則直接返回false。

下面是 swift解題的實現(xiàn)代碼

class Solution {
      
    func isValid(_ s: String) -> Bool {
        
        if s.count == 0  { return false }
        var stack = [String]()
        let dict: [String:String] = ["(":")","[":"]","{":"}"]
        
        for c in s {
            if dict.keys.contains(c.description) {
                stack.append(c.description) //如果是左括號就入棧
            }else {
                if stack.count > 0 && c.description == dict[stack.last!] { //如果是右括號，并且匹配就出棧
                    stack.removeLast()
                }else {
                    return false
                }
            }
        }
        return stack.count == 0
    }
}

在LeetCode上也有很多種語言的解法，這里分享一個python[3]的解法

7.內(nèi)容總結(jié)

我們來回顧一下今天講的內(nèi)容。棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，只支持入棧和出棧操作。后進(jìn)先出是它最大的特點(diǎn)。我們還知道數(shù)據(jù)結(jié)構(gòu)中的堆棧和內(nèi)存中的堆棧不是同一個概念。我們也理解了棧在實際開發(fā)中的些應(yīng)用，以及使用遞歸，當(dāng)n值很大地時候,會有大量的臨時變量被壓如棧中而消耗內(nèi)存。以及最后通過棧的核心思想來解LeetCode中比較經(jīng)典的算法題。

相信你也真正的掌握了棧這種數(shù)據(jù)結(jié)構(gòu)了。那趕緊動手敲代碼來實踐吧！

參考資料：

• 1.棧的定義
• 2.斐波那契數(shù)列
• 3.python語言實現(xiàn)