[系统运维]【码无巨细】Java Stack类的源码详解

力扣题

力扣有这么一道题，用两个栈实现队列，做过的小伙伴们应该都知道答案吧，其中栈的实现有两种，一种是Stack<E>，一种是LinkedList<E>接口，那么它们有什么区别呢？

本篇博客深入解析Stack源码，一起来看看吧！

源码

类注释

Stack<E>继承了Vector<E>类，为了实现栈的逻辑，Stack<E>额外实现了push,pop,peek,empty,search五个方法，这也是最常用的了。

首先，我们需要知道，Vector<E>是一种动态数组，其实现细节不在本篇讨论，只需要知道，它的底层是用数组实现的。

push

push(E item)方法会调用Vector.addElement(E obj)方法，并利用私有add方法实现其逻辑。

大意就是，向底层数组中靠后的位置插入一个元素，如果插入的位置到达了数组长度，就需要调用grow()扩张该数组，然后插入。

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

    return item;
}

public synchronized void addElement(E obj) {
    modCount++;
    add(obj, elementData, elementCount);
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    elementCount = s + 1;
}

至于grow()方法，当capacityIncrement > 0时，会将其作为扩容增量，否则，容量将扩至原来的2倍。扩容具体是使用了Arrays.copyOf方法。

privateObject[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth */
            capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                       /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

pop

pop方法也很简单，调用peek方法，获取要弹出的元素，然后调用Vector.removeElementAt删除size()-1位置的元素。删除元素的时候，要调用System.arraycopy把后续元素向前移动1个位置，即补上缺口。

public synchronized E pop() {
    E       obj;
    int     len = size();

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

    return obj;
}

public synchronized void removeElementAt(int index) {
    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);
    }
    modCount++;
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

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

E elementData(int index) {
    return (E) elementData[index];
}

empty

public boolean empty() {
    return size() == 0;
}

search

search方法是调用了Vector.lastIndexOf，获取对象o在底层数组中出现的最大索引，由于栈是后进先出，所以栈的search方法需要返回的是size()-i，即对象o距离栈顶的最近距离。如果对象在栈中不存在，则返回-1。

publicsynchronized int search(Object o) {
    int i = lastIndexOf(o);

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