java stack的详细实现分析

简介

    我们最常用的数据结构之一大概就是stack了。在实际的程序执行，方法调用的过程中都离不开stack。那么，在一个成熟的类库里面，它的实现是怎么样的呢？也许平时我们实践的时候也会尝试着去写一个stack的实现玩玩。这里，我们就仔细的分析一下jdk里的详细实现。

Stack

    如果我们去查jdk的文档，我们会发现stack是在java.util这个包里。它对应的一个大致的类关系图如下：

    通过继承Vector类，Stack类可以很容易的实现他本身的功能。因为大部分的功能在Vector里面已经提供支持了。

Stack里面主要实现的有一下几个方法：

方法名	返回类型	说明
empty	boolean	判断stack是否为空。
peek	E	返回栈顶端的元素。
pop	E	弹出栈顶的元素
push	E	将元素压入栈
search	int	返回最靠近顶端的目标元素到顶端的距离。

    因为前面我们已经提到过，通过继承Vector，很大一部分功能的实现就由Vector涵盖了。Vector的详细实现我们会在后面分析。它实现了很多的辅助方法，给Stack的实现带来很大的便利。现在，我们按照自己的思路来分析每个方法的具体步骤，再和具体实现代码对比。

empty

    从我们的思路来说，如果要判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。或者说我们有一个指向栈顶的变量，如果它开始的时候是设置为空的，我们可以认为栈为空。这部分的实现代码也很简单：

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

 如果更进一步分析的话，是因为Vector已经实现了size()方法。在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0，则表示容器空。这部分在Vector里面的实现如下：

public synchronized int size() {
    return elementCount;
}

 

peek

    peek是指的返回栈顶端的元素，我们对栈本身不做任何的改动。如果栈里有元素的话，我们就返回最顶端的那个。而该元素的索引为栈的长度。如果栈为空的话，则要抛出异常：

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

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

 这个elementAt方法也是Vector里面的一个实现。在Vector里面，实际上是用一个elementData的Object数组来存储元素的。所以要找到顶端的元素无非就是访问栈最上面的那个索引。它的详细实现如下：

public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

pop

    pop方法就是将栈顶的元素弹出来，如果栈里有元素，就取最顶端的那个，否则就要抛出异常：

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

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

    return obj;
}

    在这里，判断是否可以取栈顶元素在peek方法里实现了，也将如果栈为空则抛异常的部分包含在peek方法里面。这里有必要注意的一个细节就是，在通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。我们平时可能不太会留意到这一点。为什么要移除呢？我们反正有一个elementCount来记录栈的长度，不管它不是也可以吗？

    实际上，这么做在程序运行的时候会有一个潜在的内存泄露的问题。因为在java里面，如果我们普通定义的类型属于强引用类型。比如这里vector就底层用的Object[]这个数组强类型来保存数据。强类型在jvm中做gc的时候，只要程序中有引用到它，它是不会被回收的。这就意味着在这里，只要我们一直在用着stack，那么stack里面所有关联的元素就都别想释放了。这样运行时间一长就会导致内存泄露的问题。那么，为了解决这个问题，这里就是用的removeElementAt()方法。

 

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; /* to let gc do its work */
}

     这个方法实现的思路也比较简单。就是用待删除元素的后面元素依次覆盖前面一个元素。这样，就相当于将数组的实际元素长度给缩短了。因为这里这个移除元素的方法是定义在vector中间，它所面对的是一个更加普遍的情况，我们移除的元素不一定就是数组尾部的，所以才需要从后面依次覆盖。如果只是单纯对于一个栈的实现来说，我们完全可以直接将要删除的元素置为null就可以了。

push

    push的操作也比较直观。我们只要将要入栈的元素放到数组的末尾，再将数组长度加1就可以了。

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

    return item;
}

    这里，addElement方法将后面的细节都封装了起来。如果我们更加深入的去考虑这个问题的话，我们会发现几个需要考虑的点。1. 首先，数组不会是无穷大的 ，所以不可能无限制的让你添加元素下去。当我们数组长度到达一个最大值的时候，我们不能再添加了，就需要抛出异常来。2. 如果当前的数组已经满了，实际上需要扩展数组的长度。常见的手法就是新建一个当前数组长度两倍的数组，再将当前数组的元素给拷贝过去。前面讨论的这两点，都让vector把这份心给操了。我们就本着八卦到底的精神看看它到底是怎么干的吧：

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

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

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

     看到这部分代码的时候，我不由得暗暗叹了口气。真的是拔了萝卜带出泥。本来想看看stack的细节实现，结果这些细节把vector都深深的出卖了。在vector中间有几个计数的变量，elementCount表示里面元素的个数，elementData是保存元素的数组。所以一般情况下数组不一定是满的，会存在着elementCount <= elementData.length这样的情况。这也就是为什么ensureCapacityHelper方法里要判断一下当新增加一个元素导致元素的数量超过数组长度了，我们要做一番调整。这个大的调整就在grow方法里展现了。

    grow方法和我们所描述的方法有点不一样。他不一样的一点在于我们可以用一个capacityIncrement来指示调整数组长度的时候到底增加多少。默认的情况下相当于数组长度翻倍，如果设置了这个变量就增加这个变量指定的这么多。

search

    search这部分就相当于找到一个最靠近栈顶端的匹配元素，然后返回这个元素到栈顶的距离。

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

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

    对应在vector里面的实现也相对容易理解：

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]))
                return i;
    }
    return -1;
}

    这个lastIndexOf的实现无非是从数组的末端往前遍历，如果找到这个对象就返回。如果到头了，还找不到对象呢？...不好意思，谁让你找不到对象的？活该你光棍，那就返回个-1吧。

Vector

    在前面对stack的讨论和分析中，我们几乎也把vector这部分主要的功能以及实现给涵盖了。vector和相关类以及接口的关系类图如下： 

    因为Java没有内置对List类型的支持，所以Vector内部的实现是采用一个object的array。其定义如下：

protected Object[] elementData;

    这里从某种角度来说可以说是java里对泛型支持的不足，因为内部保存数据的是Object[]，在存取数据的时候如果不注意的话会出现存取数据类型不一致的错误。所以在以下的某些个方法里需要加上@SuppressWarnings("unchecked")的声明。

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    我们前面讨论的那些数组的增长，删除元素，查找元素以及修改等功能就占据了vector的大部分。如果有兴趣看vector的源代码的话，会发现里面主要就是这些功能的实现再加上一个迭代器功能。总共的代码不是很多，1200多行，这里就不再赘述了。 

    可以说，vector它本身就是一个可以动态增长的数组。和我们常用的ArrayList很像。和ArrayList的不同在于它对元素的访问都用synchronized修饰，也就是说它是线程安全的。在多线程的环境下，我们可以使用它。

总结

    看前面这些代码，不但理顺了栈和vector的具体实现，还可以从中发现一些其他的东西。比如说，栈最大的长度取决于vector里面数组能有多长。这里vector里面最大能取到Integer.MAX_VALUE。 以前写c程序的代码时经常感叹，要是有那种可以自动增长的数组类型就好了。当然，c99后面确实提供了这个福利。在java里面，比较典型这一部分就由vector提供了。你看，他可以自动按照需要增长，本身是线程安全的，顺便帮你把清除元素时的内存泄露问题都考虑到了。简直是自动、安全、健康又环保啊：）

参考资料：

http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html