Java中的棧實現

在Java中，?？梢酝ㄟ^數組或鏈表來實現。下面我們將分別介紹這兩種實現方式。

1. 使用數組實現棧

使用數組實現棧的優點是簡單直觀，但缺點是數組的大小是固定的，可能會導致棧溢出或空間浪費。

public class ArrayStack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public ArrayStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1;
    }

    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stackArray[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stackArray[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stackArray[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public int size() {
        return top + 1;
    }
}

2. 使用鏈表實現棧

使用鏈表實現棧的優點是棧的大小可以動態調整，不會出現棧溢出的問題。

public class LinkedListStack {
    private Node top;

    private class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        int count = 0;
        Node current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

棧的應用場景

棧在計算機科學中有著廣泛的應用，以下是一些常見的應用場景：

1. 函數調用棧

在程序執行過程中，函數的調用和返回是通過棧來管理的。每次調用一個函數時，系統會將函數的返回地址、局部變量等信息壓入棧中；當函數返回時，系統會從棧中彈出這些信息，恢復到調用函數前的狀態。

2. 表達式求值

?？梢杂糜诮馕龊陀嬎銛祵W表達式，特別是中綴表達式轉換為后綴表達式（逆波蘭表達式）的過程。通過棧，可以輕松處理運算符的優先級和括號的嵌套。

3. 括號匹配

?？梢杂糜跈z查代碼中的括號是否匹配。例如，檢查一個字符串中的括號是否成對出現，并且順序正確。

4. 瀏覽器歷史記錄

瀏覽器的“后退”和“前進”功能可以通過棧來實現。每次訪問一個新頁面時，將頁面壓入棧中；點擊“后退”按鈕時，從棧中彈出頁面。

總結

棧是一種簡單但功能強大的數據結構，它在Java中的實現可以通過數組或鏈表來完成。棧的“后進先出”特性使其在函數調用、表達式求值、括號匹配等場景中非常有用。理解棧的實現和應用場景，對于掌握數據結構和算法至關重要。通過本文的介紹，希望讀者能夠對Java中的棧實現有更深入的理解，并能夠在實際編程中靈活運用。