數據結構學習筆記（三） 堆棧

堆棧：
    具有一定操作約束的線性表，只在一端（棧頂）做出棧和入棧（先進後出）

棧的順序存儲實現：

package stack;

public class StackArray {
    private static int[] a ;
    //這個是棧頂元素的下標，若為負數，則代表為空棧
    private static int top1 = -1;
    private static int top2 = 20;
//    top1--》                  《--top2
    public static void main(String[] args) {
        init();
        //將20這個元素放入1堆棧
        System.out.println("將10這個元素放入1堆棧:"+push(10,1));
        System.out.println("將20這個元素放入2堆棧:"+push(20,2));
        show();
        System.out.println("將10這個元素從1堆棧出棧:"+pop(1));
        System.out.println("將20這個元素從2堆棧出棧:"+pop(2));
        show();
        
    }
    /**
     * 初始化
     */
    public static void init(){
        a = new int[20];
    }
    
    /**
     * 入棧
     * @param tag :判斷是哪一個堆棧
     * @param item
     * @return
     */
    public static String push(int item,int tag){
        //判斷棧是否滿了 top1 top2是否緊挨著
        if(top2-top1 == 1){
            return "棧已經滿了";
        }else{
            if(tag == 1){
                a[++top1] = item;
                return "入棧成功";
            }else{
                a[--top2] = item ;
                return "入棧成功";
            }
        }
    }
    
    /**
     * 出棧
     * @return
     */
    public static String pop(int tag){
        if(tag == 1){
            if(top1 < 0){
                return "空棧";
            }else{
                top1--;
                return "出棧成功";
            }
        }else{
            if(top2 > a.length){
                return "空棧";
            }else{
                top2++;
                return "出棧成功";
            }
        }
    }
    public static void show(){
        System.out.print("1堆棧的元素：");
        for (int i = 0; i <= top1; i++) {
            System.out.print(a[i] +"  ");
        }
        System.out.println();
        System.out.print("2堆棧的元素：");
        for (int i = top2; i < a.length; i++) {
            System.out.print(a[i] +"  ");
        }
        System.out.println();
    }
}

棧的鏈式存儲解決(棧頂在鏈棧的棧頂)：

package stack;

public class StackChained {
    private static Node first;
    public static void main(String[] args) {
        init();
        System.out.println(push(10));
        System.out.println(push(20));
        show();
        System.out.println(pop());
        show();
    }
    /**
     * 初始化，讓first的next為空，代表沒有元素
     */
    public static void init(){
        first = new Node(0);
        first.next = null;
    }
    /**
     * 入棧
     */
    public static String push(int item){
        Node node = new Node(item);
        node.next = first.next;
        first.next = node;
        return "入棧成功";
    }
    
    /**
     * 出棧
     */
    public static String pop(){
        if(first.next == null){
            return "棧為空";
        }else{
            //出棧元素
            Node node = first.next;
            first.next = node.next;
            return "出棧成功,出棧元素為："+node.data;
        }
    }
    
    public static void show(){
        Node node = first;
        System.out.print("棧中的元素有：");
        while(node.next != null){
            System.out.print(node.next.data+"  ");
            node = node.next;
        }
        System.out.println();
    }
}
package stack;

public class Node {
    public int data ;
    public  Node next ;
    public Node(int data) {
        this.data = data;
    }
    
}

 表達式求值問題
    中綴表達式:運算符號位於兩個運算數之間。如：a+b*c-d/e
    尾碼表達式：運算符號位於兩個運算數之後。如：abc*+de/-
    
中綴表達式轉換為尾碼表達式：
    1）運算數：直接輸出。
    2）左括弧：直接進行壓棧。
    3）右括弧：將棧頂元素彈出並輸出，直到左括弧。
    4）運算符：
        若優先順序大於棧頂元素，則進行壓棧
        若優先順序小於棧頂元素，則將棧頂元素輸出，棧頂元素下移，在進行比較，若還是小於，
        則繼續輸出，直到大於棧頂元素的運算符，進行壓棧。
    5）若運算數處理完畢，則將棧中元素直接輸出。
    
尾碼表達式求職策略：
    從左往右掃描，逐個處理運算數和運算符號-->需要有種存儲方法，能順序存儲運算數，在需要時倒序輸出