Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「棧(Stack)」

作者：Java精髓 2021-03-12 09:13:47

開發(fā) 后端算法

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

[[387145]]

基本介紹

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

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

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

棧的應(yīng)用場(chǎng)景

1.子程序的調(diào)用:在調(diào)往子程序前,會(huì)先將下個(gè)指令的地址存到棧中,直到子程序執(zhí)行完后再將地址取出,以回到原來的程序.

2.處理遞歸調(diào)用:和子程序的調(diào)用類似,只是除了儲(chǔ)存下一個(gè)指令的地址外,也將參數(shù)\區(qū)域變量等數(shù)據(jù)存入堆棧中.

3.表達(dá)式轉(zhuǎn)換(中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式)與求值(實(shí)際解決).

4.二叉樹的遍歷.

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

棧結(jié)構(gòu)實(shí)現(xiàn)案例

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:添加數(shù)據(jù)到棧(入棧)"); 
            System.out.println("pop:從棧取出數(shù)據(jù)(出棧)"); 
            key = scanner.next(); 
            switch (key) { 
                case "show": 
                    stack.list(); 
                    break; 
                case "push": 
                    System.out.println("請(qǐng)輸入一個(gè)數(shù)"); 
                    int value = scanner.nextInt(); 
                    stack.push(value); 
                    break; 
                case "pop": 
                    try { 
                        int res = stack.pop(); 
                        System.out.println("出棧的數(shù)據(jù)%d\n" + res); 
                    } catch (Exception e) { 
                        System.out.println(e.getMessage()); 
                    } 
                    break; 
                case "exit": 
                    scanner.close(); 
                    loop = false; 
                    break; 
            } 
        } 
        System.out.println("程序退出"); 
    } 
} 
 
//定義一個(gè)類表示棧結(jié)構(gòu) 
class ArrayStack { 
    private int maxSize;//棧的大小 
    private int[] stack;//數(shù)組模擬棧,數(shù)據(jù)就放入該數(shù)組 
    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("?？?沒有數(shù)據(jù)~~"); 
            return; 
        } 
        for (int i = top; i >= 0; i--) { 
            System.out.printf("stack[%d]=%d\n", i, stack[i]); 
        } 
    } 
 
}

使用棧完成表達(dá)式的計(jì)算(中綴表達(dá)式)

準(zhǔn)備兩個(gè)棧,數(shù)字棧和符號(hào)棧.

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

2.如果發(fā)現(xiàn)是一個(gè)數(shù)字就直接入數(shù)字棧.

3.如果是一個(gè)符號(hào),分情況考慮如果當(dāng)前符號(hào)棧為空,就直接入站.如果符號(hào)棧有操作符,就進(jìn)行比較.

如果當(dāng)前操作符的優(yōu)先級(jí)小于或者等于棧中的操作符,就需要從數(shù)棧中pop兩個(gè)數(shù),再?gòu)姆?hào)棧中pop出一個(gè)字符,進(jìn)行運(yùn)算,將得到結(jié)果入數(shù)棧,然后當(dāng)前操作符入符號(hào)棧.
如果當(dāng)前的操作符的優(yōu)先級(jí)大于棧中的操作符,就直接入棧.

4.當(dāng)表達(dá)式掃描完畢,就順序地從數(shù)棧和符號(hào)棧中pop出相應(yīng)的數(shù)和符號(hào),并運(yùn)行.

5.最后在數(shù)字棧只有一個(gè)數(shù)字,就是表達(dá)式的結(jié)果.

package com.structures.stack; 
 
public class Calculator { 
    public static void main(String[] args) { 
        //表達(dá)式 
        String expression = "700+2*6-2"; 
        //數(shù)棧 
        ArrayStack2 numStack = new ArrayStack2(10); 
        //符號(hào)棧 
        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 = "";//用于拼接多位數(shù) 
        while (true) { 
            ch = expression.substring(index, index + 1).charAt(0); 
            //如果是運(yùn)算符 
            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); 
                        //把運(yùn)算的結(jié)果入數(shù)棧,當(dāng)前符號(hào)入符號(hào)棧 
                        numStack.push(res); 
                        operStack.push(ch); 
                    } else { 
                        operStack.push(ch); 
                    } 
                } 
            } else { 
                //當(dāng)處理多位數(shù)時(shí),不能立即入棧. 
                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("表達(dá)式%s=%d\n", expression, numStack.pop()); 
 
    } 
} 
 
class ArrayStack2 { 
    private int maxSize;//棧的大小 
    private int[] stack;//數(shù)組模擬棧,數(shù)據(jù)就放入該數(shù)組 
    private int top = -1;//top表示棧頂,初始化-1 
 
    public ArrayStack2(int maxSize) { 
        this.maxSize = maxSize; 
        stack = new int[this.maxSize]; 
    } 
 
    //返回當(dāng)前棧頂?shù)闹?不是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("?？?quot;); 
        } 
        int value = stack[top]; 
        top--; 
        return value; 
    } 
 
    //顯示棧的情況[遍歷棧] 
    public void list() { 
        if (isEmpty()) { 
            System.out.println("?？?沒有數(shù)據(jù)~~"); 
            return; 
        } 
        for (int i = top; i >= 0; i--) { 
            System.out.printf("stack[%d]=%d\n", i, stack[i]); 
        } 
    } 
 
    //返回運(yùn)算符的優(yōu)先級(jí),數(shù)字越大則優(yōu)先級(jí)越高. 
    //假定目前操作符只有 +  - * / 
    public int priority(int oper) { 
        if (oper == '*' || oper == '/') { 
            return 1; 
        } else if (oper == '+' || oper == '-') { 
            return 0; 
        } else { 
            return -1; 
        } 
    } 
 
    //判斷是不是一個(gè)運(yùn)算符 
    public boolean isOper(char val) { 
        return val == '+' || val == '-' || val == '*' || val == '/'; 
    } 
 
    //計(jì)算方法 
    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; 
    } 
}