前言

繼續Java常用數據結構分析之路，這次的主角是

類繼承關係

先來看Stack：

public class Stack extends Vector

原來Stack繼承了Vector，那再看Vector：

public class Vector
 extends AbstractList
 implements List, RandomAccess, Cloneable, java.io.Serializable

又是熟悉的感覺：

1. 繼承AbstractList抽象類，算是List模板的擴展；
2. 實現List接口，Vector屬於List的一種；
3. 實現RandomAccess接口，一個空接口，用來標記可以隨機訪問元素；
4. 實現Cloneable接口，可以被克隆；
5. 實現Serializable接口，可以被序列化；

總的來說，Stack和Vector其實都是List的一種實現，可以進行隨機訪問，子類中實現自己的特徵邏輯。

Vector源碼分析

重要屬性

// 用來存儲元素，該數組的大小就是Vector的容量大小，說明支持null
protected Object[] elementData;
// 當前已存儲元素的數量
protected int elementCount;
// 當容量不夠時，Vector擴充的大小
protected int capacityIncrement;
// Vector的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Vector使用數組來存儲元素，有意思的是開發人員可以自己控制每次擴容的大小。

構造函數

public Vector() {
 this(10); // 默認容量10
 }
  

public Vector(int initialCapacity) {
 this(initialCapacity, 0); // 默認擴容增量設置為0表示雙倍擴展
 }
 
// 可以設置擴容時增量大小
public Vector(int initialCapacity, int capacityIncrement) {
 super();
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 this.elementData = new Object[initialCapacity];
 this.capacityIncrement = capacityIncrement;
 }

使用無參構造函數創建Vector時，默認大小是10，且每次擴容時容量變成原來的兩倍。

重用方法

先來看擴容方法：

private int newCapacity(int minCapacity) {
 // overflow-conscious code
 int oldCapacity = elementData.length; // 因為已經滿了，所以是舊容量
 // 如果擴充容量值小於等於0，則直接擴充為原來的兩倍
 int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
 capacityIncrement : oldCapacity);
 // minCapacity一般是oldCapacity+1，即執行add操作擴容
 if (newCapacity - minCapacity <= 0) {
 if (minCapacity < 0) // overflow
 throw new OutOfMemoryError();
 return minCapacity;
 }
 return (newCapacity - MAX_ARRAY_SIZE <= 0)
 ? newCapacity
 : hugeCapacity(minCapacity);
 }

當執行add操作時，就有可能進行擴容，來看看add方法：

public synchronized boolean add(E e) {
 modCount++; // 記錄修改次數
 add(e, elementData, elementCount);
 return true;
 }
 
private void add(E e, Object[] elementData, int s) {
 if (s == elementData.length)
 elementData = grow(); // 擴容
 elementData[s] = e; // 增加新元素
 elementCount = s + 1; // 元素數量加1
 }
 
private Object[] grow() {
 return grow(elementCount + 1); // 擴充的最小容量是原數據量加1
 }
 
private Object[] grow(int minCapacity) {
 // 調用newCapacity獲取新容量，同時進行數組複製
 return elementData = Arrays.copyOf(elementData,
 newCapacity(minCapacity));
 }

注意到add(E e)方法增加了synchronized關鍵字，說明是線程安全的。其實，Vector大部分公開方法都有synchronized關鍵字，所以說Vector是線程安全的。

Vector中除了add(E e)還可以使用addElement(E obj)和insertElementAt(E obj, int index)來添加元素，內部實現大同小異。

有擴容，理論上也要有縮容，然而Vector沒有自動縮容邏輯，但提供了一個方法：

public synchronized void trimToSize() { 

 modCount++;
 int oldCapacity = elementData.length;
 if (elementCount < oldCapacity) {
 elementData = Arrays.copyOf(elementData, elementCount);
 }
 }

trimToSize方法可以將Vector的容量調整到元素數量大小。

說到Vector的容量，其實Vector是支持自定義設置大小的，使用setSize(int newSize)即可。

public synchronized void setSize(int newSize) {
 modCount++;
 if (newSize > elementData.length)
 grow(newSize);
 final Object[] es = elementData;
 for (int to = elementCount, i = newSize; i < to; i++)
 es[i] = null; // 不夠則補null，多了則剪去
 elementCount = newSize;
 }

如果設置的大小大於當前存儲的元素數量，則補null值；如果小於現有元素數量，則會剪去多餘元素。

遍歷方法

對應Vector，可以使用三種方法進行遍歷：

1. 使用iterator()或者listIterator()方法；
2. 使用elements()方法；
3. 使用forEach(Consumer super E> action)方法；

第一種方法中，使用iterator時，不可以對Vector進行add和remove操作；第二種方法中，使用elements時，可以使用add操作，但不可以使用remove操作；第三種方法，可以使用lambda表達式。

Vector的主要源碼分析就這麼多，還有一些導航方法，如indexOf、lastElement等實現邏輯都很簡單。

Stack源碼分析

Stack類繼承了Vector，也是使用數組進行元素存儲，其源碼很少，就提供了幾個公有方法，下面直接分析這些方法。

• push方法

public E push(E item) {
 // 直接調用Vector的addElement方法，將元素添加到數組尾部
 addElement(item);
 return item;
 }

• pop和peek方法

// 返回棧頂元素，並且在數組中刪除該元素
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); // 隨機訪問數組中最後一個元素
 }

• search方法

// 返回離棧頂最近的指定元素到棧頂的距離
// 從1開始
public synchronized int search(Object o) {
 int i = lastIndexOf(o); // 指定元素在數組中最後出現的位置
 if (i >= 0) { // 獲取差量
 return size() - i;
 }
 return -1;
 }

舉個例子：

基礎Stack：7 2 11 -6 5 8 66，執行下面的代碼：

 // 7 2 11 -6 5 8 66
 // 基本位置為1
 System.out.println("search操作，11距離頂部的距離：" + stack.search(11));
 System.out.println("search 7：" + stack.search(7));
 System.out.println("search 66：" + stack.search(66));
 stack.push(0);
 stack.push(0);
 stack.push(0);
 stack.push(9);
 stack.push(33); // 7 2 11 -6 5 8 66 0 0 0 9 33 
 stack.forEach(integer -> {
 System.out.print(integer + " ");
 }); 

 System.out.println();
 System.out.println("search 離頂部最近的0：" + stack.search(0));

總結

Stack和Vector的代碼都很簡單，使用數組進行數據存儲。Stack的先進後出特性很好用，常在算法題中得到應用；Vector雖然保證了線程安全，但考慮到大部分使用場景都是單線程模式，所以對效率稍有影響。

閱讀更多 Java小可愛 的文章

關鍵字: 常用 數據結構 線程