棧與隊列經典應用：括號匹配、表達式求值（中綴/後綴）、遞歸模擬與層次遍歷

棧與隊列經典應用

棧（LIFO）與隊列（FIFO）是最基礎的資料結構，廣泛應用於語法分析、運算式計算、樹圖遍歷等場景。

1. 棧常見應用

1.1 括號匹配

演算法：遍歷字串，左括號進棧；遇右括號則出棧比對型別，若不匹配或最終棧非空則失敗。

public static boolean isMatching(String match) {
    Stack<Character> stack = new Stack<>();
    for (char ch : match.trim().toCharArray()) {
        if (ch == '[' || ch == '(') stack.push(ch);
        else if (ch == ']') { if (stack.isEmpty() || stack.pop() != '[') return false; }
        else if (ch == ')') { if (stack.isEmpty() || stack.pop() != '(') return false; }
    }
    return stack.isEmpty();
}

1.2 運算式求值

支援 + - * / ( )，優先級處理關鍵在於棧內優先級 (isp)與棧外優先級 (icp)：

1.2.1 直接中綴求值（雙棧法）

• 操作數棧 vals、運算子棧 ops。
• 掃描字元：數字入 vals；運算子比較 icp 與 isp，大則進棧，小則彈出計算；右括號觸發計算至左括號。
• 掃描結束 (#) 清空 ops 計算，vals 頂為結果。

public static double infix(String expr) {
    Stack<String> ops = new Stack<>();
    Stack<Double> vals = new Stack<>();
    ops.push("#");
    for (char ch : expr.trim().toCharArray()) {
        String op = String.valueOf(ch);
        if ("#".equals(op)) {
            while (!"#".equals(ops.peek()))
                vals.push(calculate(vals.pop(), vals.pop(), ops.pop().charAt(0)));
        } else if (!opstr.contains(op)) {
            vals.push(Double.valueOf(op));
        } else {
            if (icp.get(op) > isp.get(ops.peek())) ops.push(op);
            else {
                while (icp.get(op) < isp.get(ops.peek()))
                    vals.push(calculate(vals.pop(), vals.pop(), ops.pop().charAt(0)));
                if (!")".equals(op)) ops.push(op);
                else ops.pop(); // 彈出 '('
            }
        }
    }
    return vals.pop();
}

1.2.2 中綴轉後綴 → 再求值

• 後綴表達式（逆波蘭式）無括號、優先級已隱含，計算極簡單：遇數字入棧，遇運算子彈出兩數計算入棧。
• 轉換演算法同雙棧法，但輸出改為字串緩衝區。

public static String infix2suffix(String expr) {
    Stack<String> ops = new Stack<>();
    StringBuilder sb = new StringBuilder();
    ops.push("#");
    for (char ch : expr.trim().toCharArray()) {
        String op = String.valueOf(ch);
        if ("#".equals(op)) {
            while (!"#".equals(ops.peek())) sb.append(ops.pop());
        } else if (!opstr.contains(op)) {
            sb.append(op);
        } else {
            if (icp.get(op) > isp.get(ops.peek())) { ops.push(op); continue; }
            while (icp.get(op) < isp.get(ops.peek())) sb.append(ops.pop());
            if (!")".equals(op)) ops.push(op);
            else ops.pop();
        }
    }
    return sb.toString();
}

1.3 遞歸與非遞歸

遞歸本質是系統維護呼叫棧。斐波那契數列遞歸實作效率低（重複計算），可轉為迭代或自定義棧模擬：

// 非遞歸迭代版
public static int NotRecur(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int n0 = 0, n1 = 1;
    while (n >= 2) { int tmp = n1 + n0; n0 = n1; n1 = tmp; n--; }
    return n1;
}

2. 隊列常見應用

2.1 層次遍歷 (BFS)

二叉樹層次遍歷、圖的廣度優先搜尋：根節點入隊，迴圈出隊訪問並將子節點入隊。

2.2 緩衝區

生產者-消費者模型，解決速度不匹配（如鍵盤輸入、網路封包、印表機列印）。