Stack源码解析

/ Java / 没有评论 / 199浏览

在前两篇我们已经介绍了两种底层是通过数组方式实现的集合类,它们分别是ArrayList集合和Vector集合。在这一篇中我们继续介绍另一种底层也是用数据方式实现的集合,它就是Stack集合。Stack与ArrayList和Vector相比,有自己独特的一些特性。正是因为Stack有自己独特的特性,所以在使用上Stack与ArrayList、Vector相比有些区别,所以下面我们先了解一下Stack集合的基本使用,然后在分析Stack集合的底层源码。

Stack也就是栈,它和其它集合相比它的特性就是后进先出,也就是后添加到Stack集合中的元素,会被添加到栈的最顶位置。下面我们看一下在Stack集合中的都包括哪些方法。

E push(E item)    // 把元素添加到栈中的顶部
E pop()           // 把栈顶的元素删除,并返回删除的当前元素
E peek()          // 查看当前栈中的栈顶元素
search(Object o)  // 返回元素在栈中的位置,注意栈顶元素返回的是1而不是0

下面我们通过一个简单的例子来演示上面方法的基本使用。

Stack stack = new Stack();
for (int i = 1; i <= 5; i++) {
stack.push(i);
}
System.out.println(String.format("查看栈中元素: %s", stack));
System.out.println(String.format("查看栈顶元素: %s", stack.peek()));
System.out.println(String.format("删除栈顶元素: %s", stack.pop()));
System.out.println(String.format("查看栈中元素: %s", stack));
System.out.println(String.format("查看元素索引: %s", stack.search(4)));
查看栈中元素: [1, 2, 3, 4, 5]
查看栈顶元素: 5
删除栈顶元素: 5
查看栈中元素: [1, 2, 3, 4]
查看元素索引: 1

下面我们分析一下Stack集合的底层源码,还是和ArrayList集合和Vector集合一样,我们先看一下Stack集合的初始化。

public Stack() {
}

源码中只有一个无参的构造主法,这就说明,在我们创建Stack对象时,并不会执行底层数组的初始化。

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) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
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);
}

上面的代码是Stack集合把元素添加到栈顶的方法,我们看上面的代码是不是感觉似曾相识,好像和Vector集合的底层源码一模一样。这是因为Stack集合是Vector集合的子类,也就是Stack集合默认继承了Vector集合。下面是底层源码。

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

所以我们可以理解为Stack集合的底层实现原理和Vector集合是一样的,包括底层数组的自动扩展规律等特性都是一样的。也就是说Stack集合和Vector集合一样当底层数据超过最大容量时,会自动扩展为原来的2倍容量来存储元素。

下面我们看一下Stack集合中其它方法的底层实现,因为这些方法逻辑已经在Vector集合中介绍过了,并且方法的实现逻辑比较简单,这里我们就不在详细分析了,只是简单展示。

public synchronized E peek() {
int len = size();

if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}

return elementData(index);
}
public synchronized E pop() {
E obj;
int len = size();

obj = peek();
removeElementAt(len - 1);

return obj;
}
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;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);

if (i >= 0) {
return size() - i;
}
return -1;
}