前言
★ 這里是小冷的博客
? 優質技術好文見專欄
個人公眾號，分享一些技術上的文章，以及遇到的坑
當前系列：資料結構系列
源代碼 git 倉庫 ‘
資料結構代碼地址 代碼Git 倉庫地址
堆疊
我們這里將一個場景帶入學習
請輸入一個運算式
計算式:[722-5+1-5+3-3] 點擊計算 計算出結果
請問: 計算機底層是如何運算得到結果的？ 注意不是簡單的把算式列出運算,因為我們看這個算式 7 * 2 * 2 - 5, 但是計算機怎么理解這個算式的(對計算機而言，它接收到的就是一個字串)，我們討論的是這個問題，----> 堆疊
堆疊的介紹
-
堆疊的英文為(stack)
-
堆疊是一個先入后出(FILO-First In Last Out)的有序串列，
-
堆疊(stack)是限制線性表中元素的插入和洗掉只能在線性表的同一端進行的一種特殊線性表，允許插入和洗掉的 一端，為變化的一端，稱為堆疊頂(Top)，另一端為固定的一端，稱為堆疊底(Bottom)，
-
根據堆疊的定義可知，最先放入堆疊中元素在堆疊底，最后放入的元素在堆疊頂，而洗掉元素剛好相反，最后放入的元 素最先洗掉，最先放入的元素最后洗掉
-
圖解方式說明出堆疊(pop)和入堆疊(push)的概念
入堆疊與出堆疊 ： 堆疊 資料結構的特性 先入后出
堆疊的應用場景
-
子程式的呼叫：在跳往子程式前，會先將下個指令的地址存到堆疊中，直到子程式執行完后再將地址取出，以 回到原來的程式中，
-
處理遞回呼叫：和子程式的呼叫類似，只是除了儲存下一個指令的地址外，也將引數、區域變數等資料存入堆 堆疊中，
-
運算式的轉換[中綴運算式轉后綴運算式]與求值(實際解決)，
-
二叉樹的遍歷，
-
圖形的深度優先(depth 一 first)搜索法，
堆疊 快速入門（陣列模擬堆疊）
實作思路
詳細的每一部分的思路 都在代碼的注釋當中，想要詳細理解可以參考代碼中的注釋
package com.hyc.DataStructure.Stack;
import java.util.Scanner;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: ArrayStackDemo
* @author: 冷環淵 doomwatcher
* @description: TODO 用陣列來模擬堆疊
* @date: 2021/12/23 18:08
* @version: 1.0
*/
public class ArrayStackDemo {
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 res = stack.pop();
System.out.printf("出堆疊的資料是 %d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程式退出~~~");
}
}
class ArrayStack {
//堆疊的最大長度
private int MaxSize;
//模擬堆疊 資料就放在這個陣列里
private int[] stack;
// 等于堆疊頂 默認等于-1 代表最底部分
private int top = -1;
public ArrayStack() {
}
// 初始化堆疊
public ArrayStack(int maxSize) {
MaxSize = maxSize;
stack = new int[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 data) {
if (isFull()) {
System.out.println("堆疊滿");
return;
}
top++;
stack[top] = data;
}
// 將資料取出堆疊
public int pop() {
if (isempty()) {
throw new RuntimeException("堆疊是空的 無法取出");
}
int value = stack[top];
top--;
return value;
}
//遍歷堆疊 遍歷的時候需要從堆疊頂開始顯示資料
public void list() {
if (isempty()) {
System.out.println("堆疊是空的");
}
// 從堆疊頂開始輸出 其實就是倒序的輸出陣列
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
小總結
- 這里我們用陣列模擬了堆疊的一些基礎操作，入堆疊出堆疊遍歷內容，
- 除了使用陣列，我們還可以使用鏈表來實作堆疊，這里我也寫了這種寫法有詳細的注釋，代碼如下
package com.hyc.DataStructure.Stack;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: ListStackDemo
* @author: 冷環淵 doomwatcher
* @description: TODO 用鏈表來模擬堆疊
* @date: 2021/12/23 18:23
* @version: 1.0
*/
public class ListStackDemo {
public static void main(String[] args) {
listStack listStack = new listStack();
listStack.push(5);
listStack.push(6);
listStack.push(9);
System.out.println("出堆疊前");
listStack.list();
System.out.println("出堆疊后");
System.out.println("出堆疊：" + listStack.pop());
System.out.println("出堆疊：" + listStack.pop());
listStack.list();
}
}
class listStack {
//創建一個頭結點
StackNode head = new StackNode(0);
StackNode temp = head;
//判斷是否為空
public boolean isempty() {
return head.next == null;
}
//壓入堆疊
public void push(int value) {
//創建節點物件
StackNode newnode = new StackNode(value);
//改變頭節點指標的指向
temp.next = newnode;
//指標后移
temp = temp.next;
}
//出堆疊
public int pop() {
if (isempty()) {
throw new RuntimeException("堆疊空");
}
StackNode Before = head;
//將 before 節點遍歷到 temp也就是最后一個節點的上一個節點，讓temp指標想前遍歷
while (true) {
if (Before.next == temp) {
break;
}
Before = Before.next;
}
//將before的下一個節點為空相當于出堆疊之后 洗掉參考
Before.next = null;
//取值
int value = temp.data;
//此時 before指向的這個節點就是上一個節點的位置，將temp前移動，重復操作實作出堆疊
temp = Before;
return value;
}
//遍歷堆疊
public void list() {
// 判斷非空
if (isempty()) {
System.out.println("堆疊是空的");
return;
}
StackNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
System.out.println(temp.next.data);
temp = temp.next;
}
}
}
//單向鏈表節點
class StackNode {
// 資料
public int data;
//下一個節點
public StackNode next;
public StackNode(int data) {
this.data = data;
}
//方便輸出陳述句輸出
@Override
public String toString() {
return "StackNode{" +
", data='" + data + '\'' +
", next=" + next +
'}';
}
}
中綴運算式計算器
使用堆疊來實作綜合計算器
計算機底層是如何處理這種公式的呢，思路如下
我們需要使用兩個堆疊，一個記錄數字，一個記錄符號，根據這個堆疊的資料特性來通過符號和資料的出現規則來實作公式的計算
思路
- 1.通過一個index值（素引）,來遍歷我們的運算式
- 2.如果我們發現是一個數字，就直接入數堆疊
- 3.如果發現掃描到是一個符號，就分如下情況
- 3.1如果發現當前的符號堆疊為空，就直接入堆疊
- 3.2如果符號堆疊有運算子，就進行比較，如果當前的運算子的優先級小于或者等于堆疊中
- 的運算子，就需要從數堆疊中pop出兩個數在從符號堆疊中pop出一個符號，進行運算，
- 將得到結果，入數堆疊，然后將當前的運算子入符號堆疊，如果當前的運算子的優先級大
- 于堆疊中的運算子，就直接入符號找，
- 4.當運算式掃描完畢，就順序的從數樓和符號堆疊中pop出相應的數和符號，并運行.
- 5.最后在數堆疊只有一個數字，就是運算式的結果
- 驗證：3+2*6-2=13
- 這里我們就根據上面的思路實作接下來的思路
代碼實作
package com.hyc.DataStructure.Stack;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: Calculator
* @author: 冷環淵 doomwatcher
* @description: TODO
* @date: 2021/12/24 20:39
* @version: 1.0
*/
public class Calculator {
public static void main(String[] args) {
// 根據文章的思路 我們這里完成對一串計算只包含加減乘除的運算式運算操作
String expression = "3+2*6-2";
/** 計算思路 使用堆疊完成運算式的計算思路
* 1.通過一個index值（素引）,來遍歷我們的運算式
* 2.如果我們發現是一個數字，就直接入數堆疊
* 3.如果發現掃描到是一個符號，就分如下情況
* 3.1如果發現當前的符號堆疊為空，就直接入堆疊
* 3.2如果符號堆疊有運算子，就進行比較，如果當前的運算子的優先級小于或者等于堆疊中
* 的運算子，就需要從數堆疊中pop出兩個數在從符號堆疊中pop出一個符號，進行運算，
* 將得到結果，入數堆疊，然后將當前的運算子入符號堆疊，如果當前的運算子的優先級大
* 于堆疊中的運算子，就直接入符號找，
* 4.當運算式掃描完畢，就順序的從數樓和符號堆疊中pop出相應的數和符號，并運行.
* 5.最后在數堆疊只有一個數字，就是運算式的結果
* 驗證：3+2*6-2=13
* 這里我們就根據上面的思路實作接下來的思路
* */
// 創建兩個堆疊 一個存放需要計算的數字 一個存放需要運算的符號
ArrayCalStack numStack = new ArrayCalStack(10);
ArrayCalStack operStack = new ArrayCalStack(10);
// 定義相關變數
int index = 0; //用于指標掃描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
//將每次掃描得到的char保存到ch
char ch;
//用于萍姐多位數
String keepNums = "";
//開始while 回圈掃描運算式 expression
while (true) {
// 一次得到expression的每一個字符
ch = expression.substring(index, index + 1).charAt(0);
// 判斷ch 是什么（數字或者符號）之后進行操作
if (operStack.isOper(ch)) {
/* 如果符號堆疊有運算子，就進行比較，如果當前的運算子的優先級小于或者等于堆疊中
* 的運算子，就需要從數堆疊中pop出兩個數在從符號堆疊中pop出一個符號，進行運算，
* 將得到結果，入數堆疊，然后將當前的運算子入符號堆疊，如果當前的運算子的優先級大
* 于堆疊中的運算子，就直接入符號找，*/
//非空判斷
if (!operStack.isempty()) {
if (operStack.priotrity(ch) <= operStack.priotrity(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 {
// 如果為空直接入符號堆疊
operStack.push(ch);
}
} else {
// 如果是數字 就直接進入數字堆疊
/*思路
* 這里我們要考慮到多位數 在處理多位數的時候
* 我們需要掃描這個數的下一位一直到找到下一個符號
* 這個時候我們定義一個字串用于拼接找到的數
* */
// 處理多位數
keepNums += ch;
// 如果ch已經是 expression 最后一位name就直接入堆疊
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNums));
} else {
// 判斷下一個字符是不是數字 ，如果是就繼續向下判斷 是運算子則入堆疊，這里我們要看的是結束的地方是不是符號
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果最后一位事原酸父則如入堆疊 這里我們的操作變化就是 keepnums =1 或者是 keepnums = 123
numStack.push(Integer.parseInt(keepNums));
// 加入之后能講 keepnunms清空 用于下一位的判斷
keepNums = "";
}
}
}
// 讓 index +1 并判斷是否掃描到expression 最后
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(num1, num2, oper);
//入堆疊
numStack.push(res);
}
// 將數堆疊最后的數，pop出，就是結果
int res2 = numStack.pop();
System.out.printf("運算式%s = %d", expression, res2);
}
}
/*
* 應為要實作計算器 我們需要撰寫一些新的功能，
* */
class ArrayCalStack {
//堆疊的最大長度
private int MaxSize;
//模擬堆疊 資料就放在這個陣列里
private int[] stack;
// 等于堆疊頂 默認等于-1 代表最底部分
private int top = -1;
public ArrayCalStack() {
}
// 初始化堆疊
public ArrayCalStack(int maxSize) {
MaxSize = maxSize;
stack = new int[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 data) {
if (isFull()) {
System.out.println("堆疊滿");
return;
}
top++;
stack[top] = data;
}
// 將資料取出堆疊
public int pop() {
if (isempty()) {
throw new RuntimeException("堆疊是空的 無法取出");
}
int value = stack[top];
top--;
return value;
}
//遍歷堆疊 遍歷的時候需要從堆疊頂開始顯示資料
public void list() {
if (isempty()) {
System.out.println("堆疊是空的");
}
// 從堆疊頂開始輸出 其實就是倒序的輸出陣列
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
/* 回傳運算子的優先級 這個規則我們可以自己來設定 優先級使用數字來表示
* 數字越大優先級約高
* */
public int priotrity(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 = num2 / num1;
break;
case '*':
res = num1 * num2;
break;
default:
break;
}
return res;
}
}
這里我們實作了基礎的運算式運算，但是我們沒有考慮的事
- 我們實作了基本計算，但是沒有考慮小括號等
- 中綴運算式對我們來說是十分的好算的，但是對于計算機計算是不方便的，之后會給大家更新適合計算機計算的后綴運算式
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/397343.html
標籤：其他
上一篇：堆排序；快速排序；歸并排序