集合 - Stack 源码剖析 - 《Java 学习》

1. 基本原理
2. 核心方法的原理
- (1) push(E)
- (3) pop()
3. 源码分析总结

1. 基本原理

Stack 是继承自 Vector 来实现的，底层也是基于数组实现的
- Vector 是一种几乎和 ArrayList 一样的数据结构，底层也是基于数组来实现的；
- Vector 是 java 1.0 就提供的一个类，它是线程安全的，但是效率就会受影响，所以在 java 1.2 提供了 ArrayList 类，线程不安全，但是效率很高；
Stack 栈的特点：先进后出，跟队列的先进先出不一样；

2. 核心方法的原理

(1) push(E)

作用：放入一个元素到 Stack 的尾部，并会返回这个插入的元素
逻辑：
- 逻辑几乎和 ArrayList 的 add(element) 一样，只是 Vector 中的 addElement(E) 加了 synchronized，是线程安全的；
- push(E) 方法调用了父类中的线程安全的 addElement(E) 方法进行插入操作：
  - 检查插入新元素前，是否要扩容
    - 如果插入后的元素个数 > 数组容量，则扩容；
    - 如果没指定扩容大小的变量 capacityIncrement，则默认扩容到原容量的两倍大小；
    - 使用 JDK 底层的工具类 Arrays.copyOf(originalArray, newLength)，创建一个新容量的数组，将原数组的元素拷贝到新数组中； ```java public E push(E item) { addElement(item);
return item; }

//=======> Vector

protected Object[] elementData; // elementData.length 数组的容量

protected int elementCount; // 数组的元素个数 size

protected int capacityIncrement; // 可以指定扩容时，容量增长的大小

// 线程安全的 public synchronized void addElement(E obj) { modCount++;

// 检查插入新元素前，是否要扩容 ensureCapacityHelper(elementCount + 1);

// 插入新元素，且元素个数+1 elementData[elementCount++] = obj; }

private void ensureCapacityHelper(int minCapacity) { // 插入后的元素个数 > 数组容量，则扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;

// 如果不指定增长容量的大小，默认是扩容成两倍容量 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

<a name="sII7T"></a>
### (2) peak()
- 作用：读取栈尾的元素，并返回（仅仅读取）
- 逻辑：
   - 获取栈的元素个数 size；
   - 调用父类的线程安全的方法 elementAt(index) 读取元素
      - 使用数组的[size-1]，直接读取元素；
```java
public synchronized E peek() {
    int     len = size();
    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}
// =====> Vector
public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }
    return elementData(index);
}
E elementData(int index) {
    return (E) elementData[index];
}

(3) pop()

作用：从栈的尾部读取一个元素返回，并将这个元素从栈的尾部移除
逻辑：
- 使用线程安全的 peak() 方法读取栈尾部的元素，并返回；
- 使用父类线程安全的 removeElementAt(size-1) 移除栈尾部的元素； ```java public synchronized E pop() { E obj; int len = size();
  
  obj = peek(); removeElementAt(len - 1);
  
  return obj; }

//=====> Vector public synchronized void removeElementAt(int index) { modCount++; if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + “ >= “ + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); }

// 如果是栈尾部的元素，j=size-(size-1)-1=0，直接将最后的元素设成null
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 */

}

<a name="mEyxf"></a>
### (4) removeElementAt(index)

- 作用：移除栈内指定位置上的元素，不返回；
- 逻辑：
   - 如果是栈尾部的元素，就直接将数组此位置设置成 null；
   - 如果是其他位置，需要使用 JDK 底层的工具类 **System.arraycopy**(srcArray, srcPos, destArray, destPos, length) 将数组中的元素往前挪一位，且将最后一位空出来的设置成 null；
```java
//=====> Vector
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }

    // 如果是栈尾部的元素，j=size-(size-1)-1=0，直接将最后的元素设成null
    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 */
}

3. 源码分析总结

栈常用的操作就是 push() + pop()，入栈和出栈，都是对栈尾的元素进行操作；
底层是基于数组实现，如果是对栈尾进行操作，性能还是挺好的；