一 定義
- 棧的英文為(
stack) - 棧是一個(gè)
先入后出(FILO-First In Last Out)的有序列表乘碑。 - 棧(stack)是限制線性表中元素的插入和刪除只能在線性表的
同一端進(jìn)行的一種特殊線性表荞胡。允許插入和刪除的一端战转，為變化的一端，稱為棧頂(Top)作谚，另一端為固定的一端迫悠，稱為棧底(Bottom)。 - 根據(jù)棧的定義可知躁愿，最先放入棧中元素在棧底，最后放入的元素在棧頂沪蓬，而刪除元素剛好相反彤钟，最后放入的元素最先刪除，最先放入的元素最后刪除
出棧(pop)和入棧(push)的概念
image.png
image.png
應(yīng)用場景
-
子程序的調(diào)用(方法棧)：在跳往子程序前跷叉，會(huì)先將下個(gè)指令的地址存到堆棧(個(gè)人理解:每次遇到新指令逸雹，放到棧頂。執(zhí)行完新指令后云挟，繼續(xù)執(zhí)行之前的指令)中梆砸，直到子程序執(zhí)行完后再將地址取出，以回到原來的程序中园欣。 -
處理遞歸調(diào)用：和子程序的調(diào)用類似帖世，只是除了儲(chǔ)存下一個(gè)指令的地址外，也將參數(shù)沸枯、區(qū)域變量等數(shù)據(jù)存入堆棧中(jvm對(duì)一些尾遞歸會(huì)做優(yōu)化日矫，不用棧)。 - 表達(dá)式的轉(zhuǎn)換[
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式]與求值(實(shí)際解決)绑榴。 -
二叉樹的遍歷哪轿。 -
圖形的深度優(yōu)先(depth一first)搜索法。
二 數(shù)組實(shí)現(xiàn)
實(shí)現(xiàn)方式有數(shù)組和鏈表兩種翔怎，和前面的隊(duì)列基本大同小異窃诉。這里只展示了數(shù)組的實(shí)現(xiàn)方式
思路分析
- 和隊(duì)列象比，棧式
先進(jìn)后出.因此不用像隊(duì)列那樣特殊處理（下標(biāo)取模）來實(shí)現(xiàn)空間的復(fù)用 - 增加一個(gè)
擴(kuò)容特性 - 棧頂指針top赤套，
下一個(gè)下標(biāo)入棧,當(dāng)前下標(biāo)出棧((數(shù)量=top+1);默認(rèn)-1
代碼實(shí)現(xiàn)
對(duì)于棧來說飘痛，只需要一個(gè)指針（指針的定義都是由編寫者自己定義）
package com.zyc.stack;
/**
* @author zhuyc
* @create 2019-07-14 7:21
*/
public class MyStack {
private Object[] array;
private int top = -1;//棧頂指針，下一個(gè)下標(biāo)入棧,當(dāng)前下標(biāo)出棧((數(shù)量=top+1)
private int size;
public MyStack(int size){
array = new Object[size];
this.size = size;
}
public void push(Object element){
if(top == size-1){
//需要擴(kuò)容
resize(size*2);
}
array[++top] = element;
}
public Object pop(){
if(top == -1){
throw new RuntimeException("已到棧底");
}
return array[top--];
}
public void resize(int resize){
Object[] data = new Object[resize];
System.arraycopy(array,0,data,0,size);
array = data;
size = resize;
}
public void show(){
int i = 0;
System.out.println("----show start-------");
while(i<=top){
System.out.print(array[i]+"\t");
i++;
}
System.out.println();
System.out.println("----show end-------");
}
}
測試代碼
@Test
public void test1(){
MyStack stack = new MyStack(4);
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
stack.push("5");
stack.push("6");
stack.push("7");
stack.push("8");
stack.push("4");
stack.push("9");
stack.show();
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push("10");
stack.push("11");
stack.push("12");
stack.push("13");
stack.show();
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.show();
}
三 計(jì)算器
不考慮括號(hào)的情況下：
image.png
總結(jié)
- 空就直接入
- 不空先判斷
操作符優(yōu)先級(jí),大于直接入于毙；小于等于敦冬，數(shù)棧出兩個(gè)辅搬，符號(hào)棧出一個(gè)唯沮。計(jì)算完的值放入數(shù)棧脖旱。然后繼續(xù)依次判斷1，2 - 表達(dá)式結(jié)束介蛉，則依次出棧（數(shù)棧2個(gè)萌庆，符號(hào)一個(gè)）
代碼實(shí)現(xiàn)
package com.zyc.stack;
import java.util.HashMap;
import java.util.Map;
/**
* @author zhuyc
* @create 2019-07-14 8:04
*/
public class SimpleCalculator {
private MyStack numStack = new MyStack(10);
private MyStack opeStack = new MyStack(10);
public int calculate(String expression){
//TODO: 校驗(yàn)省略
int pre = 0;//本次次開始的截取位置
int last = 0;
char ele;
while(last<expression.length()){
ele = expression.charAt(last);
if(ele == '+' || ele == '-' || ele == '*' || ele == '/'){
//先截取前面的數(shù)字
String num = expression.substring(pre,last);
numStack.push(Integer.valueOf(num));
//再截取操作符
String ope = expression.substring(last,last+1);
dealOpe(ope);
pre = last+1;
last++;
}else{
last++;
}
}
//遍歷結(jié)束
String num = expression.substring(pre);
numStack.push(Integer.valueOf(num));
//將符號(hào)全部取出來，運(yùn)算完
while(true){
try {
String ope = (String) opeStack.pop();
int num1 = (int) numStack.pop();
int num2 = (int) numStack.pop();//前一個(gè)數(shù)字
cal(num2,num1,ope);
}catch (Exception e){
//結(jié)束了
break;
}
}
return (int) numStack.pop();
}
public void dealOpe(String ope){
String preOpe = null;
try {
preOpe = (String) opeStack.pop();
}catch (Exception e){
//符號(hào)棧為空
opeStack.push(ope);
return;
}
//比較優(yōu)先級(jí)
int preRank = opeRank.get(preOpe);
int rank = opeRank.get(ope);
if(rank <= preRank){
int num1 = (int) numStack.pop();
int num2 = (int) numStack.pop();//前一個(gè)數(shù)字
cal(num2,num1,preOpe);
//繼續(xù)放
dealOpe(ope);
}else{
opeStack.push(preOpe);//放回去
opeStack.push(ope);
}
}
public void cal(int preNum,int num,String ope){
int value = -1;
switch (ope){
case "+": value = preNum+num;break;
case "-": value = preNum-num;break;
case "*": value = preNum*num;break;
case "/": value = preNum/num;break;
}
numStack.push(value);
}
private Map<String,Integer> opeRank = new HashMap<String,Integer>(){
{
this.put("+",1);
this.put("-",1);
this.put("*",2);
this.put("/",2);
}
};
}
測試代碼
@Test
public void testSimpleCalculator(){
SimpleCalculator sc = new SimpleCalculator();
System.out.println(sc.calculate("36/12*3+12-9+15/5*2*2/4+23"));//38
}
四 前綴表達(dá)式
前綴表達(dá)式(波蘭表達(dá)式)
- 前綴表達(dá)式又稱波蘭式币旧，前綴表達(dá)式的運(yùn)算符位于操作數(shù)之前
- 舉例說明： (3+4)×5-6 對(duì)應(yīng)的前綴表達(dá)式就是 - × + 3 4 5 6
前綴表達(dá)式的計(jì)算機(jī)求值
從右至左掃描表達(dá)式践险，遇到數(shù)字時(shí)，將數(shù)字壓入堆棧吹菱，遇到運(yùn)算符時(shí)巍虫，彈出棧頂?shù)膬蓚€(gè)數(shù)，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算（棧頂元素 和 次頂元素）鳍刷，并將結(jié)果入棧占遥；重復(fù)上述過程直到表達(dá)式最左端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果
例如: (3+4)×5-6 對(duì)應(yīng)的前綴表達(dá)式就是 - × + 3 4 5 6 , 針對(duì)前綴表達(dá)式求值步驟如下:
- 從右至左掃描输瓜，將6瓦胎、5、4尤揣、3壓入堆棧
2 .遇到+運(yùn)算符搔啊，因此彈出3和4（3為棧頂元素，4為次頂元素）北戏，計(jì)算出3+4的值负芋，得7，再將7入棧 - 接下來是×運(yùn)算符嗜愈，因此彈出7和5示罗，計(jì)算出7×5=35，將35入棧
- 最后是-運(yùn)算符芝硬，計(jì)算出35-6的值蚜点，即29，由此得出最終結(jié)果
五 中綴表達(dá)式
- 中綴表達(dá)式就是常見的運(yùn)算表達(dá)式拌阴，如(3+4)×5-6
- 中綴表達(dá)式的求值是我們?nèi)俗钍煜さ纳芑妫菍?duì)計(jì)算機(jī)來說
卻不好操作(前面我們講的案例就能看的這個(gè)問題)，因此迟赃，在計(jì)算結(jié)果時(shí)陪拘，往往會(huì)將中綴表達(dá)式轉(zhuǎn)成其它表達(dá)式來操作(一般轉(zhuǎn)成后綴表達(dá)式.)
六 后綴表達(dá)式
后綴表達(dá)式又稱逆波蘭表達(dá)式,與前綴表達(dá)式相似，只是運(yùn)算符位于操作數(shù)之后
舉例說明： (3+4)×5-6 對(duì)應(yīng)的后綴表達(dá)式就是 3 4 + 5 × 6 –
再比如:
image.png
后綴表達(dá)式的計(jì)算機(jī)求值
從左至右掃描表達(dá)式纤壁，遇到數(shù)字時(shí)左刽，將數(shù)字壓入堆棧，遇到運(yùn)算符時(shí)酌媒，彈出棧頂?shù)?code>兩個(gè)數(shù)欠痴，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算（次頂元素 和 棧頂元素）迄靠，并將結(jié)果入棧； 重復(fù)上述過程直到表達(dá)式最右端喇辽，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果
例如: (3+4)×5-6 對(duì)應(yīng)的后綴表達(dá)式就是 3 4 + 5 × 6 - , 針對(duì)后綴表達(dá)式求值步驟如下:
- 從左至右掃描掌挚，將3和4壓入堆棧；
- 遇到+運(yùn)算符菩咨，因此彈出4和3（
4為棧頂元素吠式，3為次頂元素），計(jì)算出3+4(注意順序)的值抽米，得7特占，再將7入棧； - 將5入棧云茸；
- 接下來是×運(yùn)算符摩钙，因此彈出5和7，計(jì)算出7×5=35查辩，將35入棧胖笛；
- 將6入棧；
- 最后是-運(yùn)算符宜岛，計(jì)算出35-6的值长踊，即29，由此得出最終結(jié)果
七 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
大家看到萍倡，后綴表達(dá)式適合計(jì)算式進(jìn)行運(yùn)算身弊，但是人卻不太容易寫出來，尤其是表達(dá)式很長的情況下列敲，因此在開發(fā)中阱佛，我們需要將 中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式。
具體步驟如下:
- 初始化兩個(gè)棧：
運(yùn)算符棧s1和儲(chǔ)存中間結(jié)果的棧s2戴而； -
從左至右掃描中綴表達(dá)式凑术； - 遇到操作數(shù)時(shí)，將其壓s2所意；
- 遇到運(yùn)算符時(shí)淮逊，
比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)：- 如果s1為
空，或棧頂運(yùn)算符為左括號(hào)“(”扶踊，則直接將此運(yùn)算符入棧s1泄鹏； - 若優(yōu)先級(jí)比棧頂運(yùn)算符的
高，也將運(yùn)算符壓入s1秧耗； - 否則备籽，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到
s2中，再次轉(zhuǎn)到(步驟4)與s1中新的棧頂運(yùn)算符相比較分井；
- 如果s1為
- 遇到括號(hào)時(shí)：
- 如果是·左括號(hào)“(”·车猬，則直接壓入s1
- 如果是·右括號(hào)“)”·霉猛，則·依次彈出·s1棧頂?shù)倪\(yùn)算符，并壓入s2诈唬，
直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄
-
重復(fù)步驟2至5缩麸，直到表達(dá)式的最右邊 - 將s1中
剩余的運(yùn)算符依次彈出并壓入s2
8, 依次彈出s2中的元素并輸出铸磅，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式(從下往上讀)
總結(jié)
上面這個(gè)有點(diǎn)煩。
轉(zhuǎn)換過程需要用到棧杭朱，具體過程如下：
1）如果遇到操作數(shù)阅仔，我們就直接將其輸出。
2）如果遇到操作符弧械，則我們將其放入到棧中八酒，遇到左括號(hào)時(shí)我們也將其放入棧中。
3）如果遇到一個(gè)右括號(hào)刃唐，則將棧元素彈出羞迷，將彈出的操作符輸出直到遇到左括號(hào)為止。注意画饥，左括號(hào)只彈出并不輸出衔瓮。
4）如果遇到任何其他的操作符，如（“+”抖甘， “*”热鞍，“（”）等，從棧中彈出元素直到遇到發(fā)現(xiàn)更低優(yōu)先級(jí)的元素(或者棧為空)(優(yōu)先級(jí)高的先出棧)為止衔彻。彈出完這些元素后薇宠，才將遇到的操作符壓入到棧中。有一點(diǎn)需要注意艰额，只有在遇到" ) "的情況下我們才彈出" ( "澄港，其他情況我們都不會(huì)彈出" ( "。
5）如果我們讀到了輸入的末尾柄沮，則將棧中所有元素依次彈出慢睡。
代碼實(shí)現(xiàn)
public static void translate(String MidStr) {
String express = "";
String sign = "";
Stack<String> stack = new Stack<>();
String[] strs = MidStr.split(" ");
for(String str:strs) {
if("(".equals(str)) {//這個(gè)直接放
stack.push(str);
}else if(")".equals(str)) {
do {
sign = stack.pop();
if(!"(".equals(sign)) {
express+=" "+sign;
}else {//直到'('為止，并且不輸出
break;
}
}while(!stack.empty());
}else if("+".equals(str)||"-".equals(str)) {
while(!stack.empty()) {//非空就出棧
sign = stack.pop();//出棧
// System.out.println(":"+sign);
if("(".equals(sign)) {//+或-只有碰到(才會(huì)停止铡溪，其他優(yōu)先度都不比它們低漂辐，`(`不會(huì)入棧的
stack.push("(");//放回去
break;
}
express+=" "+sign;//
}
stack.push(str);
}else if("*".equals(str) || "/".equals(str)) {
while(!stack.empty()) {
sign = stack.pop();//出棧看看是什么
if("*".equals(sign) || "/".equals(sign)) {//只有這兩個(gè)才是一樣的
express+=" "+sign;
}else {
stack.push(sign);//放回去
break;
}
}
stack.push(str);
}else {
express += " "+str;
}
}
int size = stack.size();
//pop的size是變化的棕硫，先取好
for(int i =0;i<size;i++) {
System.out.println("chu");
express += " "+stack.pop();
}
System.out.println(express);
}
