源码阅读之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)。

Published on Oct 18, 2018 in categories 数据结构

上一篇源码阅读之LinkedList实现细节
下一篇源码分析OKHttp的执行过程