Java数据结构之栈

栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据项，依次类推。所以栈是一个先进后出的数据结构

栈的代码实现：

public class stack {
    private long[] stackArray;
    private int maxSize;
    private int top;

    public stack(int s){
        maxSize=s;
        stackArray=new long[maxSize];
        top=-1;

    }
    //入栈
    public void push(long value){
        stackArray[++top]=value;
    }
    //出栈
    public long pop(){
        return stackArray[top--];
    }
    //查看栈顶元素
    public long peek(){
        return stackArray[top];
    }
    public boolean isEmpty(){
        return (top==-1);
    }
    public boolean isFull(){
        return (top==maxSize-1);
    }

    public static void main(String[] args) {
        stack s=new stack(10);
        s.push(22);
        s.push(1);
        s.push(88);
        s.push(66);

        while (!s.isEmpty()){
            long val=s.pop();
            System.out.println(val);
        }
    }
}

出错处理

有不同的方法来处理栈的错误。当向已经满了的栈用再添加一个数据项，或要从空栈中弹出一个数据项时会发生错误，可以把处理这些错误的工作推给类用户，用户在插入数据项前要确定栈不满：

if(!stack.isFull()){
    insert(item);
}

栈实例1：单词逆序

上面提供了long的栈，读者可以自行改造成char类型的栈

class Reverser{
    private String input;
    private String output;

    public Reverser(String in){
        input=in;
    }

    public String doRev(){
        int stackSize=input.length();
        stack s=new stack(stackSize);

        for(int j=0;j<input.length();j++){
            char ch=input.charAt(j);
            s.push(ch);
        }
        output=" ";
        while(!s.isEmpty()){
            char ch=s.pop();
            output=output+ch;
        }
        return output;
    }

    public static void main(String[] args) throws IOException {
        String input,output;

        while(true){
            System.out.println("请输入字符串");
            System.out.flush();
            input=getString();
            if(input.equals("")){
                break;
            }
            Reverser reverser=new Reverser(input);
            output= reverser.doRev();
            System.out.println(output);
        }
    }

    public static String getString() throws IOException {
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        String s=br.readLine();
        return s;
    }
}

栈是一个概念上的辅助工具，栈通过提供限定性访问方法push和pop，使程序易读而且不容易出错

栈的效率

数据项入栈和出栈的时间复杂度都为常数O(1)，这也就是说，栈操作所耗时间不依赖与栈中数据项的个数，因此操作时间很短，栈不需要比较和移动操作。