Java Stack 實作詳解：陣列與鏈表兩種實現方式及應用範例

什麼是 Stack（堆疊）？

Stack 是一種限制插入與刪除操作只能在一端進行的線性表，這一端稱為堆疊頂。其核心操作有 push（壓入）與 pop（彈出），遵循「後進先出」（LIFO）原則。雖然文中提到 FIFO，但正確應為 LIFO。

兩種經典實作方式

1. 陣列實作

public class MyArrayStack<E> {
    private ArrayList<E> list = new ArrayList<>();
    public void push(E e) { list.add(e); }
    public E pop() { return list.remove(list.size() - 1); }
    public E peek() { return list.get(list.size() - 1); }
    public boolean isEmpty() { return list.size() == 0; }
}

2. 鏈表實作

public class MyLinkStack<E> {
    private LinkedList<E> list = new LinkedList<>();
    public void push(E e) { list.addLast(e); }
    public E pop() { return list.removeLast(); }
    public E peek() { return list.getLast(); }
    public boolean isEmpty() { return list.size() == 0; }
}

實戰應用場景

符號平衡檢查

利用堆疊驗證程式碼中括號是否正確配對，例如 [{()}] 合法，[{]} 不合法。

public class BalanceSymbol {
    public boolean isBalance(String string) {
        MyArrayStack<Character> stack = new MyArrayStack<>();
        for (char ch : string.toCharArray()) {
            if ("{[(".indexOf(ch) >= 0) stack.push(ch);
            else if ("}])".indexOf(ch) >= 0) {
                if (isMatching(stack.peek(), ch)) stack.pop();
            }
        }
        return stack.isEmpty();
    }
    private boolean isMatching(char open, char close) {
        return (open == '{' && close == '}') || (open == '[' && close == ']') || (open == '(' && close == ')');
    }
}

後綴表達式求值

將中綴表達式 3 + 2 + 3 * 2 轉為後綴 3 2 + 3 2 * +，再用堆疊計算：遇數字入棧，遇運算符彈出兩數運算後入棧，最終結果即為棧頂元素。

public class PostfixExpression {
    public static int calculate(String expr) {
        MyArrayStack<String> stack = new MyArrayStack<>();
        for (char ch : expr.toCharArray()) {
            if (Character.isDigit(ch)) stack.push(String.valueOf(ch));
            else if ("+-*/".indexOf(ch) >= 0) {
                int a = Integer.parseInt(stack.pop());
                int b = Integer.parseInt(stack.pop());
                switch (ch) {
                    case '+': stack.push(String.valueOf(a + b)); break;
                    case '-': stack.push(String.valueOf(a - b)); break;
                    case '*': stack.push(String.valueOf(a * b)); break;
                    case '/': stack.push(String.valueOf(a / b)); break;
                }
            }
        }
        return Integer.parseInt(stack.peek());
    }
}

中綴轉後綴演算法

掃描運算元直接輸出；運算符入棧，遇左括號入棧；遇右括號彈出至左括號；遇其他運算符彈出優先級較高或相等的運算符。需建立優先級對照表。

public class ExpressionSwitch {
    private static Map<Character, Integer> priorityMap = new HashMap<>();
    private static char[][] priorityMatrix = { ... }; // 略
    public static String toPostfix(String infix) { ... } // 完整演算法見原文
}

掌握 Stack 實作與應用，是資料結構與演算法的基石，對解析器、編譯器、運算式求值等場景至關重要。