你的位置:首页 > Java教程

[Java教程]Java数据结构漫谈


Stack(栈)是一种比较典型的数据结构,其元素满足后进先出(LIFO)的特点。

Java中Stack的实现继承自Vector,所以其天然的具有了一些Vector的特点,所以栈也是线程安全的。

class Stack<E> extends Vector<E> {

事实上,除了继承自Vector的那些方法之外,Stack只提供了5个方法:

  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;  }  public synchronized int search(Object o) {    int i = lastIndexOf(o);    if (i >= 0) {      return size() - i;    }    return -1;  }

push函数是用来向Stack的顶部压入一个元素,影响其性能的是 addElement的性能:

  public synchronized void addElement(E obj) {    modCount++;    ensureCapacityHelper(elementCount + 1);    elementData[elementCount++] = obj;  }

可以看出,其方法是在Vector的最后加入一个元素,其时间复杂度是o(1)。

peek函数是从查看栈顶元素,但是不删除。其性能主要是由Vector的elementAt函数决定的:

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

由于Vector的底层是数组实现的,通过下标可以直接进行定位,所以peek的时间复杂度也是o(1)。

pop函数是移除并获取到栈顶元素,在源码中可以看到,这里调用peek获取了栈顶元素,使用removeElementAt来删除栈顶元素,这个函数也正是决定pop性能的关键:

  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 */  }

咋一看来,这里删除一个元素之后,都会对数组中的元素进行复制调整,时间复杂度是o(n),但是考虑到传进来的index值的特殊性:

index = elementCount -1;

这样的话if(j>0)的条件永远都不会成立,因为j永远都是0,中间复制调整元素的操作就避免了,仅仅是在最后把Vector最后的值赋值为null,时间复杂度是o(1)。

search是查找一个元素在Stack中的index,这里起作用的是Vector的lastIndexOf函数,代码如下:

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

可以看出,查找的过程是从后向前,挨个比较,其时间复杂度必然是o(n)。

 

Stack是Vector的子类,所以Vector的函数这里也适用,这里不再赘述,在Vector相关的介绍文章中会有。

Stack是线程安全的,所以其性能必然受到影响,如果需要使用一个非线程安全的Stack,可以直接使用LinkedList,LinkedList本身提供的方法就包含了Stack的操作。