如何使用Java編程內(nèi)功棧

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)如何使用Java編程內(nèi)功棧，文章內(nèi)容豐富且以專(zhuān)業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

 基本介紹

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

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

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

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

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

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

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

4.二叉樹(shù)的遍歷.

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è)類(lèi)表示棧結(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;     }      //判斷是否?？?nbsp;    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("?？?沒(méi)有數(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.通過(guò)一個(gè)index值(索引),來(lái)遍歷表達(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("?？?沒(méi)有數(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;     } }

上述就是小編為大家分享的如何使用Java編程內(nèi)功棧了，如果剛好有類(lèi)似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。