[[387145]]

 基本介紹

1. 棧是一個先入后出(FILO First In Last Out)的有序列表

2.棧是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表.允許插入和刪除的一端,為變化的一端,稱為棧頂(Top),另一端為固定的一端,稱為棧底(Bottom).

3.根據棧的定義可知,最先放入棧中元素在棧底,最后放入的元素在棧頂,而刪除元素剛好相反,最后放入的元素最先刪除,最先放入的元素最后刪除.

棧的應用場景

1.子程序的調用:在調往子程序前,會先將下個指令的地址存到棧中,直到子程序執行完后再將地址取出,以回到原來的程序.

2.處理遞歸調用:和子程序的調用類似,只是除了儲存下一個指令的地址外,也將參數\區域變量等數據存入堆棧中.

3.表達式轉換(中綴表達式轉后綴表達式)與求值(實際解決).

4.二叉樹的遍歷.

5.圖形的深度優先(depth-first)搜索算法.

棧結構實現案例

package com.structures.stack; 
 
import java.util.Scanner; 
 
public class ArrayStackDemo { 
    public static void main(String[] args) { 
        ArrayStack stack = new ArrayStack(4); 
        String key = ""; 
        boolean loop = true; 
        Scanner scanner = new Scanner(System.in); 
        while (loop) { 
            System.out.println("show:顯示棧"); 
            System.out.println("exit:退出程序"); 
            System.out.println("push:添加數據到棧(入棧)"); 
            System.out.println("pop:從棧取出數據(出棧)"); 
            key = scanner.next(); 
            switch (key) { 
                case "show": 
                    stack.list(); 
                    break; 
                case "push": 
                    System.out.println("請輸入一個數"); 
                    int value = scanner.nextInt(); 
                    stack.push(value); 
                    break; 
                case "pop": 
                    try { 
                        int res = stack.pop(); 
                        System.out.println("出棧的數據%d\n" + res); 
                    } catch (Exception e) { 
                        System.out.println(e.getMessage()); 
                    } 
                    break; 
                case "exit": 
                    scanner.close(); 
                    loop = false; 
                    break; 
            } 
        } 
        System.out.println("程序退出"); 
    } 
} 
 
//定義一個類表示棧結構 
class ArrayStack { 
    private int maxSize;//棧的大小 
    private int[] stack;//數組模擬棧,數據就放入該數組 
    private int top = -1;//top表示棧頂,初始化-1 
 
    public ArrayStack(int maxSize) { 
        this.maxSize = maxSize; 
        stack = new int[this.maxSize]; 
    } 
 
    //判斷是否棧滿 
    public boolean isFull() { 
        return top == maxSize - 1; 
    } 
 
    //判斷是否棧空 
    public boolean isEmpty() { 
        return top == -1; 
    } 
 
    //入棧 
    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("棧空,沒有數據~~"); 
            return; 
        } 
        for (int i = top; i >= 0; i--) { 
            System.out.printf("stack[%d]=%d\n", i, stack[i]); 
        } 
    } 
 
} 

 使用棧完成表達式的計算(中綴表達式)

準備兩個棧,數字棧和符號棧.

1.通過一個index值(索引),來遍歷表達式.

2.如果發現是一個數字就直接入數字棧.

3.如果是一個符號,分情況考慮如果當前符號棧為空,就直接入站.如果符號棧有操作符,就進行比較.

• 如果當前操作符的優先級小于或者等于棧中的操作符,就需要從數棧中pop兩個數,再從符號棧中pop出一個字符,進行運算,將得到結果入數棧,然后當前操作符入符號棧.
• 如果當前的操作符的優先級大于棧中的操作符,就直接入棧.

4.當表達式掃描完畢,就順序地從數棧和符號棧中pop出相應的數和符號,并運行.

5.最后在數字棧只有一個數字,就是表達式的結果.

package com.structures.stack; 
 
public class Calculator { 
    public static void main(String[] args) { 
        //表達式 
        String expression = "700+2*6-2"; 
        //數棧 
        ArrayStack2 numStack = new ArrayStack2(10); 
        //符號棧 
        ArrayStack2 operStack = new ArrayStack2(10); 
        int index = 0;//用于掃描 
        int num1 = 0; 
        int num2 = 0; 
        int oper = 0; 
        int res = 0; 
        char ch = ' ';//將每次掃描得到的char保存到ch 
        String keepNum = "";//用于拼接多位數 
        while (true) { 
            ch = expression.substring(index, index + 1).charAt(0); 
            //如果是運算符 
            if (operStack.isOper(ch)) { 
                //如果為空 
                if (operStack.isEmpty()) { 
                    operStack.push(ch); 
                } else { 
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) { 
                        num1 = numStack.pop(); 
                        num2 = numStack.pop(); 
                        oper = operStack.pop(); 
                        res = numStack.cal(num1, num2, oper); 
                        //把運算的結果入數棧,當前符號入符號棧 
                        numStack.push(res); 
                        operStack.push(ch); 
                    } else { 
                        operStack.push(ch); 
                    } 
                } 
            } else { 
                //當處理多位數時,不能立即入棧. 
                keepNum += ch; 
                //如果ch是expression的最后一位 
                if (index == expression.length() - 1) { 
                    numStack.push(Integer.parseInt(keepNum)); 
                } else { 
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { 
                        numStack.push(Integer.parseInt(keepNum)); 
                        keepNum = ""; 
                    } 
                } 
            } 
            index++; 
            //掃遍到最后就退出 
            if (index >= expression.length()) { 
                break; 
            } 
        } 
        while (true) { 
            if (operStack.isEmpty()) { 
                break; 
            } 
            num1 = numStack.pop(); 
            num2 = numStack.pop(); 
            oper = operStack.pop(); 
            res = numStack.cal(num1, num2, oper); 
            numStack.push(res); 
        } 
        System.out.printf("表達式%s=%d\n", expression, numStack.pop()); 
 
    } 
} 
 
class ArrayStack2 { 
    private int maxSize;//棧的大小 
    private int[] stack;//數組模擬棧,數據就放入該數組 
    private int top = -1;//top表示棧頂,初始化-1 
 
    public ArrayStack2(int maxSize) { 
        this.maxSize = maxSize; 
        stack = new int[this.maxSize]; 
    } 
 
    //返回當前棧頂的值,不是pop 
    public int peek() { 
        return stack[top]; 
    } 
 
    //判斷是否棧滿 
    public boolean isFull() { 
        return top == maxSize - 1; 
    } 
 
    //判斷是否棧空 
    public boolean isEmpty() { 
        return top == -1; 
    } 
 
    //入棧 
    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("棧空,沒有數據~~"); 
            return; 
        } 
        for (int i = top; i >= 0; i--) { 
            System.out.printf("stack[%d]=%d\n", i, stack[i]); 
        } 
    } 
 
    //返回運算符的優先級,數字越大則優先級越高. 
    //假定目前操作符只有 +  - * / 
    public int priority(int oper) { 
        if (oper == '*' || oper == '/') { 
            return 1; 
        } else if (oper == '+' || oper == '-') { 
            return 0; 
        } else { 
            return -1; 
        } 
    } 
 
    //判斷是不是一個運算符 
    public boolean isOper(char val) { 
        return val == '+' || val == '-' || val == '*' || val == '/'; 
    } 
 
    //計算方法 
    public int cal(int num1, int num2, int oper) { 
        int res = 0; 
        switch (oper) { 
            case '+': 
                res = num1 + num2; 
                break; 
            case '-': 
                res = num2 - num1;//注意順序 
                break; 
            case '*': 
                res = num1 * num2; 
                break; 
            case '/': 
                res = num2 / num1;//注意順序 
                break; 
        } 
        return res; 
    } 
} 

 【編輯推薦】