Stack源碼分析

Stack類圖

Stack是java.util包下List接口下的一個集合子類，是一個棧，線程安全的。底層是通過繼承Vector實作的。

• AbstractList抽象類：List的抽象父類，實作一些List通用的方法。
• Cloneable接口：實作對象拷貝必須要實作的接口。
• Serializable接口：實作序列化必須要實作的接口。
• RandomAccess接口：用于定義數組實作随機通路的算法，ArrayList和Vector都實作了該接口。

Stack類屬性

Stack内部隻定義了一個序列化ID，其餘屬性都是繼承自Vector。

Vector源碼分析連結：https://blog.csdn.net/qq_42191317/article/details/96752763

Stack常用API

public Stack() {
    }
           

構造方法：空參，什麼也沒有處理，執行個體化的時候，父類的構造器也會執行個體化。

public E push(E item) {
        addElement(item);

        return item;
    }

    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
           

push方法：入棧一個元素，調用Vector的add方法實作，往數組末尾增加一個元素，時間複雜度O(1)

public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
           

peek方法：檢視目前棧頂元素，即數組的頭部元素，調用Vector的elementAt方法，根據下标通路，時間複雜度O(1)

public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
           

pop方法：出棧一個元素，調用Vector的removeElementAt方法，根據下标删除元素，由于棧後進先出的特性，每次删除的都是末尾元素，時間複雜度O(1)

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

empty方法：判空方法，判斷數組目前元素個數是否為0

public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
           

search方法：搜尋某個元素是否存在，存在傳回下标，不存在傳回-1，如果存在多個，傳回最後壓入的那個

總結

• Stack是一個棧結構，繼承自Vector，線程安全的。
• 入棧、出棧時間複雜度都是O(1)，查找某個元素時間複雜度O(n)。