Java實現棧（鏈表和線性表兩種方法實現）

• 2020 年 5 月 9 日
• 筆記
• 數據結構和演算法

一、棧的介紹

任何數據結構都是一種規則

棧就是在最基礎的結構——線性結構和鏈式結構上面定義規則形成的

如果對基本數據結構（線性表和鏈表）有疑問的同學可以看我之前的部落格：//www.cnblogs.com/yxm2020/p/12762888.html

規則如下：

限制鏈表或者線性表元素的插入和取出，只能在同一端進行操作，運行插入的一段稱為棧頂（top),另一端為固定的一端，成為棧底。

圖解：（入棧和出棧）

特點：

先入後出FILO(First in last out),最先放入棧的數據，只能最後才能出來，和隊列完全相反

棧的應用場景：

保存運行過程中程式中的程式碼或者值，比如：

• 子程式的調用
• 處理遞歸的調用
• 表達式的轉換（中綴轉後綴）
• 二叉樹的遍歷
• 圖形的深度優先遍歷

二、程式碼的實現思路

1、思路

1. 確定一個結構存儲數據，線性表或者鏈表
2. 既然只能在棧頂操作，那麼定義一棧頂標誌（top)
3. 最基本的兩個方法，入棧和出棧
4. 入棧後，在棧頂加入一個元素，top上移一個單元
5. 出棧後，在棧頂刪除一個元素，top下移一個單元

2、Java實現

1. 用Java數組模擬棧
2. java鏈表實現棧

三、Java數組模擬棧

public class ArrayStack<T> {
    //棧頂標誌
    private int top;
    //java數組
    private T[] stack;
    //最大長度
    private int maxsize;
    public ArrayStack(int maxsize,Class<T> type){
        this.maxsize = maxsize;
        this.top = -1;
        stack = (T[]) Array.newInstance(type,maxsize);
    }
    //長度
    public int size(){
        return top+1;
    }
    //棧滿
    public boolean isFull(){
        return top == maxsize-1;
    }
    //棧空
    public boolean isEnpty(){
        return top == -1;
    }
    //入棧
    public void push(T t){
        if(isFull()){
            throw new RuntimeException("棧滿");
        }
        top++;
        stack[top] = t;
    }
    //出棧
    public T pop(){
        if(isEnpty()){
            throw new RuntimeException("棧空");
        }
        T value = stack[top];
        top--;
        return value;
    }
    //遍歷
    public void show(){
        if(isEnpty()){
            System.out.println("棧空");
        }
        int temp = top;
        while (temp != -1){
            System.out.println(stack[temp]);
            temp--;
        }
    }
}

四、Java鏈表實現棧

public class LinkedStack<T> {
    //定義一個棧頂標誌，帶了個
    private Node top;
    private class Node{
        private Node next;
        private T t;
        public Node(T t){
            this.t = t;
        }
    }
    //創建
    public LinkedStack(){
        top = new Node(null);
    }
    //棧空
    public boolean isEnpty(){
        if(top.next == null){
            return true;
        }
        return false;
    }
    //入棧
    public void push(T t){
        Node newNode = new Node(t);
        //從棧頂入
        newNode.next = top.next;
        top.next = newNode;
    }
    //出棧
    public T pop(){
        if(isEnpty()){
            System.out.println("棧空");
            return null;
        }
        T value = top.next.t;
        top.next = top.next.next;
        return value;
    }
    //show
    public void show(){
        Node temp = top;
        if(temp.next == null){
            System.out.println("棧空");
        }
        while (temp.next!=null){
            temp = temp.next;
            System.out.println(temp.t);
        }
    }
}