Java Stack 堆疊

堆疊（Stack）是後進先出（LIFO）的資料結構。Java 提供 Stack 類別，但官方建議使用 Deque 實作。

引入套件

import java.util.Stack;
import java.util.Deque;
import java.util.ArrayDeque;

使用 Deque 實作（推薦）

Deque<String> stack = new ArrayDeque<>();

// 入棧
stack.push("A");
stack.push("B");
stack.push("C");

// 查看頂端（不移除）
String top = stack.peek();  // C

// 出棧
String item = stack.pop();  // C

System.out.println(stack);  // [B, A]

使用 Stack 類別

Stack<String> stack = new Stack<>();

// 入棧
stack.push("A");
stack.push("B");

// 出棧
String item = stack.pop();  // B

// 查看頂端
String top = stack.peek();  // A

// 其他方法
boolean empty = stack.empty();
int pos = stack.search("A");  // 1（從頂端算起的位置）

Stack vs Deque

// Stack（舊的，執行緒安全但較慢）
Stack<String> oldStack = new Stack<>();

// Deque（新的，推薦使用）
Deque<String> newStack = new ArrayDeque<>();

實用範例

括號匹配

public static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

System.out.println(isBalanced("([{}])"));  // true
System.out.println(isBalanced("([)]"));    // false

反轉字串

public static String reverse(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        stack.push(c);
    }
    
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.toString();
}

System.out.println(reverse("Hello"));  // olleH

後綴表達式計算

public static int evaluatePostfix(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (String token : tokens) {
        switch (token) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "-" -> {
                int b = stack.pop(), a = stack.pop();
                stack.push(a - b);
            }
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "/" -> {
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);
            }
            default -> stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

// 計算 (3 + 4) * 2 = 14
String[] postfix = {"3", "4", "+", "2", "*"};
System.out.println(evaluatePostfix(postfix));  // 14

瀏覽器歷史

public class BrowserHistory {
    private Deque<String> backStack = new ArrayDeque<>();
    private Deque<String> forwardStack = new ArrayDeque<>();
    private String current;
    
    public void visit(String url) {
        if (current != null) backStack.push(current);
        current = url;
        forwardStack.clear();
    }
    
    public String back() {
        if (!backStack.isEmpty()) {
            forwardStack.push(current);
            current = backStack.pop();
        }
        return current;
    }
    
    public String forward() {
        if (!forwardStack.isEmpty()) {
            backStack.push(current);
            current = forwardStack.pop();
        }
        return current;
    }
}

重點整理

• Stack 是 LIFO（後進先出）資料結構
• 推薦使用 ArrayDeque 而非 Stack 類別
• 主要操作：push（入棧）、pop（出棧）、peek（查看）
• 常用於括號匹配、表達式計算、DFS 等
• 需要執行緒安全時使用 Collections.synchronizedDeque()