java Stack源碼解析

本源碼解析基于JDK1.7

概要

• Stack是基于Vector實作的first-in-last-out資料結構
• Stack用同步來實作了線程安全，是以在單線程情況下該類會由于加鎖開銷而效率低
• Stack在Vector的基礎上增加了五個方法
  • push 入棧
  • pop 出棧
  • peek 取棧頂元素
  • empty 判斷棧空
  • search 傳回某個元素距離棧頂的距離
• JDK提供了更為完善的棧的實作，接口Deque及其實作ArrayDeque，其使用方法

  Deque<Integer> stack = new ArrayDeque<Integer>()

源碼解析

• 以下為全部源碼，其在Vector的基礎上，對棧資料結構進行了适配
• Stack實作方法比較簡陋，隻提供了預設的構造函數，Deque接口方法比較豐富，其實作類ArrayDeque
• 由于同步使得元素隻能串行使用，效率較低，如果想要使得Deque同步通過

  Deque<Integer> queue = new ArrayDeque<Integer>(); Collections.synchronizedCollection(queue);

  ，來實作同步
• 其改變棧結構的方法都是同步的，或者調用的Vector的同步的方法

public class Stack<E> extends Vector<E> {
    public Stack() {
    }
    public E push(E item) {
        addElement(item);
        return item;
    }
    public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
    public synchronized E peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    public boolean empty() {
        return size() == 0;
    }
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
    private static final long serialVersionUID = 1224463164541339165L;
}