Java棧學習筆記

一、棧數據結構

Java中棧是一種基本數據結構，它具有“後進先出”的特點：最後進入棧中的元素最先被取出。

Java中棧的實現方式有兩種：數組實現和鏈表實現。

//數組實現
public class ArrayStack {
    private int[] arr;
    private int top;//棧頂指針
    public ArrayStack(int capacity) {
        this.arr = new int[capacity];
        this.top = -1;
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        return top == arr.length - 1;
    }
    public void push(int data) {
        if (isFull()) {
            throw new RuntimeException("棧已滿");
        }
        arr[++top] = data;
    }
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空");
        }
        return arr[top--];
    }
}

鏈表實現的棧相對於數組實現的棧，在動態擴容方面更為便捷，在鏈表頭部進行插入和刪除操作更為高效。

二、基本應用

棧在Java中有很多基本應用，如函數調用棧、表達式求值、括號匹配檢查、漢諾塔等。

三、應用擴展

1. 單調棧

單調棧是基於棧數據結構實現的特化版本，其具有以下特點：

1) 只存儲特定方向的數據，在單調遞增棧中，棧從棧底到棧頂的元素是遞增的；在單調遞減棧中，棧從棧底到棧頂的元素是遞減的。

2) 當新元素入棧時，棧內原有比其小（大）的元素都會被彈出。從而能夠在O(n)的時間複雜度內解決一些很難用暴力算法解決的問題。

單調棧可以用於解決一些最值問題，如找出一個數組中元素右邊第一個比他大的數、找出一個數組中元素左右兩邊最近的比他大的數等。

public int[] findRightMax(int[] arr) {
    int len = arr.length;
    int[] res = new int[len];
    Stack<Integer> stack = new Stack();
    for(int i = 0; i < len; i++) {
        while(!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
            int top = stack.pop();
            res[top] = i;
        }
        stack.push(i);
    }
    while(!stack.isEmpty()) {
        res[stack.pop()] = -1;
    }
    return res;
}

2. 模擬遞歸

在遞歸中，函數調用棧起着關鍵作用。但是在某些情況下，遞歸調用棧可能會耗盡堆棧空間，尤其在計算深度大的遞歸時。

為了克服這個問題，我們可以使用Java中的棧數據結構自己實現遞歸調用。

public static int recursion(int n) {
    Stack<Integer> stack = new Stack();
    int res = 0;
    stack.push(n);
    while(!stack.isEmpty()) {
        int tmp = stack.pop();
        if(tmp == 1) {
            res += 1;
        } else {
            stack.push(tmp - 1);
            stack.push(tmp - 2);
        }
    }
    return res;
}

3. 開發工具

在Java開發中，棧也被廣泛應用於開發工具的實現。如命令行模式下的命令歷史棧，文本編輯器中的撤銷操作棧等。

四、總結

本文通過對Java中棧數據結構的分析，詳細介紹了棧的基本應用，及擴展的應用在Java中的實際應用。了解和熟練運用Java中的棧數據結構可以幫助我們更好地解決實際問題。