从jdk里Stack源码的角度重温栈的实现

栈概念

栈是元素的集合, 其中有两个原则操作:

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

Push - 添加元素到栈里

下面是push,pop相关的几个关键方法的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 - 移除最近添加的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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方法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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方法, 先了解一下这个方法的参数,

1
2
3
4
5
6
7
8
9
10
/**
* 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}

Loading comments box needs to over the wall