栈概念
栈是元素的集合, 其中有两个原则操作:
- push, 它添加到集合中
- pop 则移除最近添加的元素
Push - 添加元素到栈里
下面是push,pop相关的几个关键方法的源码
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方法调用addElement(item)往栈里添加元素，elementData是一个object数组，addElement方法做的一件事就是把obj元素添加到elementData数组里，数组的长度是固定的，
不断添加元素肯定会超数组的容量，ensureCapacityHelper这个方法就是确认数组的容量
是否足够，不够就进行扩充。接着看grow这个方法，进行扩充，oldCapacity变量记录旧的数组长度，newCapacity等于oldCapacity加上一个增量，capacityIncrement变量是增量，但默认为0，可以在构造器中赋值，capacityIncrement为0时，增量等于oldCapacity，newCapacity相当于增加了一倍。最后调用Arrays的copyOf方法把原来的elementData数组复制到一个新的数组里。
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方法：移除并返回移除栈顶的元素
peek方法: 只是返回栈顶的元素
pop方法是先调用peek方法获取栈顶的元素，在调用removeElementAt方法移除。
先看peek方法, 数组的index是从0开始，栈顶的index就是len - 1, 最终实质是返回elementData[index]即可。
接着看removeElementAt方法的实现
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 */
}
这个方法调用System.arraycopy()进行复制数据.
这个方法是native方法， 先了解一下这个方法的参数，
/**
* src : 原数组
* srcPos ： 原数组起始位置
* dest ：目标数组
* destPos ： 目标数组起始位置
* length ： 复制数组的长度
**/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
j = 数组长度- index(需要移除的位置) - 1;
例如有{ a, b, c, d ,e } 共5个元素, 要移除c, 这里 j 等于 c 之后的元素个数，即2个.
调用System.arraycopy方法时，原数组和目标数组都是同一个，实质上是把d,e 复制到原来c, d 的位置上，目标数组为{ a, b, d, e, e}
最后elementCount减1，把数组elementData最后一个赋值null, 最终数组为{ a, b, d, e, null}
