栈的java实现

昨天心血来潮用java实现了一下栈（Stack），在这分享一下。

栈的概念

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈（push），它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈(pop)，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 
它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。如图所示 

实现过程

实现起来比较简单，就是利用一个数组作为容器，同时定义一个指向“栈顶”即数组插入字符的最后一个索引指针即可。当push的时候，指针加1；pop的时候，指针减1。 
需要注意的是不要溢出。直接上代码了！

代码

public class Stack{
    private final int count;
    private String[] stackStr;
    private int ptr = -1;
    public Stack(){
        ptr = -1;
        this.count = 100;
        stackStr = new String[this.count];
    }
    public Stack(int count){
        this.count = count;
        ptr = -1;
        stackStr = new String[this.count];
    }
    public void push(String s) throws ArrayIndexOutOfBoundsException{
        if (ptr < count - 1){
            stackStr[++ptr] = s;
        }
        else 
            System.out.print(s + " 压栈溢出! \n"); 
    }
    public String pop(){
        String s = stackStr[ptr];
        ptr--;
        return s;
    }
    public Boolean isEmpty(){
        if (ptr == -1)
            return true;
        else 
            return false;
    }
    public String toString(){
        String s = "";
        for(int i = 0; i <= ptr; i++){
            s = s + stackStr[i] + " ";
        }
        return s;
    }
}

做一下测试：

public static void main(String[] args){
        Stack stk = new Stack(2);
        stk.push("a");
        stk.push("b");
        stk.push("c");
        print(stk.toString());
        print("\n");
        stk.pop();
        print(stk.toString());
    }
    static void print(String s){
        System.out.print(s);
    }

结果如下： 

OK！这里做了压栈和出栈，可以看到当溢出的时候不会报错。

栈的作用

栈的用处有很多。栈可以用来在函数调用的时候存储断点，做递归时要用到栈，等等。最近学习的下推自动机使用栈作为存储完成其算法。