Stack源码解析

释放双眼,带上耳机,听听看~!

在前两篇我们已经介绍了两种底层是通过数组方式实现的集合类,它们分别是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集合。下面是底层源码。

publicclass Stack<E> extends Vector<E> {

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

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

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

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧