棧蔫饰，在這里說的是一種數(shù)據(jù)結(jié)構(gòu)。
你還可能知道的棧
提到“椨洳颍”篓吁，做Java的同學(xué)還會(huì)想起Java內(nèi)存模型中的“棧”蚪拦，與之緊密關(guān)聯(lián)的還有一個(gè)名詞——堆杖剪，但是這里，此棧非彼棧驰贷。
引用《深入理解Java虛擬機(jī)》中有關(guān)棧的介紹
經(jīng)常有人把Java內(nèi)存區(qū)分為堆內(nèi)存（Heap）和棧內(nèi)存（Stack）盛嘿，這種分法比較粗糙，Java內(nèi)存區(qū)域的劃分實(shí)際上遠(yuǎn)比這復(fù)雜括袒。這種劃分方式的流行只能說明大多數(shù)程序員最關(guān)注的次兆、與對(duì)象內(nèi)存分配關(guān)系最密切的內(nèi)存區(qū)域是這兩塊。其中所指的“堆”筆者在后面專門講述箱熬，而所指的“椑嗫眩”就是現(xiàn)在講的虛擬機(jī)棧，或者說是虛擬機(jī)棧中局部變量部分城须。
局部變量表存放了編譯可知的各種基本數(shù)據(jù)類型（boolean蚤认、byte、char糕伐、short砰琢、int、float良瞧、long陪汽、double）、對(duì)象引用（reference類型褥蚯，它不等同于對(duì)象本身挚冤，可能是一個(gè)只想對(duì)象起始地址的引用指針，也可能是指向一個(gè)對(duì)象的句柄或其他與此對(duì)象相關(guān)的位置）和returnAddress類型（指向了一條字節(jié)碼指令的地址）
說人話就是赞庶，Java內(nèi)存結(jié)構(gòu)中的一部分训挡，線程私有澳骤，用來(lái)存儲(chǔ)指定的數(shù)據(jù)類型數(shù)據(jù)。
棧是什么
棧是一種數(shù)據(jù)結(jié)構(gòu)澜薄，它有自己的特點(diǎn)
它是一種線性表为肮，同為線性表的還有之前說到的數(shù)組和鏈表
它操作受限，具體表現(xiàn)在先進(jìn)后出肤京，后進(jìn)先出颊艳，只能在一端進(jìn)行數(shù)據(jù)的插入和刪除
基于以上兩點(diǎn)，大概就能勾勒出棧的模樣忘分。
棧的應(yīng)用
經(jīng)常聽到有很多人抱怨說（也包括我~~~）棋枕，如果知道這門課這么重要，我當(dāng)時(shí)拼死老命也要把它學(xué)好饭庞。
還記得當(dāng)時(shí)看吳恩達(dá)的《machine learning》戒悠，在前幾節(jié)課里展示了如何使用聚類算法進(jìn)行圖像處理，如果使用增強(qiáng)學(xué)習(xí)算法讓一個(gè)模型飛機(jī)飛起來(lái)
那么舟山，我們來(lái)看下棧有什么應(yīng)用
棧在表達(dá)式求值中的應(yīng)用
給出一個(gè)表達(dá)式“3+5*8-6”，如果讓你算卤恳，想必難不倒你累盗。
交給機(jī)器做，肯定也難不倒它突琳，機(jī)器甚至可以做更加復(fù)雜的你做不到的運(yùn)算若债。
但是機(jī)器底層是怎么做的，如果不給定規(guī)則拆融，它并不知道加減乘除是什么蠢琳，也不知道他們的優(yōu)先級(jí)順序。所以镜豹，這時(shí)候棧就排上了用場(chǎng)傲须。
具體做法：
準(zhǔn)備兩個(gè)棧，一個(gè)用來(lái)存儲(chǔ)需要運(yùn)算的數(shù)字趟脂，一個(gè)用來(lái)存儲(chǔ)運(yùn)算符號(hào)泰讽。
數(shù)字棧按照從左到右的順序入棧，符號(hào)棧也是如此昔期，只是除此之外還多了一個(gè)規(guī)則限定已卸。
當(dāng)新入棧的符號(hào)優(yōu)先級(jí)比當(dāng)前棧頂符號(hào)的優(yōu)先級(jí)高的時(shí)候，繼續(xù)入棧硼一；當(dāng)比棧頂符號(hào)優(yōu)先級(jí)低或者相同時(shí)累澡，則取出當(dāng)前棧頂符號(hào)，同時(shí)取出數(shù)字棧的操作數(shù)字進(jìn)行運(yùn)算般贼，將運(yùn)算后的結(jié)果壓棧愧哟，直至兩個(gè)棧元素全部彈出惑申。
具體看專題中給出的過程圖
棧在括號(hào)匹配中的應(yīng)用
給出一串“{(({[{{}}]}))}”，需要校驗(yàn)這串表達(dá)式中是否能前后一一匹配翅雏。
沒錯(cuò)圈驼，這個(gè)也可以利用棧的特性解決。
具體做法：
從左到右掃描表達(dá)式望几，對(duì)于左括號(hào)入棧绩脆，遇到右括號(hào)則取出當(dāng)前棧頂元素，如果發(fā)現(xiàn)匹配橄抹，則取出棧頂元素繼續(xù)匹配靴迫。
當(dāng)所有字符串匹配完成，并且棧最后是空棧楼誓，說明字符串可以正確匹配玉锌。
棧在瀏覽器前進(jìn)后退中的應(yīng)用
在瀏覽器中，我們可以通過前進(jìn)后退回到自己想要的網(wǎng)頁(yè)疟羹。
這個(gè)功能也是可以通過棧來(lái)實(shí)現(xiàn)的主守，具體做法：
準(zhǔn)備兩個(gè)棧，一個(gè)用于存放前進(jìn)棧的網(wǎng)頁(yè)ID榄融，一個(gè)用于存放后退棧的網(wǎng)頁(yè)ID参淫。當(dāng)需要前進(jìn)的時(shí)候，從前進(jìn)棧取出棧頂元素愧杯，并將該元素放入后退棧中涎才；
當(dāng)需要后退的時(shí)候，從后退棧取出棧頂元素力九，并將該元素放入前進(jìn)棧中耍铜。
具體實(shí)現(xiàn)參見項(xiàng)目rome中的BackAndForwardUtil和BackAndForwardUtilDemo類
如何實(shí)現(xiàn)一個(gè)棧
采用鏈表接口實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu)
package com.jackie.algo.geek.time.chapter8_stack;
/**
* @Author: Jackie
*/
public class Stack {
private Node top = null;
/**
* 壓棧
* @see com.jackie.algo.geek.time.chapter6_linkedlist.LinkedList 中的insertToHead方法和這里的push思想類似
*
* |------|
* | node | 上移后的top在這個(gè)位置
* |------|
* | p | 一開始top在這里，經(jīng)過node.next = top綁定了node和p關(guān)系后跌前，又通過top = node棕兼，則將top上移
* |------|
* | ... |
* |------|
*
*/
public void push(int value) {
Node node = new Node(value, null);
if (top == null) {
top = node;
} else {
node.next = top;
top = node;
}
}
/**
* 出棧
*/
public int pop() {
if (top == null) {
return -1;
}
int value = top.value;
top = top.next;
return value;
}
public void printAll() {
Node p = top;
while (p != null) {
System.out.print(p.value + " ");
p = p.next;
}
System.out.println();
}
public static class Node {
private int value;
private Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
}
具體參見項(xiàng)目rome
