棧只允許訪問一個數(shù)據(jù)項(xiàng)：即最后插入的數(shù)據(jù)項(xiàng)饿自。移除這個數(shù)據(jù)項(xiàng)后才能訪問倒數(shù)第二個插入的數(shù)據(jù)項(xiàng)汰翠，依次類推。所以棧是一個先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)

棧的代碼實(shí)現(xiàn)：

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

出錯處理

有不同的方法來處理?xiàng)５腻e誤昭雌。當(dāng)向已經(jīng)滿了的棧用再添加一個數(shù)據(jù)項(xiàng)复唤，或要從空棧中彈出一個數(shù)據(jù)項(xiàng)時會發(fā)生錯誤，可以把處理這些錯誤的工作推給類用戶烛卧，用戶在插入數(shù)據(jù)項(xiàng)前要確定棧不滿：

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

棧實(shí)例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唱星，使程序易讀而且不容易出錯

棧的效率

數(shù)據(jù)項(xiàng)入棧和出棧的時間復(fù)雜度都為常數(shù)O(1)雳旅，這也就是說，棧操作所耗時間不依賴與棧中數(shù)據(jù)項(xiàng)的個數(shù)间聊，因此操作時間很短，棧不需要比較和移動操作抵拘。