目錄

一、什麼是棧（Stack）

二、棧的基本操作

三、棧的存儲結構

四、棧的典型應用場景

1. 函數調用與返回（Call Stack）

2. 表達式求值與語法解析

3. 遞歸與回溯（Recursion & Backtracking）

4.其他算法中的應用

五、棧在 JVM 中的體現

1.JVM 棧的結構與作用

2. 操作數棧：JVM 的“計算引擎”

3. JVM 調用棧過程

六、棧與 JVM 的關係對照表

五、總結

一、什麼是棧（Stack）

棧（Stack） 是一種受限的線性數據結構，只能在一端（稱為 棧頂（Top））進行插入和刪除操作。
它遵循 後進先出（LIFO, Last In First Out） 的原則 —— 後放進去的元素先被取出。

可以把它想象成“疊盤子”的場景：

把盤子一個個疊上去 → 壓棧（push）

取盤子時只能從最上面拿 → 彈棧（pop）

這就是棧的直觀模型。

二、棧的基本操作

三、棧的存儲結構

棧可以通過兩種方式實現：

順序棧（Array Stack）：
使用數組實現，結構簡單、訪問高效。

常用於空間大小可預估的情況。

JVM 的操作數棧就是基於數組實現的。

鏈棧（Linked Stack）：
使用鏈表實現，插入刪除靈活，不需要預設大小。

適合棧深不確定的場景（如深度遞歸）。

四、棧的典型應用場景

1. 函數調用與返回（Call Stack）

當函數 A 調用函數 B 時：

函數 A 的局部變量與返回地址會被壓入棧；

JVM 跳轉執行函數 B；

當 B 執行完畢後，棧頂記錄被彈出，返回 A 的調用點繼續執行。

void A() {
    B();
}
void B() {
    System.out.println("Hello Stack");
}

執行流程：

A() 調用 → JVM 為 A 創建棧幀 → 壓棧
A 調用 B → JVM 為 B 創建棧幀 → 壓棧
B 執行完 → B 的棧幀出棧 → 返回 A
A 執行完 → A 的棧幀出棧

每個方法調用都對應着 一次入棧與出棧操作。
這就是我們常説的“調用棧”。

2. 表達式求值與語法解析

棧是編譯器和解釋器處理中綴表達式的關鍵結構。

例如表達式：

(1 + 2) * 3

求值過程（編譯器利用棧存儲操作符與中間結果）：

（1）讀取 ( → 壓棧（表示新的子表達式）

（2）讀取 1 → 壓棧（操作數）

（3）讀取 + → 壓棧（操作符）

（4）讀取 2 → 壓棧

（5）遇到 ) → 彈出操作符與操作數計算（得到 3），結果壓棧

（6）讀取 * → 壓棧

（7）讀取 3 → 壓棧

（8）彈出 * 與兩個操作數計算（得到 9）

最終結果為 9。

類似邏輯也用於：

括號匹配校驗（檢查是否“左括號=右括號”）

中綴轉後綴（逆波蘭表達式）

編譯器語法樹構建

3. 遞歸與回溯（Recursion & Backtracking）

遞歸調用的本質，就是函數不斷地入棧與出棧。

例如計算階乘：

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

執行 factorial(3) 的過程：

factorial(3) → 入棧
factorial(2) → 入棧
factorial(1) → 入棧
factorial(1) 返回 1 → 出棧
factorial(2) 返回 2 * 1 = 2 → 出棧
factorial(3) 返回 3 * 2 = 6 → 出棧

當最內層函數執行完畢後，系統會逐層彈棧返回結果。
這正是遞歸函數能“自動返回”的根本原因。

4.其他算法中的應用

DFS（深度優先搜索）：利用棧保存待訪問的節點

括號匹配：用棧判斷表達式是否合法

瀏覽器前進/後退：前進與回退分別用兩個棧保存歷史

撤銷（Undo）操作：通過棧記錄每次修改歷史，支持一步步撤銷

五、棧在 JVM 中的體現

JVM 是一台 基於棧的虛擬機。
這裏的“棧”指的是 每個線程獨有的 JVM 棧（Java Virtual Machine Stack）。
它記錄了方法調用過程與執行狀態，是 Java 程序運行的核心結構。

1.JVM 棧的結構與作用

當線程創建時，JVM 會為其分配一個獨立的 JVM 棧。
每次方法調用時，都會在這個棧中創建一個 棧幀（Stack Frame）。

每個棧幀包含以下關鍵部分：

當方法被調用時：棧幀入棧
當方法執行完畢時：棧幀出棧

每個線程的調用鏈條就是 JVM 棧幀的入棧與出棧過程。

2. 操作數棧：JVM 的“計算引擎”

JVM 並不像 CPU 一樣通過寄存器運算，而是依靠 操作數棧（Operand Stack） 來完成計算。

例如：

int a = 1;
int b = 2;
int c = a + b;

對應字節碼：

0: iconst_1    // 將常量1壓入棧
1: istore_1    // 彈出1，存入局部變量表槽1 (a)
2: iconst_2    // 壓入常量2
3: istore_2    // 彈出2，存入槽2 (b)
4: iload_1     // 取出a壓入操作數棧
5: iload_2     // 取出b壓入操作數棧
6: iadd        // 彈出兩個數相加，結果壓棧
7: istore_3    // 彈出結果，存入槽3 (c)

所有運算都通過“壓入棧 → 運算 → 彈出”完成。

這正是 JVM 基於棧結構執行指令的直接體現。

3. JVM 調用棧過程

例如：

public static void main(String[] args) {
    foo();
}
public static void foo() {
    bar();
}
public static void bar() {}

執行過程：

可以把調用棧理解為“任務清單疊疊樂”：
每次調用方法就是“加一張任務卡”，執行完就“拿掉最上面的那張”。

六、棧與 JVM 的關係對照表

五、總結

        棧（Stack）是一種遵循“後進先出”（LIFO）原則的線性數據結構，只能在一端進行插入和刪除操作，常用來保存臨時數據和控制程序執行流程。在計算機中，棧的思想貫穿編譯、運行與算法設計全過程：在算法中用於遞歸、回溯、括號匹配、撤銷操作等；在編譯器中用於表達式求值和語法解析；在 JVM 中，每個線程都有獨立的 JVM 棧，用來管理方法調用，通過“棧幀”的入棧與出棧保存局部變量、返回地址和計算過程，操作數棧則承擔所有計算任務。可以説，棧不僅是數據結構中的重要基礎，更是理解程序執行機制、方法調用過程和虛擬機底層原理的核心。