棧概念

棧是元素的集合, 其中有兩個(gè)原則操作:

• push, 它添加到集合中
• pop 則移除最近添加的元素

Push - 添加元素到棧里

下面是push,pop相關(guān)的幾個(gè)關(guān)鍵方法的源碼

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

    return item;
}


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


private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}


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);
}

push方法調(diào)用addElement(item)往棧里添加元素，elementData是一個(gè)object數(shù)組，addElement方法做的一件事就是把obj元素添加到elementData數(shù)組里，數(shù)組的長(zhǎng)度是固定的，
不斷添加元素肯定會(huì)超數(shù)組的容量，ensureCapacityHelper這個(gè)方法就是確認(rèn)數(shù)組的容量
是否足夠，不夠就進(jìn)行擴(kuò)充。接著看grow這個(gè)方法，進(jìn)行擴(kuò)充，oldCapacity變量記錄舊的數(shù)組長(zhǎng)度，newCapacity等于oldCapacity加上一個(gè)增量，capacityIncrement變量是增量，但默認(rèn)為0，可以在構(gòu)造器中賦值，capacityIncrement為0時(shí)，增量等于oldCapacity，newCapacity相當(dāng)于增加了一倍。最后調(diào)用Arrays的copyOf方法把原來的elementData數(shù)組復(fù)制到一個(gè)新的數(shù)組里。

Pop - 移除最近添加的元素

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);
}

pop方法：移除并返回移除棧頂?shù)脑?br> peek方法: 只是返回棧頂?shù)脑?/p>

pop方法是先調(diào)用peek方法獲取棧頂?shù)脑兀谡{(diào)用removeElementAt方法移除。

先看peek方法, 數(shù)組的index是從0開始，棧頂?shù)膇ndex就是len - 1, 最終實(shí)質(zhì)是返回elementData[index]即可。
接著看removeElementAt方法的實(shí)現(xiàn)

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 */
}

這個(gè)方法調(diào)用System.arraycopy()進(jìn)行復(fù)制數(shù)據(jù).

這個(gè)方法是native方法， 先了解一下這個(gè)方法的參數(shù)，

/**
 * src : 原數(shù)組
 * srcPos ： 原數(shù)組起始位置
 * dest ：目標(biāo)數(shù)組
 * destPos ： 目標(biāo)數(shù)組起始位置
 * length ： 復(fù)制數(shù)組的長(zhǎng)度
 **/
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

j = 數(shù)組長(zhǎng)度- index(需要移除的位置) - 1;
例如有{ a, b, c, d ,e } 共5個(gè)元素, 要移除c, 這里 j 等于 c 之后的元素個(gè)數(shù)，即2個(gè).

調(diào)用System.arraycopy方法時(shí)，原數(shù)組和目標(biāo)數(shù)組都是同一個(gè)，實(shí)質(zhì)上是把d,e 復(fù)制到原來c, d 的位置上，目標(biāo)數(shù)組為{ a, b, d, e, e}
最后elementCount減1，把數(shù)組elementData最后一個(gè)賦值null, 最終數(shù)組為{ a, b, d, e, null}