热门资源

使用数组实现栈

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

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

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

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

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

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章