您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 實作堆疊與佇列資料結構完整教學與程式碼範例

編輯：Java 相關知識

前言：認識堆疊與佇列

在程式設計的世界裡，堆疊與佇列是兩種最基礎且重要的線性資料結構。它們通常作為演算法的輔助工具，生命週期較短，僅在執行期間存在。兩者的共同特點是存取受限——在特定時刻只能讀取或刪除一個資料元素，且底層實作機制對使用者透明（例如陣列或鏈結串列）。

一、堆疊：後進先出 (LIFO)

堆疊只允許在一端進行插入與刪除操作，稱為「堆疊頂」。其核心特性為後進先出，進堆疊與出堆疊的時間複雜度均為 O(1)，效能極高。

1. 陣列實作固定大小堆疊

使用陣列作為底層儲存結構，需預先指定容量。適合資料量可預估的場景。

public class StackS<T> {
    private int maxSize;
    private T[] array;
    private int top; // 指向堆疊頂元素的索引

    public StackS(int size) {
        this.maxSize = size;
        array = (T[]) new Object[maxSize];
        top = -1;
    }

    // 進堆疊
    public void push(T data) {
        if (!isFull()) array[++top] = data;
    }

    // 出堆疊
    public T pop() {
        if (isEmpty()) return null;
        return array[top--];
    }

    // 查看堆疊頂
    public T peek() {
        return array[top];
    }

    public boolean isEmpty() { return top == -1; }
    public boolean isFull() { return top == maxSize - 1; }
    public int size() { return top + 1; }
}

2. 鏈結串列實作動態堆疊

若不想受限於固定大小，可使用 LinkedList 實作，自動擴容。

public class StackSS<T> {
    private LinkedList<T> data = new LinkedList<>();

    public void push(T data) { this.data.addLast(data); }
    public T pop() { return this.data.removeLast(); }
    public T peek() { return this.data.getLast(); }
    public boolean isEmpty() { return this.data.isEmpty(); }
    public int size() { return this.data.size(); }
}

3. 實戰應用：字串反轉

利用堆疊「後進先出」特性，輕鬆實現字串逆序。

public class WordReverse {
    public static void reverse(String word) {
        if (word == null) return;
        StackSS<Character> stack = new StackSS<>();
        for (char c : word.toCharArray()) stack.push(c);
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());
        System.out.println("反轉後：" + sb.toString());
    }
}

二、佇列：先進先出 (FIFO)

佇列模擬現實生活中的排隊情境，先來的先處理。插入與刪除操作時間複雜度同為 O(1)。

1. 環狀陣列實作普通佇列

使用頭尾指標 front、rear 循環利用陣列空間，避免資料搬移。

public class QueueQ<T> {
    private T[] array;
    private int front, rear, count, maxSize;

    public QueueQ(int size) {
        maxSize = size;
        array = (T[]) new Object[maxSize];
        front = 0; rear = -1; count = 0;
    }

    public void insert(T item) {
        if (rear == maxSize - 1) rear = -1; // 循環到頭
        array[++rear] = item;
        count++;
    }

    public T remove() {
        T temp = array[front++];
        if (front == maxSize) front = 0;
        count--;
        return temp;
    }
    // ... peek, isEmpty, isFull, size 等方法
}

2. 雙端佇列

兩端皆可插入/刪除，結合堆疊與佇列功能。以 LinkedList 實作最簡潔。

public class QueueQT<T> {
    private LinkedList<T> list = new LinkedList<>();
    public void insertLeft(T t) { list.addFirst(t); }
    public void insertRight(T t) { list.addLast(t); }
    public T removeLeft() { return list.removeFirst(); }
    public T removeRight() { return list.removeLast(); }
    // ... peekLeft, peekRight, isEmpty, size
}

3. 優先權佇列

元素依優先權排序，插入時需比較定位 O(N)，刪除 O(1)。適合任務排程等場景。

public class QueueQP {
    private int[] array;
    private int count, maxSize;

    public void insert(int item) {
        int j;
        if (count == 0) array[count++] = item;
        else {
            for (j = count - 1; j >= 0; j--) {
                if (item > array[j]) array[j + 1] = array[j];
                else break;
            }
            array[j + 1] = item;
            count++;
        }
    }
    public int remove() { return array[--count]; } // 移除優先權最低
}