12.java鏈表棧和數組棧

棧是一個先入后出的有序列表，棧是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表，一端為變化的一端，稱為棧頂，另一端是固定的，稱為棧底。先入的元素在棧底，最后放入的元素在棧頂，刪除時后放入的元素先刪除，最先放入的元素最后刪除。

老師在這里講解的只有用數組模擬棧，書寫類ArrayStack，其中定義一個int類型的變量top來記錄棧頂索引，一個數組來記錄數據，一個int類型的變量maxSize來記錄棧的最大尺寸即可容納的數據個數。

代碼如下：

class ArrayStack{
    public int top=-1;
    public int[] stack;
    public int maxSize;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack=new int[maxSize];
    }
    public boolean isFull(){
        if(top==maxSize-1) return true;
        return false;
    }
    public boolean isEmpty(){
        if(top==-1) return true;
        return false;
    }
    public void push(int value){
        if(isFull()){
            System.out.println("棧滿，無法加入");
            return;
        }
        top++;//先加棧頂再賦值
        stack[top]=value;
    }
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("棧空，沒有數據");
        }
        int value=stack[top];
        top--;
        return value;
    }
    public void list(){
        if(isEmpty()){
            System.out.println("棧空，沒有數據");
        }
        for(int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d",i,stack[i]);
        }
    }
}

老師留了課后作業，讓我們用鏈表代替數組來書寫棧，在很多次的修改和斟酌以后，我的最后設想如下：首先鏈表的節點中有三個變量，代表編號的no變量，代表具體數據的data變量和一個ArrayStack變量next來指向下一個節點。不再額外定義鏈表類來管理節點，直接定義鏈表棧類來管理節點，其中有兩個變量，代表最大可容納數據的maxSize，和一個頭節點代表鏈表。在原先變量top的改變上我最開始想另外定義一個節點為top來指向棧頂。但在試驗后發現并沒有這種必要，因為此處我使用的是頭插法，所以棧頂永遠都是head.next，不需另外定義。另外，在判斷棧空和棧滿時我發現十分麻煩，所以廢物利用了一下head節點中的data變量，將其含義變為目前鏈表長度，這樣在判斷時只需要判斷head.data是否為0或者maxSize即可。

java鏈表棧的類定義如下：

class linkstack{
    public int maxSize;

    public linkstack(int maxSize) {
        this.maxSize = maxSize;
    }

    public stackNodee head=new stackNodee(0,0);
    public boolean isFull(){
        if(head.data==maxSize){
            return true;
        }
        return false;
    }
    public boolean isempty(){
        if(head.data==0){
            return true;
        }
        return false;
    }
    public void push(int value){
        if(isFull()){
            System.out.println("棧已滿，無法加入");
            return;
        }
        int n=head.data+1;
        stackNodee temp=new stackNodee(n,value);
        if(isempty()){
            head.next=temp;
            head.data++;
            return;
        }
        temp.next=head.next;
        head.next=temp;
        head.data++;
    }
    public int pop(){
        int value;
        if(isempty()){
            throw new RuntimeException("棧空，沒有數據");
        }else {
            value=head.next.data;
            head.next=head.next.next;
            head.data--;
        }
        return value;
    }
    public void list(){
        if(isempty()){
            System.out.println("鏈表為空");
            return;
        }
        stackNodee temp=head.next;
        for (int i=1;i<=head.data;i++){
            System.out.printf("stack[%d]=%d\n",i,temp.data);
            temp=temp.next;
        }
    }

}
class stackNodee{
    public int no;
    public int data;
    public stackNodee next;

    public stackNodee(int no, int data) {
        this.no = no;
        this.data = data;
    }
}

這次的實驗讓我靈活運用了鏈表和棧，對此兩種數據結構都有了更進一步的理解。在書寫代碼的過程中，我個人認為數組的方式還是要比鏈表的方式簡單很多，有序數組自帶記錄了索引和數據，以及可定義數組長度，我認為還是比鏈表方便很多。

posted @ 2022-03-25 19:29 水煮小白菜閱讀(51) 評論(0) 收藏舉報

刷新頁面返回頂部

codesslave

12.java鏈表棧和數組棧

公告