源码阅读之Java栈的实现

0x00 栈

栈是 Last-In-First-Out （后进先出）的线性表。对栈的操作主要有两个：入栈(push)和出栈(pop)。因此它也是一种操作受限的线性表。尽管如此，它在计算机中应用非常广泛，是一种非常基础的数据结构。

0x01 源码

从源码中可以看出栈也是一种非常简单的数据结构。栈的源码非常简洁，只有100多行代码。

public class Stack<E> extends Vector<E> {
     
    public Stack() {
    }

    //入栈操作
    public E push(E item) {
        addElement(item);

        return item;
    }

    //出栈操作
    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);
    }

    //检查是否为空栈
    public boolean empty() {
        return size() == 0;
    }

    //查找元素，如果找到则返回从栈顶开始计数的位置，否则返回-1
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

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

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

它继承于 Vector 类，这个跟前面讲的 ArrayList 是一样的，只不过 Vector 类方法是同步的，因此 Stack 也是线程安全的。

push

入栈

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

    return item;
}

虽然此方法没有声明 synchronized，但内部调用一个 addElement 来实现入栈操作。这个操作方法是在父类中实现的，它被声明为线程安全的，因此它也是线程安全的。

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);
}
//扩容方法
//这里跟 ArrayList 扩容算法有点不一样，ArrayList 一次是扩容为原来的1.5倍，Vector 默认扩容为原来的1倍
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 方法没有声明 synchronized 但 addElement 方法中有。在这个方法里

• 首先把 modCount 加 1，记录一次对数据结构的操作。
• 然后检查数组容量是否足够，不够则扩容。
• 最后把元素对象添加到数组末尾。

需要注意的是Vector的扩容策略是默认一次扩容为原来的1倍，这与ArrayList 一次扩容原来的1.5倍不同。

pop

出栈

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

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

    return obj;
}

pop 方法被声明为 synchronized ，是线程安全的方法。它通过 peek 方法获取到栈顶元素对象，然后调用父类的 removeElementAt 方法把栈顶元素删除。

peek

查看栈顶元素

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

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

这个方法也是线程安全的。可以看出如果栈的大小为0时，执行 peek 方法会抛出 EmptyStackException 异常。

search

在栈中搜索元素

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

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

继续查看父类代码

public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {//如果查找的元素是空的则遍历找到最接近栈的空元素
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))//通过equals方法来判断两个元素是否相同
                return i;
    }
    return -1;
}

在栈中查询一个元素需要遍历，时间复杂度为O(n)。

0x02 总结

栈是一种LIFO的数据结构，它基于 Vector 来实现，所有的方法都是线程安全的。入栈和出栈操作的时间复杂度为O(1)，查找元素的时间复杂度为O(n)。