Stack源碼分析

文章目錄

• 底層資料結構
• 構造方法
• 進棧
• 獲得棧頂元素
• 出棧
• 查詢元素在棧中位置（下标）
• linkedList實作棧
• • 底層資料結構
  • 進棧
  • 出棧
  • 獲得棧頂元素
  • 是否是空棧

之前我們看過Vector，知道Vector是基于數組實作的，本文我們來看看Stack（棧）這種資料結構

棧是一種先進後出的資料結構，可以基于數組實作，也可以基于連結清單實作

java集合中的Stack是基于Vector實作的,對于Vector可以具體看Vector源碼分析

public
class Stack<E> extends Vector<E> 
           

底層資料結構

因為是基于Vector實作，是Vector的子類，是以同樣，Stack的底層資料結構是數組

public
class Stack<E> extends Vector<E> 

protected Object[] elementData;
           

構造方法

隻有一個預設的無參構造方法，調用構造一個空棧

public Stack() {
    }
           

進棧

進棧操作操作的數組的末端，數組的末端相當于棧頂

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

        return item;
    }
           

調用的是vector的添加元素的方法，預設是數組末端添加

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

獲得棧頂元素

peek()方法是線程安全的，也使用到了同步關鍵字，通過數組下标直接定位到棧頂元素，進而擷取

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

        if (len == 0)
            throw new EmptyStackException();
        //通過數組下标直接定位到棧頂元素    
        return elementAt(len - 1);
    }

    //傳回目前數組元素個數，這是Vector的API，在這裡是棧中元素個數
    public synchronized int size() {
        return elementCount;
    }

    //Vector的API，根據下标擷取值
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }
           

出棧

也是調用Vector的API直接點根據下标删除棧頂元素

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

        //擷取棧頂元素,傳回用
        obj = peek();
        //根據下标删除棧頂元素
        removeElementAt(len - 1);

        return obj;
    }

    //也是調用Vector的API直接點根據下标删除棧頂元素
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
           

查詢元素在棧中位置（下标）

public synchronized int search(Object o) {
        //從後往前找，在這裡可以看做從棧頂往棧底
        int i = lastIndexOf(o);

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

    //第二個參數是查詢的開始下标
    public synchronized int lastIndexOf(Object o) {
        return lastIndexOf(o, elementCount-1);
    }

    public synchronized int lastIndexOf(Object o, int index) {
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

        if (o == null) {
            for (int i = index; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
           

上面就是jdk中Stack的源碼，Stack在jdk中是基于順序存儲結構的數組實作的，也可以基于雙向連結清單的LinkedList實作，下邊看看如何用LinkedList實作棧

linkedList實作棧

底層資料結構

List<Integer> list;

    /** Initialize your data structure here. */
    public MyStack() {
       list = new LinkedList<>();
    }
           

進棧

進棧操作中，Vector操作的是數組末端，那麼linkedList也很類似，操作的是尾節點，連結清單末端就是棧頂

/** Push element x onto stack. */
    public void push(int x) {
        list.add(x);
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
           

出棧

public int pop() {
       int length = list.size();
       return list.remove(length);
    }
    
    //找到相關節點後，删除節點，解除連結關系
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
           

獲得棧頂元素

public int top() {
        int length = list.size();
        return list.get(length);
    }

    //通過下标找到相關節點後擷取節點值
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
           

是否是空棧

public boolean empty() {
        return list.isEmpty();
    }