總目錄：地址如下看總綱
1、棧是什么
1、棧是一個(gè)先入后出(FILO-First In Last Out)的有序列表。
2、棧(stack)是限制線性表中元素的插入和刪除只能在線性表的同一端進(jìn)行的一種特殊線性表。
允許插入和刪除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。
3、根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，
最后放入的元素最先刪除，最先放入的元素最后刪除
2、出入棧圖解
image.png
image.png
3、棧的數(shù)組設(shè)計(jì)思路
image.png
- 定義一個(gè) top 來表示棧頂?shù)慕菢?biāo)位置，初始化 為 -1
- 入棧的操作，當(dāng)有數(shù)據(jù)加入到棧時(shí)， top++; stack[top] = data;
- 出棧的操作， int value = stack[top]; top--, return value
4、代碼實(shí)現(xiàn)
package com.kk.datastructure.stack;
import java.util.Scanner;
/**
* title: 棧實(shí)現(xiàn)(通過數(shù)組)
* @author 阿K
* 2020年11月28日 下午11:28:43
*/
public class StackArrayDemo {
public static void main(String[] args) {
// 先創(chuàng)建一個(gè)ArrayStack對象->表示棧
StackArray stack = new StackArray(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ù)(出棧)");
System.out.println("請輸入你的選擇");
key = scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("請輸入一個(gè)數(shù)");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出棧的數(shù)據(jù)是 %d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~~");
}
}
//定義一個(gè) StackArray 表示棧
class StackArray {
private int maxSize;// 棧的大小
private int[] stack;// 數(shù)組，數(shù)組模擬棧，數(shù)據(jù)就放在該數(shù)組
private int top = -1;// top表示棧頂?shù)慕菢?biāo)，初始化為-1
// 構(gòu)造器
public StackArray(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 棧滿
public boolean isFull() {
// return stack.length == maxSize;
return top == maxSize - 1;
}
// ?？? public boolean isEmpty() {
return top == -1;
}
// 入棧-push
public void push(int data) {
// 判斷是否滿
if (isFull()) {
System.out.println("棧滿");
return;
}
top++;
stack[top] = data;
}
// 出棧-pop,將棧頂?shù)臄?shù)據(jù)返回
public int pop() {
// 判斷是否為空
if (isEmpty())
throw new RuntimeException("棧空，無法?。?！");
return stack[top--];
}
// 遍歷棧
public void list() {
// 判空
if (isEmpty())
System.out.println("當(dāng)前棧沒有數(shù)據(jù)，無法遍歷");
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
5、棧的應(yīng)用場景
- 子程序的調(diào)用：在跳往子程序前，會(huì)先將下個(gè)指令的地址存到堆棧中，直到子程序執(zhí)行完后再將地址取出，以回到原來的程序中。 (函數(shù)棧)
- 處理遞歸調(diào)用：和子程序的調(diào)用類似，只是除了儲(chǔ)存下一個(gè)指令的地址外，也將參數(shù)、區(qū)域變量等數(shù)據(jù)存入堆棧中。(函數(shù)棧)
- 表達(dá)式的轉(zhuǎn)換[中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式]與求值(實(shí)際解決)。
- 二叉樹的遍歷。
- 圖形的深度優(yōu)先(depth一first)搜索法。
6、棧實(shí)現(xiàn)一個(gè)綜合計(jì)算器
當(dāng)前一個(gè)字符串，"3+2*6=?","30+2/4=?"
通過棧得出結(jié)果
7、棧實(shí)現(xiàn)表達(dá)式計(jì)算器的思路
image.png
- 通過一個(gè) index 值（索引），來遍歷我們的表達(dá)式
- 如果我們發(fā)現(xiàn)是一個(gè)數(shù)字, 就直接入數(shù)棧
- 如果發(fā)現(xiàn)掃描到是一個(gè)符號, 就分如下情況
1 如果發(fā)現(xiàn)當(dāng)前的符號棧為 空，就直接入棧
2 如果符號棧有操作符，就進(jìn)行比較,如果當(dāng)前的操作符的優(yōu)先級小于或者等于棧中的操作符， 就需要從數(shù)棧中pop出兩個(gè)數(shù),在從符號棧中pop出一個(gè)符號，進(jìn)行運(yùn)算，將得到結(jié)果，入數(shù)棧，然后將當(dāng)前的操作符入符號棧， 如果當(dāng)前的操作符的優(yōu)先級大于棧中的操作符， 就直接入符號棧.- 當(dāng)表達(dá)式掃描完畢，就順序的從 數(shù)棧和符號棧中pop出相應(yīng)的數(shù)和符號，并運(yùn)行.
- 最后在數(shù)棧只有一個(gè)數(shù)字，就是表達(dá)式的結(jié)果
8、代碼
package com.kk.datastructure.stack.calculatro;
/**
* title: 棧實(shí)現(xiàn)綜合計(jì)算器
* @author 阿K
* 2020年11月29日 下午3:30:14
*/
public class Calculatro {
public static void main(String[] args) {
// expression 表達(dá)式
String expression = "30-8*4/2";
// 創(chuàng)建兩個(gè)棧，一個(gè)數(shù)棧，一個(gè)符號棧
StackArray numStack = new StackArray(10);
StackArray operStack = new StackArray(10);
// 定義需要的相關(guān)變量
int index = 0;// //用于掃描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' '; // 將每次掃描得到char保存到ch
String keepNum = ""; // 用于拼接 多位數(shù)
// 開始while循環(huán)的掃描expression
while (true) {
// 依次得到expression 的每一個(gè)字符
ch = expression.substring(index, index + 1).charAt(0);
// 判斷ch是什么，然后做相應(yīng)的處理
if (operStack.isOper(ch)) {// 如果是運(yùn)算符
// 判斷當(dāng)前的符號棧是否為空
if (!operStack.isEmpty()) {
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
// 如果符號棧有操作符，就進(jìn)行比較
// 比較規(guī)則：如果當(dāng)前操作符的優(yōu)先級小于或者等于棧中的操作符，就需要從數(shù)棧中pop出兩個(gè)數(shù)來
// 再從符號棧中pop出一個(gè)操作符，進(jìn)行運(yùn)算，將得到的結(jié)果入數(shù)棧，然后將當(dāng)前操作符入符號棧
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
// 將運(yùn)算結(jié)果，入數(shù)棧
numStack.push(res);
// 操作符入操作符棧
operStack.push(ch);
} else {
// 如果當(dāng)前操作符優(yōu)先級大于操作符棧頂?shù)闹祪?yōu)先級，則直接入操作符棧
operStack.push(ch);
}
} else {
// 如果操作符棧為空，則直接入棧
operStack.push(ch);
}
} else {// 如果是數(shù)，則入數(shù)棧
//numStack.push(ch - 48); //? "1+3" '1' => 1
// 1、在處理多位數(shù)的時(shí)候，不能遇到數(shù)就直接入棧，因?yàn)榭赡軘?shù)多位數(shù)
// 2、在處理數(shù)時(shí)，需要向expression 表達(dá)式的 index 再往后移動(dòng) 一位看 一下，如果是數(shù) 則繼續(xù)掃描，
//如果遇到的是符號，就可以直接入數(shù)棧了
// 3、因此需要一個(gè)輔助的字符串拼接判斷
keepNum +=ch;// 處理多位數(shù)
// 如果ch已經(jīng)是expression的最后一位，就直接入棧
if(index == expression.length() -1) {
numStack.push(Integer.valueOf(keepNum));
}else {
// 判斷下一個(gè)字符是不是數(shù)字，如果是數(shù)字，就繼續(xù)掃描，如果是運(yùn)算符，則入棧
// 注意是看后一位，不是index++
if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
// 如果后一位是運(yùn)算符，則入棧 keepNum = "1" 或者 "123"
numStack.push(Integer.valueOf(keepNum));
// 清空（注意?。。。? keepNum = "";
}
}
}
// 讓index + 1, 并判斷是否掃描到expression最后
index++;
if(index >= expression.length()) {
break;
}
}
// 當(dāng)表達(dá)式掃描計(jì)算完畢，就順序的從 數(shù)棧和符號棧中pop出相應(yīng)的數(shù)和符號，并運(yùn)行
while(true) {
// 如果符號棧為空，則計(jì)算到最后的結(jié)果, 數(shù)棧中只有一個(gè)數(shù)字【結(jié)果】
if(operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);//入棧
}
// 將數(shù)棧的最后數(shù)，pop出，就是結(jié)果
int result = numStack.pop();
System.out.printf("表達(dá)式 %s = %d", expression, result);
}
}
//定義一個(gè) StackArray 表示棧
class StackArray {
private int maxSize;// 棧的大小
private int[] stack;// 數(shù)組，數(shù)組模擬棧，數(shù)據(jù)就放在該數(shù)組
private int top = -1;// top表示棧頂?shù)慕菢?biāo)，初始化為-1
// 構(gòu)造器
public StackArray(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
// 查看棧頂?shù)闹?，不是pop
public int peek() {
return stack[top];
}
// 返回運(yùn)算符優(yōu)先級，數(shù)字越大，優(yōu)先級越高
public int priority(int oper) {
if(oper == '*' || oper == '/') {
return 2;
}
else if(oper == '+' || oper == '-') {
return 1;
}
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; // res 用于存放計(jì)算的結(jié)果
switch (oper) {
case '+':
res = num1+num2;
break;
case '-':
res = num2-num1;
break;
case '*':
res = num1*num2;
break;
case '/':
res = num2/num1;
break;
default:
break;
}
return res;
}
// 棧滿
public boolean isFull() {
// return stack.length == maxSize;
return top == maxSize - 1;
}
// ?？? public boolean isEmpty() {
return top == -1;
}
// 入棧-push
public void push(int data) {
// 判斷是否滿
if (isFull()) {
System.out.println("棧滿");
return;
}
top++;
stack[top] = data;
}
// 出棧-pop,將棧頂?shù)臄?shù)據(jù)返回
public int pop() {
// 判斷是否為空
if (isEmpty())
throw new RuntimeException("?？?，無法?。?！");
return stack[top--];
}
// 遍歷棧
public void list() {
// 判空
if (isEmpty())
System.out.println("當(dāng)前棧沒有數(shù)據(jù)，無法遍歷");
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
