java模擬棧的操作
- 2020 年 4 月 5 日
- 筆記
棧是一種有序列表，可以使用數組的結構來儲存棧的數據內容
思路
1. 創建一個棧類StackArray
2. 定義一個top來模擬棧頂，初始化為-1
3. 入棧： 當有數據加入到棧的時候 top++ stack[top] = data
4. 出棧 int value = stack[top]; top--, return value
代碼實現
//定義一個類來表示棧 class ArrayStack{ private int maxSize; //棧的大小 private int[] stack; //數組模擬棧 數據放在數組中 private int top = -1; //top 表示棧頂 //構造器 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[maxSize]; } //棧滿 當棧頂和棧容量相等時 棧滿 public boolean isFull(){ return top == maxSize - 1; } //判斷棧空 public boolean isEmpty(){ return top == -1; } //入棧 push public void push(int value){ //先判斷棧是否滿 if(isFull()){ System.out.println("棧滿"); return; } top ++; stack[top] = value; } //出棧 pop 將棧頂的數據返回 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]=%dn", i,stack[i]); } } }
通過main方法調用自定義的棧類來模擬棧的操作
public class StackArrayDemo { public static void main(String[] args) { //測試ArrayStack //創建一個ArrayStack對象 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: 表示從棧取出數據"); System.out.println("請輸入你的選擇: "); 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 result = stack.pop(); System.out.printf("取出的數據為：%dn", result); }catch (Exception e){ System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出"); } }
根據上邊的內容 來模擬一下用棧實現的計算表達式的功能
思路
通過一個index（索引） 來遍歷我們的表達式
如果我們發現是一個數字 就直接入數棧
如果掃描到的是一個符號 就分如下情況
1.如果當前符號棧為空， 就直接入棧
2.如果符號棧有操作符 就進行比較 如果當前操作符的優先級 小於或等於棧中的操作符
就需要從數棧中pop出兩個數，再從符號棧中pop出一個符號，進行運算，將得到的結果入數棧
再把當前的符號入符號棧，
3.如果當前符號的優先級大於棧中的操作符，直接入棧
掃描完畢後 就順序地沖數棧和符號棧中pop出響應的數和符號 並運行
最後在數棧中只有一個數字就是表達式的結果
參考上邊的ArrayStack類 拓展一個ArrayStack2 類 並對功能進行增強
//定義一個類來表示棧 對ArrayStack進行擴展 class ArrayStack2{ private int maxSize; //棧的大小 private int[] stack; //數組模擬棧 數據放在數組中 private int top = -1; //top 表示棧頂 //構造器 public ArrayStack2(int maxSize) { this.maxSize = maxSize; stack = new int[maxSize]; } //棧滿 當棧頂和棧容量相等時 棧滿 public boolean isFull(){ return top == maxSize - 1; } //判斷棧空 public boolean isEmpty(){ return top == -1; } //入棧 push public void push(int value){ //先判斷棧是否滿 if(isFull()){ System.out.println("棧滿"); return; } top ++; stack[top] = value; } //出棧 pop 將棧頂的數據返回 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]=%dn", 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 oper, int num1, int num2){ int result = 0; // 用於存放計算的結果 switch (oper){ case '+': result = num1 + num2; break; case '-': result = num2 - num1; break; case '*': result = num2 * num1; break; case '/': result = num2 / num1; break; default: break; } return result; } //返回棧頂的值 不Pop public int peek(){ return stack[top]; } }
調用主方法 進行案例的具體實現
public class StackCalculate { public static void main(String[] args) { //完成表達式的運算 String expression = "500+7*2-8"; //創建兩個棧 一個數棧一個符號棧 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){ //依次得到expression的每一個字符 ch = expression.substring(index, index + 1).charAt(0); //判斷ch是什麼 然後做相應的處理 if (operStack.isOper(ch)){ //如果是運算符 //判斷當前的符號棧是否為空 if(!operStack.isEmpty()){ /* 處理,進行符號優先級比較如果當前操作符的優先級 小於或等於棧中的操作符 就需要從數棧中pop出兩個數，再從符號棧中pop出一個符號，進行運算，將得到的結果入數棧 再把當前的符號入符號棧， 如果當前符號的優先級大於棧中的操作符，直接入棧 */ if (operStack.priority(ch) <= operStack.priority(operStack.peek())){ //獲取數棧的數據和符號棧的運算符 num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); //運算 res = numStack.cal(oper,num1, num2); //將運算結果壓入數棧 numStack.push(res); //將當前運算符壓入符號棧 operStack.push(ch); }else { operStack.push(ch); } }else { //為空 直接入棧、 operStack.push(ch); } }else { //如果ch是數字 直接入數棧 // numStack.push(ch - 48); // ASCII碼轉換成int //當處理多位數時 有可能是多位數 因此 需要定義一個字符串變量 用於拼接 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 keepNum = ""; } } //index ++ 判斷是否掃描到表達式最後的位置 index++; if (index >= expression.length()){ break; } } //表達式掃描完畢後 從棧中pop出符號和數據 進行運算 while (true){ //如果符號棧為空 則計算結束 獲取最後的結果 此時數棧只有一個數字 if (operStack.isEmpty()){ break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); //運算 res = numStack.cal(oper,num1, num2); numStack.push(res); } //將最後的計算結果pop出 int finalRes = numStack.pop(); System.out.printf("表達式%s = %d", expression, finalRes); } }
