棧的規(guī)則
先進(jìn)后出诅妹。如：依次入棧順序?yàn)椋篈,B,C,D;怎出棧順序?yàn)椋篋,C,B,A .
二叉樹和表達(dá)式
- 表達(dá)式的二叉樹展示方式
例如：(a+b×(c-d))-e/f缸榄，我們平時(shí)數(shù)學(xué)中表達(dá)式槐沼，其實(shí)就是所謂的中綴表達(dá)式表達(dá)式用樹形來表示，如圖所示瓷们。運(yùn)算符在樹中放在非終端結(jié)點(diǎn)的位置上界牡，操作數(shù)放在葉子結(jié)點(diǎn)處。
當(dāng)我們對(duì)此二叉樹進(jìn)行先序俩块、中序和后序遍歷后黎休，便可得到表達(dá)式的前綴、中綴和后綴書寫形式：
前綴：
-+a*b-cd/ef中綴：
a+b*c-d-e/f后綴：
abcd-*+ef/- 一般的解法玉凯，可以考慮將中綴表達(dá)式轉(zhuǎn)換成二叉樹势腮，在求值。
前漫仆、中捎拯、后綴表達(dá)式
舉例：
(3 + 4) × 5 - 6就是中綴表達(dá)式
- × + 3 4 5 6前綴表達(dá)式
3 4 + 5 × 6 -后綴表達(dá)式中綴表達(dá)式（中綴記法）
直接按照數(shù)學(xué)邏輯求值就行了。個(gè)人感覺中綴表達(dá)式最容器轉(zhuǎn)換成二叉樹了盲厌，因?yàn)闃涞奶攸c(diǎn)是：根節(jié)點(diǎn)為運(yùn)算操作符署照，而非根葉子節(jié)點(diǎn)為操作數(shù)，根據(jù)這個(gè)規(guī)則和表達(dá)式的優(yōu)先規(guī)則切分成根吗浩、左右子樹就可以了建芙。-
前綴表達(dá)式（前綴記法、波蘭式）
特點(diǎn)：前綴表達(dá)式的運(yùn)算符位于操作數(shù)之前懂扼。前綴表達(dá)式的計(jì)算機(jī)求值：
從右至左（其實(shí)很簡(jiǎn)單記住掃描方向禁荸，就是從第一個(gè)操作數(shù)所在的那一端開始掃描）掃描表達(dá)式，遇到數(shù)字時(shí)阀湿，將數(shù)字壓入堆棧赶熟，遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)數(shù)陷嘴，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算（棧頂元素 op 次頂元素）映砖，并將結(jié)果入棧；重復(fù)上述過程直到表達(dá)式最左端灾挨，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果邑退。
例如前綴表達(dá)式“- × + 3 4 5 6”：
(1) 從右至左掃描，將6劳澄、5瓜饥、4、3壓入堆棧浴骂；
(2) 遇到+運(yùn)算符乓土，因此彈出3和4（3為棧頂元素，4為次頂元素，注意與后綴表達(dá)式做比較）趣苏，計(jì)算出3+4的值狡相，得7，再將7入棧食磕；
(3) 接下來是×運(yùn)算符尽棕，因此彈出7和5，計(jì)算出7×5=35彬伦，將35入棧滔悉；
(4) 最后是-運(yùn)算符，計(jì)算出35-6的值单绑，即29回官，由此得出最終結(jié)果使用棧，將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式
遵循以下步驟：
(1) 初始化兩個(gè)棧：運(yùn)算符棧S1和儲(chǔ)存中間結(jié)果的棧S2搂橙；
(2) 從右至左（和計(jì)算求值時(shí)的掃描方向是一致的）掃描中綴表達(dá)式歉提；
(3) 遇到操作數(shù)時(shí)，將其壓入S2区转；
(4) 遇到運(yùn)算符時(shí)苔巨，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí)：
(4-1) 如果S1為空，或棧頂運(yùn)算符為右括號(hào)“)”废离，則直接將此運(yùn)算符入棧侄泽；
(4-2) 否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的較高或相等蜻韭，也將運(yùn)算符壓入S1蔬顾；（意思是棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)時(shí)刻至少要高于前面入棧的）
(4-3) 否則，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中湘捎，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運(yùn)算符相比較；
(5) 遇到括號(hào)時(shí)：
(5-1) 如果是右括號(hào)“)”窄刘，則直接壓入S1窥妇；
(5-2) 如果是左括號(hào)“(”，則依次彈出S1棧頂?shù)倪\(yùn)算符娩践，并壓入S2活翩，直到遇到右括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄翻伺；
(6) 重復(fù)步驟(2)至(5)材泄，直到表達(dá)式的最左邊；
(7) 將S1中剩余的運(yùn)算符依次彈出并壓入S2吨岭；
(8) 依次彈出S2中的元素并輸出拉宗，結(jié)果即為中綴表達(dá)式對(duì)應(yīng)的前綴表達(dá)式。
下面舉例演示一下，省的畫圖了旦事，就借用一下網(wǎng)上現(xiàn)成的吧魁巩，謝謝這位大神。
例如姐浮，將中綴表達(dá)1+((2+3)×4)-5轉(zhuǎn)換為前綴表達(dá)式的過程如下（最后S2出棧谷遂，結(jié)果為- + 1 × + 2 3 4 5）：
-
后綴表達(dá)式（后綴記法、逆波蘭式）
特點(diǎn)：后綴表達(dá)式與前綴表達(dá)式類似卖鲤，只是運(yùn)算符位于操作數(shù)之后肾扰。后綴表達(dá)式的計(jì)算機(jī)求值
與前綴表達(dá)式求值方式差不多，只是掃描方向相反蛋逾，從左到右開始掃描集晚。將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
與轉(zhuǎn)換為前綴表達(dá)式相似，遵循以下步驟：
(1) 初始化兩個(gè)棧：運(yùn)算符棧S1和儲(chǔ)存中間結(jié)果的棧S2换怖；
(2) 從左至右（再提一次甩恼，此時(shí)操作數(shù)在左邊）掃描中綴表達(dá)式；
(3) 遇到操作數(shù)時(shí)沉颂，將其壓入S2条摸；
(4) 遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí)：
(4-1) 如果S1為空铸屉，或棧頂運(yùn)算符為左括號(hào)“(”钉蒲，則直接將此運(yùn)算符入棧；
(4-2) 否則彻坛，若優(yōu)先級(jí)比棧頂運(yùn)算符的高顷啼，也將運(yùn)算符壓入S1（注意轉(zhuǎn)換為前綴表達(dá)式時(shí)是優(yōu)先級(jí)較高或相同，而這里則不包括相同的情況）昌屉；
(4-3) 否則钙蒙，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運(yùn)算符相比較间驮；
(5) 遇到括號(hào)時(shí)：
(5-1) 如果是左括號(hào)“(”躬厌，則直接壓入S1；
(5-2) 如果是右括號(hào)“)”竞帽，則依次彈出S1棧頂?shù)倪\(yùn)算符扛施，并壓入S2，直到遇到左括號(hào)為止屹篓，此時(shí)將這一對(duì)括號(hào)丟棄疙渣；
(6) 重復(fù)步驟(2)至(5)，直到表達(dá)式的最右邊堆巧；
(7) 將S1中剩余的運(yùn)算符依次彈出并壓入S2妄荔；
(8) 依次彈出S2中的元素并輸出泼菌，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式（轉(zhuǎn)換為前綴表達(dá)式時(shí)不用逆序）。
例如懦冰，將中綴表達(dá)1+((2+3)×4)-5轉(zhuǎn)換為后綴表達(dá)式的過程如下（結(jié)果為1 2 3 + 4 × + 5 -（注意S2出棧后需要逆序輸出）灶轰。）：
根據(jù)表達(dá)式反推二叉樹
-
中綴表達(dá)式求二叉樹：
其實(shí)記住運(yùn)算符為根節(jié)點(diǎn)，然后把操作數(shù)作為左右葉子節(jié)點(diǎn)刷钢，根據(jù)二叉樹的中序遍歷笋颤，構(gòu)建一棵子樹，不斷自下而上内地，就能復(fù)原了伴澄。舉例(3 + 4) × 5 - 6（畫了個(gè)丑圖）：中綴表達(dá)式轉(zhuǎn)二叉樹 -
后綴表達(dá)式求二叉樹：
思路是一樣的，拿兩個(gè)操作數(shù)和一個(gè)運(yùn)算符阱缓，不斷自底向上組建二叉樹非凌。舉例：3 4 + 5 × 6 -后綴表達(dá)式。（寫字太丑了荆针，我自己都看不下去了敞嗡。。航背。喉悴。。）
后綴表達(dá)式求二叉樹 前綴表達(dá)式轉(zhuǎn)二叉樹
抱歉玖媚，我想不出來箕肃。。今魔。勺像。
兩個(gè)棧共用存儲(chǔ)空間
棧滿條件：棧1向上增長(zhǎng)，棧2向下增長(zhǎng)错森，顯然當(dāng)top[1]和top[2]相鄰時(shí)吟宦，棧滿。
棧和堆
棧區(qū)（stack）— 由編譯器自動(dòng)分配釋放 涩维，存放為運(yùn)行函數(shù)而分配的局部變量殃姓、函數(shù)參數(shù)、返回?cái)?shù)據(jù)激挪、返回地址等。
堆區(qū)（heap） — 一般由程序員分配釋放锋叨， new, malloc之類的垄分，若程序員不釋放，程序結(jié)束時(shí)可能由OS回收 娃磺。
