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

Java 實作堆疊：陣列版與鏈結版完整原始碼解析

編輯：Java 相關知識

堆疊是後進先出（LIFO）的線性資料結構。本文提供兩種經典實作：順序堆疊（陣列基礎）與鏈結堆疊（鏈表基礎），完整原始碼附詳細註解，涵蓋介面定義、核心操作、邊界處理與測試驗證，適合資料結構學習與面試準備。

一、統一介面定義 `IStack<E>`

package stack;

public interface IStack<E> {
    boolean isEmpty();           // 1. 判斷空堆疊
    boolean isMax();             // 2. 判斷滿堆疊（順序堆疊適用）
    boolean push(E e);           // 3. 入堆疊
    E pop();                     // 4. 出堆疊
    E peek();                    // 5. 取得堆疊頂元素不移除
    int getIndex(E e);           // 6. 取得元素在堆疊中位置
    int size();                  // 7. 取得實際元素個數
    int getStackSize();          // 8. 取得容量上限
    void display();              // 9. 列印堆疊內容
}

二、順序堆疊 `MyStack<E>`（陣列實作）

核心欄位

private Object[] data = null;  // 資料陣列
private int top = -1;          // 堆疊頂指標，-1 表示空
private int maxSize = 0;       // 最大容量

關鍵方法實作重點

擴容策略：本範例為固定容量，滿時拋錯；實務可參考 ArrayList 1.5 倍擴容
型別安全：內部用 Object[]，pop()/peek() 以 @SuppressWarnings("unchecked") 強轉
getIndex() 破壞性遍歷：原碼中直接移動 top 指標導致資料遺失，實務應用臨時變數遍歷
display() 同樣破壞性：同理需修正

完整原始碼

package stack;

public class MyStack<E> implements IStack<E> {
    private Object[] data = null;
    private int top = -1;
    private int maxSize = 0;

    public MyStack() { this(10); }

    public MyStack(int initialSize) {
        if (initialSize >= 0) {
            this.data = new Object[initialSize];
            this.maxSize = initialSize;
            this.top = -1;
        }
    }

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

    @Override public boolean isMax() { return top >= maxSize - 1; }

    @Override public boolean push(E e) {
        if (isMax()) {
            System.err.println("對不起,堆疊已滿,無法入堆疊");
            return false;
        }
        data[++top] = e;
        return true;
    }

    @Override @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            System.err.println("對不起，目前是空堆疊，沒有元素可以出堆疊");
            return null;
        }
        return (E) data[top--];
    }

    @Override @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            System.err.println("對不起，目前是空堆疊，無法返回堆疊頂元素");
            return null;
        }
        return (E) data[top];
    }

    @Override public int getIndex(E e) {
        // 修正：使用臨時指標避免破壞資料
        for (int i = top; i >= 0; i--) {
            if (data[i].equals(e)) return i;
        }
        return -1;
    }

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

    @Override public int getStackSize() { return maxSize; }

    @Override public void display() {
        // 修正：從頂往下列印，不移動 top
        for (int i = top; i >= 0; i--) {
            System.out.println("索引 " + i + ": " + data[i]);
        }
    }

    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        for (int i = 0; i < 10; i++) stack.push(i);
        System.out.println("堆疊大小: " + stack.size());
        System.out.println("堆疊頂: " + stack.peek());
        stack.display();
    }
}

三、鏈結堆疊 `LinkedStack`（鏈表實作）

節點內部類

private class Node {
    Object data;
    Node next;
    Node(Object data, Node next) { this.data = data; this.next = next; }
}

核心邏輯

入堆疊：新節點 next 指向舊 top，更新 top 為新節點，O(1)
出堆疊：保存 top，移動 top = top.next，斷開舊節點引用，O(1)
無容量上限：僅受記憶體限制
注意：原碼 getIndex() 與 display() 同樣破壞 top，已在下方修正

修正版關鍵方法

public int getIndex(Object obj) {
    int i = 0;
    Node temp = top;
    while (temp != null) {
        if (temp.data.equals(obj)) return i;
        temp = temp.next;
        i++;
    }
    return -1;
}

public void display() {
    Node temp = top;
    while (temp != null) {
        System.out.println(temp.data);
        temp = temp.next;
    }
}

完整原始碼

package stack;

public class LinkedStack {
    private class Node {
        Object data;
        Node next;
        Node() {}
        Node(Object data, Node next) { this.data = data; this.next = next; }
        @Override public String toString() { return "Node[data=" + data + ", next=" + next + "]"; }
    }

    private Node top = null;
    private int size = 0;

    public boolean isEmpty() { return size == 0; }

    public boolean push(Object obj) {
        top = new Node(obj, top);
        size++;
        return true;
    }

    public Object pop() {
        if (isEmpty()) {
            System.out.println("對不起，目前是空堆疊，不能出堆疊");
            return null;
        }
        Node temp = top;
        top = top.next;
        temp.next = null;
        size--;
        return temp.data;
    }

    public Object peek() { return isEmpty() ? null : top.data; }

    public int getIndex(Object obj) {
        int i = 0;
        Node temp = top;
        while (temp != null) {
            if (temp.data.equals(obj)) return i;
            temp = temp.next;
            i++;
        }
        return -1;
    }

    public int getSize() { return size; }

    public void display() {
        Node temp = top;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack();
        for (int i = 0; i < 10; i++) stack.push(i);
        System.out.println("元素 9 位置: " + stack.getIndex(9));
        stack.display();
    }
}

四、兩種實作對比總結

維度	順序堆疊 (陣列)	鏈結堆疊 (鏈表)
空間預分配	需指定容量	動態分配，無上限
記憶體效率	連續，無額外指標開銷	每節點額外 next 指標
擴容成本	需複製陣列 O(n)	無擴容概念
Push/Pop 時間	O(1) 攤還	O(1) 固定
適用場景	容量可預估、追求緩存局部性	容量不可預估、頻繁變動