Java棧應用實例

一、棧的簡介

棧是一種非常常用的數據結構，它是一種線性結構，具有後進先出（LIFO）的性質，即最後入棧的元素最先出棧。棧通常只允許在棧頂進行插入和刪除操作，其它位置均不可訪問。

在Java中，棧通常指的是調用棧（call stack），是用來保存函數調用狀態的內存區域。在函數調用時，每一個函數都會在棧上開闢一塊用於保存該函數的局部變量、參數、返回地址等信息，函數返回時再將對應的信息出棧，使得程序可以回到函數被調用的位置。

二、棧的應用場景

棧作為一種常用的數據結構，在許多場景下都有應用。以下是一些典型的棧的應用場景：

1. 表達式求值

在計算機中，算術表達式往往是以中綴表達式的形式出現的，而計算時往往需要將其轉化為後綴表達式，然後通過棧來計算。具體的實現方式是，遍歷中綴表達式並依次將各個元素入棧，當遇到操作符時，將前面兩個元素出棧，計算後的結果再入棧。最後棧中剩下的元素即為計算後的結果。

2. 括號匹配

在編程中，經常需要判斷一個字符串中的括號是否匹配。此時可以利用棧的後進先出的特性，將遇到的左括號依次入棧，遇到右括號時如果棧頂是對應的左括號則彈出，否則說明括號不匹配。

3. 瀏覽器的前進和後退

當用戶在瀏覽器中訪問不同的頁面時，瀏覽器會將每個頁面的URL保存在一個歷史記錄棧中。當用戶點擊後退按鈕時，瀏覽器將從棧頂彈出一個URL並加載該頁面，當用戶點擊前進按鈕時，則將棧頂的URL入棧並打開對應的頁面。

/**
 * 表達式求值
 * 
 * @param exp 中綴表達式數組
 * @return 表達式的計算結果
 */
public static int evaluateExpression(String[] exp) {
    Stack stack = new Stack();
    for (String s : exp) {
        if (isNumber(s)) {
            stack.push(Integer.parseInt(s));
        } else {
            int x = stack.pop();
            int y = stack.pop();
            switch (s) {
                case "+":
                    stack.push(y + x);
                    break;
                case "-":
                    stack.push(y - x);
                    break;
                case "*":
                    stack.push(y * x);
                    break;
                case "/":
                    stack.push(y / x);
                    break;
            }
        }
    }
    return stack.pop();
}

/**
 * 判斷字符串是否為數字
 */
private static boolean isNumber(String s) {
    try {
        Integer.parseInt(s);
        return true;
    } catch (NumberFormatException e) {
        return false;
    }
}

三、棧的實現

Java中的棧可以通過繼承Vector（或ArrayList）來實現，也可以通過構造一個由數組支持的小容量的堆棧來實現。以下是一個基於鏈表的棧的實現示例：

/**
 * 基於鏈表的棧的實現
 * 
 * @param  棧中元素的類型
 */
public class LinkedStack<T> {

    private Node<T> top;  // 棧頂節點

    // 入棧操作
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
    }

    // 出棧操作
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T data = top.data;
        top = top.next;
        return data;
    }

    // 獲取棧頂元素
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    // 判斷棧是否為空
    public boolean isEmpty() {
        return top == null;
    }

    // 棧中節點定義
    private static class Node<T> {
        T data;           // 節點數據
        Node<T> next;  // 指向下一個節點的引用
        Node(T data) {
            this.data = data;
        }
    }
}