一種"操作受限"的線性表數(shù)據(jù)結(jié)構(gòu)--棧(Stack)
棧(Stack)是限定盡在表尾部進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)司训，另一端稱為棧底(bottom)液走，不含任何數(shù)據(jù)元素的棧稱為空棧。支持兩個(gè)基本操作：入棧push()和出棧pop()柳弄。
棧的順序存儲(chǔ)結(jié)構(gòu)--順序棧(Array實(shí)現(xiàn))
// 基于數(shù)組實(shí)現(xiàn)的順序棧
public class ArrayStack {
private String[] items; // 數(shù)組
private int count; // 棧中元素個(gè)數(shù)
private int n; // 棧的大小
// 初始化數(shù)組唱捣，申請(qǐng)一個(gè)大小為 n 的數(shù)組空間
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入棧操作
public boolean push(String item) {
// 數(shù)組空間不夠了两蟀，直接返回 false，入棧失敗爷光。
if (count == n) return false;
// 將 item 放到下標(biāo)為 count 的位置垫竞，并且 count 加一
items[count] = item;
++count;
return true;
}
// 出棧操作
public String pop() {
// 棧為空，則直接返回 null
if (count == 0) return null;
// 返回下標(biāo)為 count-1 的數(shù)組元素蛀序，并且棧中元素個(gè)數(shù) count 減一
String tmp = items[count-1];
--count;
return tmp;
}
}
棧在入棧和出棧過程中欢瞪，只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間，所以時(shí)間復(fù)雜度和空間復(fù)雜度都是O(1)徐裸。
兩棧共享空間
棧的順序存儲(chǔ)是很方便的遣鼓，因?yàn)樗粶?zhǔn)棧頂進(jìn)出元素，所以不存在線性表的插入和刪除時(shí)需要移動(dòng)元素的問題重贺。但是他有一個(gè)很大的缺陷骑祟，就是必須實(shí)現(xiàn)確定數(shù)組存儲(chǔ)空間大小，萬一不夠用了气笙，就需要?jiǎng)討B(tài)擴(kuò)容數(shù)組的容量次企，這樣會(huì)使入棧的空間復(fù)雜度和時(shí)間復(fù)雜度退化成O(n)。
思路：數(shù)組有兩個(gè)端點(diǎn)潜圃，兩個(gè)棧有兩個(gè)棧底缸棵，讓一個(gè)棧的棧底為數(shù)組的始端，即下標(biāo)為0處谭期，另一個(gè)棧的棧底為數(shù)組的末端堵第，即下標(biāo)為數(shù)組長度n-1處。這樣兩個(gè)棧如果增加元素隧出，就是兩端點(diǎn)向中間延伸踏志，只要是兩個(gè)棧頂指針不見面，兩個(gè)棧就可以一直使用胀瞪。
這樣的數(shù)據(jù)結(jié)構(gòu)针余，通常都是當(dāng)兩個(gè)具有相同數(shù)據(jù)類型的棧，兩個(gè)棧的空間需求有相反關(guān)系時(shí)，也就是一個(gè)棧增長時(shí)另一個(gè)棧在縮短的情況圆雁。這樣使用兩棧共享空間存儲(chǔ)方法才有比較大的意義
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--鏈?zhǔn)綏?/h4>
一般的情況是將棧頂放在鏈表的頭部傍妒，因?yàn)殒湵肀旧碇С挚焖僭鰟h結(jié)點(diǎn)，所以在時(shí)間和空間復(fù)雜度上都是O(1)摸柄。
如果棧的使用過程中元素變化不可預(yù)料，有時(shí)很小既忆，有時(shí)非常大驱负，那么最后用鏈?zhǔn)綏＃粗绻淖兓诳煽胤秶鷥?nèi)患雇，建議使用順序棧會(huì)更好一些跃脊。
棧的作用
在函數(shù)調(diào)用中的應(yīng)用--函數(shù)調(diào)用棧
在jvm內(nèi)存中，分配了一塊獨(dú)立的內(nèi)存空間--棧苛吱，用來存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量酪术，每次進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧翠储，當(dāng)被調(diào)用函數(shù)執(zhí)行完成绘雁，返回之后，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧援所。
瀏覽器的前進(jìn)與后退功能
使用兩個(gè)棧庐舟，A和B，把首次瀏覽的頁面一次壓入棧A住拭，當(dāng)點(diǎn)擊后退按鈕時(shí)挪略，再依次從棧A中出棧，并將出棧的數(shù)據(jù)依次放入棧B滔岳，這樣就實(shí)現(xiàn)了瀏覽器的前進(jìn)和后退功能杠娱。
棧在表達(dá)式求值中的應(yīng)用
沒有括號(hào)的表達(dá)式
通過兩個(gè)棧來實(shí)現(xiàn)的，其中一個(gè)保存操作數(shù)的棧谱煤，另一個(gè)是保存運(yùn)算符的棧摊求。從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)據(jù)趴俘，就直接壓入操作數(shù)棧睹簇；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較寥闪。
如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)高太惠，就將當(dāng)前運(yùn)算符壓入棧；如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同疲憋，從運(yùn)算符棧中取棧頂運(yùn)算符凿渊，從操作數(shù)棧的棧頂取2個(gè)操作數(shù)，然后進(jìn)行計(jì)算，再把計(jì)算完的結(jié)果壓入操作數(shù)棧埃脏，繼續(xù)比較搪锣。
有括號(hào)的表達(dá)式
-先將標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式(中綴表達(dá)式)轉(zhuǎn)成后綴表達(dá)式(逆波蘭表示)
規(guī)則：從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào)，若是數(shù)字就輸出彩掐，即成為后綴表達(dá)式的一部分构舟；若是符號(hào)，則判斷其與棧頂符號(hào)的優(yōu)先級(jí)堵幽，是右括號(hào)或優(yōu)先級(jí)不高于棧頂符號(hào)(乘除優(yōu)先加減)則棧頂元素依次出棧并輸出狗超，并將當(dāng)前符號(hào)進(jìn)棧，一直到最終輸出后綴表達(dá)式為止朴下。
-應(yīng)用后綴表達(dá)式計(jì)算最終的結(jié)果
規(guī)則：從左到右遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào)努咐，遇到是數(shù)字就進(jìn)棧，遇到是符號(hào)殴胧，就將處于棧頂兩個(gè)數(shù)字出棧渗稍，進(jìn)行運(yùn)算，運(yùn)算結(jié)果進(jìn)棧团滥，一直到最終獲得結(jié)果竿屹。
