疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

栈在Java类库中的实现


 

 
栈是一种后进先出的数据结构。在它之上,主要有三种操作:
 
(1)判断栈是否为空——empty();
 
(2)在栈顶添加一个元素——push(E);
 
(3)删除并返回栈顶元素——pop()。
 
在Java类库中,Stack类实现了栈,它继承自Vector类:
 
 
public class Stack<E> extends Vector<E>
于是,Stack用数组保存元素:
 
protected Object[] elementData;
用一个整数记录栈中元素的个数:
 
protected int elementCount;
接下来看看栈的三种操作在Stack中是如何实现的。
1.
empty()方法实现如下:
 
 
    public boolean empty() {
        return size() == 0;
    }
 
size()方法是在Vector中定义的方法,具体定义如下:
 
 public synchronized int size() {
        return elementCount;
    }
 
它返回栈中元素的个数,也就是说,如果栈中元素个数为0,栈就为空。
2.push(E element)方法实现如下:
 
 
    public E push(E item) {
        addElement(item);
 
        return item;
    }
 
它调用addElement(E)方法实现向栈中添加元素,addElement(E)方法实现如下:
 
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
 
只需要关注方法的最后一行:
 
elementData[elementCount++] = obj;
 
它将元素添加到之前数组中已有元素的后面并把元素个数加1,这正是栈的push操作需要的。
 
3.pop()方法实现如下:
 
    public synchronized E pop() {
        E       obj;
        int     len = size();
 
        obj = peek();
        removeElementAt(len - 1);
 
        return obj;
    }
 
前面已经知道size()返回栈中元素的个数,于是len等于elementCount;peek()是Stack中的另一个方法,用于返回栈顶元素;removeElementAt(int)是Vector中定义的方法,删除指定位置元素。
peek()实现如下:
 
 
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
 
peek()方法又调用Vector中定义的方法elementAt(int)返回栈顶元素,elementAt(int)的实现如下:
 
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
 
        return elementData(index);
    }
 
elementAt(int)方法又调用elementData(int)方法,elementData(int)方法实现如下:
 
    E elementData(int index) {
        return (E) elementData[index];
    }
 
原来,peek()方法实际上就是通过elementData[len-1]返回栈顶元素的。
接下来看removeElementAt(int)方法:
 
 
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 */
    }
 
pop()中传给removeElementAt(int)的参数是len-1, 也就是elementCount-1,也就是说,removeElementAt(int)中的j=0,于是removeElementAt(int)方法直接执行到:
 
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
这两行通过先把栈中元素数量减1,然后把之前的栈顶元素设置为null使之被垃圾收集器回收达到删除栈顶元素的目的。