作者 | 無量測試之道
編輯 | 小 晴
有效括号，刷過LeetCode的也許對這道題很熟悉。
1.開篇問題：有效的括号 [1]
[1]
假如現在要你來解這道題，你會想到怎樣的解法了？
這就要用到我們今天要講的“棧”這種資料結構。帶着這個問題，我們來學習今天的内容。
2.如何了解“棧”？
關于棧，有一個非常貼切的遊戲--漢諾塔。玩這個遊戲的時候，我們都是從下往上一個一個放；取的時候，我們也是從上往下一個一個地依次取，不能從中間任意抽出。後進者先出，先進者後出，這就是典型的“棧”結構。
從棧的操作特性上來看，棧是一種“操作受限”的線性表，隻允許在一端插入和删除資料。
棧的定義
[2]
：
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和删除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。
3.如何實作棧
從剛才棧的定義裡，我們可以看出，棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個資料和從棧頂删除一個資料。了解了棧的定義之後，我們來看一看如何用代碼實作一個棧。
【本文使用
swift
語言來編寫代碼，讀者朋友們不要因為程式設計語言不同而有畏難情緒，重要的是思維和邏輯，語言隻是表達方式。你可以用你自己熟悉的語言來表達你的邏輯，可以先試着寫一寫】
Talking is cheap，show you the code.
class Stack {
//初始化數組
var datas = [Int]()
//出棧操作
func pop() -> Int? {
return datas.popLast()
}
//入棧操作
func push(obj: Int) {
datas.append(obj)
}
//棧頂對象
func top() -> Int? {
return datas.last
}
} 複制
4.棧在實際開發過程中的應用
- 棧在函數調用中的應用
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() 函數調用了 add() 函數，傳入臨時變量a和b，擷取計算結果，最後列印 result 的值。
為了讓你清晰地看到這個過程對應的函數棧裡出棧、入棧的操作，我畫了一張圖。圖中顯示的是，在執行到 add() 函數時，函數調用棧的情況。
- 遞歸
在算法中，經常會使用的一個思想就是遞歸思想。很著名的就是斐波那契數列
[3]
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)
···
最後的效果是，會有很多中間值壓入棧中，這也是為什麼，當
n
很大的時候，會非常消耗記憶體。是以在實際的開發中，掌握這些底層的開發基礎，會有助你選擇合适的技術方案。
5.概念區分：資料結構堆棧 VS 記憶體中的堆棧
在學習計算機基礎的時候，我們知道記憶體中有棧區和堆區。那它與資料結構中的堆棧有什麼差別了，它們是同一個概念嗎？
記憶體中的堆棧和資料結構堆棧不是一個概念，可以說記憶體中的堆棧是真實存在的實體區，資料結構中的堆棧是抽象的資料存儲結構。
記憶體空間在邏輯上分為三部分：代碼區、靜态資料區和動态資料區，動态資料區又分為棧區和堆區。
代碼區：存儲方法體的二進制代碼。進階排程（作業排程）、中級排程（記憶體排程）、低級排程（程序排程）控制代碼區執行代碼的切換。
靜态資料區：存儲全局變量、靜态變量、常量，常量包括final修飾的常量和String常量。系統自動配置設定和回收。
棧區：存儲運作方法的形參、局部變量、傳回值。由系統自動配置設定和回收。
堆區：new一個對象的引用或位址存儲在棧區，指向該對象存儲在堆區中的真實資料。
6.解答開篇
好了，我想現在你已經完全了解了棧的概念。我們再回來看看開篇的思考題，如何實作有效括号的判斷？其實使用棧的思想就可以非常完美的解決這個問題。
我們開始分析：
- 1.如果開始就是右括号
)、]、}
- 2.如果是左括号
(、[、{
)、]、}
下面是
swift
解題的實作代碼
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
[4]
的解法
7.内容總結
我們來回顧一下今天講的内容。棧是一種操作受限的資料結構，隻支援入棧和出棧操作。後進先出是它最大的特點。我們還知道資料結構中的堆棧和記憶體中的堆棧不是同一個概念。我們也了解了棧在實際開發中的些應用，以及使用遞歸，當
n
值很大地時候,會有大量的臨時變量被壓如棧中而消耗記憶體。以及最後通過棧的核心思想來解LeetCode中比較經典的算法題。
相信你也真正的掌握了棧這種資料結構了。那趕緊動手敲代碼來實踐吧！
參考資料：
-
1.有效的括号:
https://leetcode-cn.com/problems/valid-parentheses
-
2.棧的定義:
https://baike.baidu.com/item/%E6%A0%88/12808149?fr=aladdin
-
3.斐波那契數列:
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
-
4.python語言實作:
https://leetcode-cn.com/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/