Java栈数据结构的实现方式

栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法:

ava工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类:

  1. pop() 出栈操作,弹出栈顶元素。
  2. push(E e) 入栈操作
  3. peek() 查看栈顶元素
  4. isEmpty() 栈是否为空

枚举(Enumeration)

另外,实现一个栈,还应该考虑到几个问题:

位集合(BitSet)

  1. 栈的初始大小以及栈满以后如何新增栈空间
  2. 对栈进行更新时需要进行同步

向量(Vector)

简单示例,使用数组实现栈,代码如下:

栈(Stack)

public class Stack<E> {  

    // Java 不支持泛型数组,如需使用,请使用Java提供的容器  
    private Object[] stack;  

    // 栈的默认初始大小  
    private static final int INIT_SIZE = 2;  

    // 栈顶索引  
    private int index;  

    public Stack() {  
        stack = new Object[INIT_SIZE];  
        index = -1;  
    }  

    /**  
     * 构造方法  
     *   
     * @param initSize  
     *            栈的初始大小  
     */ 
    public Stack(int initSize) {  
        if (initSize < 0) {  
            throw new IllegalArgumentException();  
        }  
        stack = new Object[initSize];  
        index = -1;  
    }  

    /**  
     * 出栈操作  
     *   
     * @return 栈顶对象  
     */ 
    public synchronized E pop() {  
        if (!isEmpty()) {  
            E temp = peek();  
            stack[index--] = null;  
            return temp;  
        }  
        return null;  
    }  

    /**  
     * 入栈操作  
     *   
     * @param obj  
     *            等待入栈的对象  
     */ 
    public synchronized void push(E obj) {  
        if (isFull()) {  
            Object[] temp = stack;  
            // 如果栈满,则创建空间为当前栈空间两倍的栈  
            stack = new Object[2 * stack.length];  
            System.arraycopy(temp, 0, stack, 0, temp.length);  
        }  
        stack[++index] = obj;  
    }  

    /**  
     * 查看栈顶对象  
     *   
     * @return 栈顶对象  
     */ 
    public E peek() {  
        if (!isEmpty()) {  
            return (E) stack[index];  
        }  
        return null;  
    }  

    /**  
     * 查看栈是否为空  
     *   
     * @return 如果栈为空返回true,否则返回false  
     */ 
    public boolean isEmpty() {  
        return index == -1;  
    }  

    /**  
     * 查看栈是否满  
     *   
     * @return 如果栈满返回true,否则返回false  
     */ 
    public boolean isFull() {  
        return index >= stack.length - 1;  
    }  
}

字典(Dictionary)

最后说明,Java中实现了栈(java.util.Stack)的数据结构,它是通过继承Vector类实现的,一般情况下我们直接拿来用就行了。

哈希表(Hashtable)

属性(Properties)

以上这些类是传统遗留的,在Java2中引入了一种新的框架-集合框架(Collection),我们后面再讨论。

枚举(Enumeration)

枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很广。
枚举(The Enumeration)接口定义了一种从数据结构中取回连续元素的方式。

例如,枚举定义了一个叫nextElement
的方法,该方法用来得到一个包含多元素的数据结构的下一个元素。

关于枚举接口的更多信息,请参见枚举(Enumeration)。

位集合(BitSet)

位集合类实现了一组可以单独设置和清除的位或标志。

该类在处理一组布尔值的时候非常有用,你只需要给每个值赋值一”位”,然后对位进行适当的设置或清除,就可以对布尔值进行操作了。

关于该类的更多信息,请参见位集合(BitSet)。

向量(Vector)

向量(Vector)类和传统数组非常相似,但是Vector的大小能根据需要动态的变化。

澳门新葡亰网站注册,和数组一样,Vector对象的元素也能通过索引访问。

使用Vector类最主要的好处就是在创建对象的时候不必给对象指定大小,它的大小会根据需要动态的变化。