1. 棧的數(shù)據(jù)結(jié)構(gòu)

棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表

允許插入和刪除的一端稱為棧頂(Top),另一端稱為棧底,不含任何數(shù)據(jù)元素的棧稱為空棧,棧又稱為后進(jìn)先出的線性表

image

2.棧的實(shí)現(xiàn)

1. 順序方式

只能進(jìn)行尾插和尾刪

image

應(yīng)用Stack繼承自Vector(可以說Vector是加上線程安全的ArrayList)

2. 鏈?zhǔn)椒绞?/h4>

image

插入方式

image

3. 逆波蘭表達(dá)式

知識(shí):
a/2和a>>1位移行效率會(huì)更高


a2和a<<1位移效率高


為什么:


/和需要六個(gè)運(yùn)算集,位移只需要一個(gè)運(yùn)算集


為什么有6個(gè)計(jì)算集:


高級(jí)語言計(jì)算表達(dá)式不是簡單的計(jì)算,使用逆波蘭表達(dá)式

1.例使用逆波蘭表達(dá)式計(jì)算9+(3-1)*3+10/2(中綴表達(dá)式)

c和java會(huì)將中綴表達(dá)式,轉(zhuǎn)成后綴表達(dá)式進(jìn)行計(jì)算

中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式

橫向表示棧頂,豎向表示取到的操作符

規(guī)則:數(shù)字輸出,運(yùn)算法進(jìn)棧,括號(hào)匹配出棧,比棧頂優(yōu)先級(jí)低就出棧(表中1>2)

image

• 9直接輸出
• +號(hào)進(jìn)棧,棧底默認(rèn)有一個(gè)優(yōu)先級(jí)最高的#(如果+號(hào)優(yōu)先級(jí)比#高就出棧,如果低就直接往里面放)
• "("直接放到棧里面,這時(shí)候棧里面數(shù)據(jù)是#,+,(
• 3直接輸出,這時(shí)候輸出有9 3
• "-"號(hào)進(jìn)棧
• 1輸出 9 3 1
• )與(匹配,棧中()中的-直接出棧,這時(shí)候棧中剩#,+ 9 3 1 -
• *比+號(hào)優(yōu)先級(jí)高,直接進(jìn)棧
• 3輸出 9 3 1 - 3
• +號(hào)比棧頂?shù)?em>優(yōu)先級(jí)低,“”就出棧 9 3 1 - 3 *,+號(hào)和+號(hào)比優(yōu)先級(jí)也高,也出來 9 3 1 - 3 * +
• 數(shù)字10直接輸出 9 3 1 - 3 * + 10
• / 優(yōu)先級(jí)比+號(hào)高,直接放到棧里面
• 輸出數(shù)字2 9 3 1 - 3 * + 10 2
• 最后把棧里的東西取出來就輸出了后綴表達(dá)式 9 3 1 - 3 * + 10 2 / +
  
  計(jì)算方法
  
  
  1?? 數(shù)字入棧
  
  
  2?? 符號(hào)就取2個(gè)進(jìn)行計(jì)算,再入棧
• 數(shù)字入棧,棧中就是9 3 1,1處在棧頂
• 接下來是-號(hào),就從棧中取倆個(gè)數(shù)字,從右向左放就是3-1,然后把計(jì)算結(jié)果放到棧里面,這時(shí)棧里面就是9,2 2處于棧頂
• *號(hào)運(yùn)算符出現(xiàn),就再取倆個(gè)數(shù)字,從右向左放就是6,從新放到棧里面是9,6
• +號(hào)出現(xiàn),得出15放回棧里面
• 10,2入棧,棧里面就是15,10,2
• /運(yùn)算符出現(xiàn),棧里面改成15,5
• 最后還剩下+法,得出結(jié)果是20

2.遞歸

5!=54!
4!=43!這種情況可以使用遞歸解決

    public int fact(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * fact(n - 1);
        }
    }

1.使用遞歸玩轉(zhuǎn)漢諾塔游戲

    /**
     * 漢諾塔游戲
     *
     * @param n      盤子的個(gè)數(shù)
     * @param start  開始的柱子
     * @param middle 中介柱子
     * @param end    放結(jié)果的柱子
     */
    public static void hanoi(int n, int start, int middle, int end) {

        if (n <= 1) {
            System.out.println(start + "---" + end);
        } else {
            //通過結(jié)果的柱子，把盤子移到中間的柱子上
            hanoi(n - 1, start, end, middle);
            //把最下面的大盤子移動(dòng)到放結(jié)果的柱子上
            System.out.println(start + "---" + end);
            //把剩下的盤子從中間柱子通過第一個(gè)柱子移到最后一個(gè)柱子上
            hanoi(n - 1, middle, start, end);
        }
    }