您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

數據結構精講：棧的定義、數組/鏈表實現、JDK Stack 源碼分析與自定義封裝

編輯：Java 綜合教學

數據結構精講：棧的定義、數組/鏈表實現、JDK Stack 源碼分析與自定義封裝

棧是「後進先出」的線性結構，操作受限於棧頂。本文從定義出發，對比數組與鏈表實現，深度解析 JDK java.util.Stack 繼承 Vector 的設計缺陷，並提供可生產使用的泛型棧實現（含擴容、縮容策略）與單元測試。

一、棧的核心特徵

LIFO：Last In First Out，後進先出。
單端操作：僅在棧頂進行 push/pop/peek，不允許中間插入/刪除/查找。

符合以上兩點的容器即為棧，與底層存儲（數組/鏈表）無關。

二、JDK Stack 源碼剖析與吐槽


public class Stack<E> extends Vector<E> {
    public E push(E item) { addElement(item); return item; }
    public synchronized E pop() { ... }
    public synchronized E peek() { ... }
    public boolean empty() { return size() == 0; }
    public int search(Object o) { ... } // 從頂往下 1-based 索引
}

設計缺陷：

繼承 Vector：暴露 add(index, elem)、set(index, elem)、remove(index) 等破壞 LIFO 的方法。
方法全 synchronized：單線程場景性能損耗大（推薦用 ArrayDeque）。
非泛型早期設計：Java 5 前無泛型，現已不推薦直接使用。

Stack.java 類圖 Vector.java 方法列表

三、自定義泛型棧實現

介面定義


public interface Stack<E> {
    void push(E e);
    E pop();
    E peek();
    boolean isEmpty();
    int size();
}

1. 數組實現（支援動態擴容/縮容）


public class ArrayStack<E> implements Stack<E> {
    private static final int DEFAULT_CAPACITY = 16;
    private Object[] elements;
    private int top = -1;           // 棧頂索引
    private final float loadFactor; // 裝載因子觸發擴容
    private final boolean shrinkable; // 是否支援縮容

    public ArrayStack() { this(DEFAULT_CAPACITY, 0.75f, true); }
    public ArrayStack(int initCap, float lf, boolean shrink) {
        elements = new Object[Math.max(initCap, 1)];
        this.loadFactor = lf;
        this.shrinkable = shrink;
    }

    @Override public void push(E e) {
        ensureCapacity(top + 2);
        elements[++top] = e;
    }

    @Override @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) return null;
        E e = (E) elements[top];
        elements[top--] = null; // 幫助 GC
        if (shrinkable && top + 1 < elements.length / 4) shrink();
        return e;
    }

    @Override @SuppressWarnings("unchecked")
    public E peek() { return isEmpty() ? null : (E) elements[top]; }
    @Override public boolean isEmpty() { return top == -1; }
    @Override public int size() { return top + 1; }

    private void ensureCapacity(int minCap) {
        if (minCap > elements.length) {
            int newCap = Math.max(minCap, (int)(elements.length * 1.5));
            elements = Arrays.copyOf(elements, newCap);
        }
    }
    private void shrink() {
        int newCap = Math.max(DEFAULT_CAPACITY, elements.length / 2);
        elements = Arrays.copyOf(elements, newCap);
    }
}

2. 鏈表實現（簡潔、無擴容煩惱）


public class LinkedStack<E> implements Stack<E> {
    private static class Node<E> {
        E item; Node<E> next;
        Node(E item, Node<E> next) { this.item = item; this.next = next; }
    }
    private Node<E> top;
    private int size;

    @Override public void push(E e) { top = new Node<>(e, top); size++; }
    @Override public E pop() {
        if (top == null) return null;
        E item = top.item;
        top = top.next;
        size--;
        return item;
    }
    @Override public E peek() { return top == null ? null : top.item; }
    @Override public boolean isEmpty() { return top == null; }
    @Override public int size() { return size; }
}

四、單元測試驗證


public class StackTest {
    @Test public void testArrayStack() {
        Stack<Integer> s = new ArrayStack<>(5, 0.75f, false); // 固定容量測試溢出行為
        for (int i = 0; i < 10; i++) s.push(i);
        assertEquals(10, s.size());
        for (int i = 9; i >= 0; i--) assertEquals(Integer.valueOf(i), s.pop());
        assertTrue(s.isEmpty());
    }
    @Test public void testLinkedStack() {
        Stack<String> s = new LinkedStack<>();
        Stream.of("a","b","c").forEach(s::push);
        assertEquals("c", s.peek());
        assertEquals("c", s.pop());
        assertEquals("b", s.pop());
        assertEquals("a", s.pop());
        assertTrue(s.isEmpty());
    }
}