栈实现

栈是先进先出数据结构。
下面基于数组，实现栈结构。

Stack继承Vector

public class Stack<E> extends Vector<E> {
}

public class Vector<E> extends AbstractList<E> implements List<E>,
        RandomAccess, Cloneable, Serializable{
    /**
     * The number of elements or the size of the vector.
     */
    protected int elementCount;

    /**
     * The elements of the vector.
     */
    protected Object[] elementData;
    ...
}

elementData：Object数组
elementCount：数量。

入栈与出栈

出栈Stack#pop方法。

public synchronized E pop() {
    if (elementCount == 0) {//空栈出栈异常
        throw new EmptyStackException();
    }
    final int index = --elementCount;//元素数量-1，栈顶索引
    final E obj = (E) elementData[index];//弹出Object。
    elementData[index] = null;//索引处元素置空。
    modCount++;
    return obj;
}

elementCount是数组元素数量，index是索引，出栈即返回数组的最后一个元素，元素位置处置空。等下次入栈时，将元素放入空位置处。区别Stack#peek方法。

public synchronized E peek() {
    try {
        return (E) elementData[elementCount - 1];
    } catch (IndexOutOfBoundsException e) {
        throw new EmptyStackException();
    }
}

直接返回最后一个元素，数组索引位置不置空。
入栈Stack#push方法。

public synchronized void addElement(E object) {
    if (elementCount == elementData.length) {
        growByOne();//扩充数组。
    }
    elementData[elementCount++] = object;
    modCount++;
}

父类Vector#addElement方法，当元素数量达到数组长度上限时，扩充数组，未达到上限时，在数组尾部elementCount索引处填充元素，且elementCount自增。
扩充数组Vector#growByOne方法。

private void growByOne() {
    int adding = 0;
    if (capacityIncrement <= 0) {
        if ((adding = elementData.length) == 0) {
            adding = 1;//新数组长度增1
        }
    } else {
        adding = capacityIncrement;
    }

    E[] newData = newElementArray(elementData.length + adding);
    System.arraycopy(elementData, 0, newData, 0, elementCount);
    elementData = newData;
}

创建一个新数组，容量在原有基础上增加adding，adding设置成capacityIncrement，native静态方法System#arraycopy拷贝旧数组数据到新数组，指针交指向新数组。

任重而道远