本文是在閱讀《算法》第四版時的筆記温亲。
棧
棧數(shù)據(jù)結(jié)構(gòu)遵循 LIFO( last in first out ) 的原則菇怀。
它主要有壓棧和彈棧這兩種操作以及 isEmpty() 和 size() 函數(shù)快鱼。
LIFO
關(guān)于 LIFO 原則麻献，有一個很好的例子：假如你有一堆郵件在桌子上（這堆郵件就是一個棧結(jié)構(gòu)），有新郵件的時候世落，你會把新郵件放在這一堆郵件的最上面，這個操作就是壓棧糟需，新郵件總是處于棧頂屉佳，而你要處理這些郵件的時候，會從最上面的開始讀洲押，也就是從棧頂開始一封一封的讀武花，讀過的郵件，就從這堆郵件里面拿出來杈帐，這就是彈棧髓堪，彈棧總是對棧頂?shù)臄?shù)據(jù)進行操作娘荡。
Java實現(xiàn)一個簡單的棧結(jié)構(gòu)
書上目前沒看見關(guān)于 Stack 具體實現(xiàn)的代碼干旁，所以我也是只基于數(shù)組實現(xiàn)了 Stack 的基本功能，有不對的地方炮沐，請指正争群，謝謝！４竽辍换薄！
這里主要是實現(xiàn)四個方法：
-
Stack()定義一個棧 -
push(T t)壓棧 -
pop()彈棧 -
isEmpty()判斷棧是否為空 -
size()返回棧內(nèi)數(shù)據(jù)個數(shù)
public class Stack<T> implements Iterable<T> {
@Override
public Iterator<T> iterator() {
return null;
}
private ArrayList<T> array = new ArrayList<T>();
public Stack(){
}
public void push(T t){
this.array.add(t);
}
public T pop(){
return this.array.remove(array.size()-1);
}
public boolean isEmpty(){
return this.array==null;
}
public int size(){
return this.array.size();
}
}
棧的運用
引用《算法》第四版里的例子。
先看一個數(shù)學(xué)表達式：
( 1 + ( 2 + 3 ) * ( 4 * 5 ) ) )
這個數(shù)學(xué)表達式翔试，學(xué)過小學(xué)數(shù)學(xué)的都知道計算結(jié)果是 101 轻要。
我們把上面的表達式輸入到計算機里面，輸入的是字符串垦缅，要怎樣處理冲泥，它才能得出 101 這個結(jié)果呢？
上世紀(jì) 70 年代壁涎，E.W.Dijkstra 運用兩個棧結(jié)構(gòu)解決了這個問題凡恍，一個棧 ( ops ) 用來保存操作符（+，-怔球，*嚼酝，/，sqrt ）竟坛，一個棧 ( vals ) 用來保存操作數(shù)（數(shù)字）闽巩，同時還得遵循下面這幾種原則：
- 輸入表達式的時候钧舌，操作數(shù)和操作符要用一個空格隔開。
- 忽略左括號
- 遇見右括號涎跨，棧 ops 彈出一個操作符延刘，棧 vals 彈出必要的操作數(shù)，然后將計算結(jié)果再壓棧操作壓入棧 vals 六敬。
看著有點玄幻碘赖，本人還買的英文版，對英語沒過四級的我來說就更玄幻了外构，不急普泡，看代碼。
public class Evalution {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty()) {
String s = StdIn.readString();
if (s.equals("("));
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")")) {
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
首先审编，你會發(fā)現(xiàn)在 while 循環(huán)的條件里面亂入了一個 StdIn 撼班，別慌，這是《算法》作者自己封裝的一個工具類垒酬，這本書里面還用到其他的一些作者自己封裝的工具類砰嘁，在這里 (https://introcs.cs.princeton.edu/java/stdlib/) 可以下載到。
接下來勘究，emmm...矮湘，while 循環(huán)的判斷語句這里有點問題，因為這段代碼運行下來口糕，輸入上面的數(shù)學(xué)表達式之后缅阳，會死循環(huán)，很驚喜景描，很意外十办，反正網(wǎng)上說是停止符 EOF 這些的問題，可是我是來學(xué)算法的超棺，這些問題不管向族，有網(wǎng)友說輸入上面的數(shù)學(xué)表達式之后回車，然后 Ctrl + D 就可以了棠绘，試了一下件相，行得通。弄唧。适肠。
代碼邏輯分析
好了終于到了最重要的環(huán)節(jié)，來分析一下這段代碼的邏輯吧候引，搞懂了其實挺簡單的，然而我花了一些時間才搞懂敦跌。澄干。逛揩。。
嗯麸俘，每一次循環(huán)辩稽，都會讀取一個操作數(shù)或者操作符，這里可能會問 sqrt 怎么處理的(其實是我自己問的)从媚，在上面就說過逞泄，操作數(shù)和操作符，用空格隔開拜效，這樣才不會出錯喷众，其實也是因為 Scanner 類的邏輯，這里不討論紧憾。
讀取到一個操作符到千，就是一層層的 if...else if..else... 判斷了，如果是左括號就跳過本次循環(huán)赴穗，執(zhí)行下一次循環(huán)憔四，如果是其他的操作符（比如 + ，- ）般眉，就將操作符壓入棧 ops 了赵，如果不是操作符，而是操作數(shù)甸赃，就壓入棧 vals 斟览。
上的各種壓棧理清楚了，是不是發(fā)現(xiàn)當(dāng)遇見右括號的時候辑奈，畫風(fēng)就變了苛茂，是的，這是最重要的一步（個人認(rèn)為）鸠窗，因為妓羊，這里就是進行計算的邏輯，嗯稍计，到這里建議再看看前面實現(xiàn) Stack 的彈棧和壓棧的代碼邏輯躁绸。
這一步可能圖解更好，但是書上的圖拍下來不清晰臣嚣，有時間畫了再補上來净刮。開始分析之前，再把數(shù)學(xué)表達式搬過來：
( 1 + ( 2 + 3 ) * ( 4 * 5 ) ) )
就拿遇見的第一個右括號舉例硅则，此時淹父，棧 ops 里面有兩個元素（ +，+ ）怎虫，棧 vals 里面有三個元素（ 1暑认，2困介，3 ），遇見右括號蘸际，ops 彈棧座哩，拿到棧頂元素操作符 + ，然后 vals 彈棧粮彤，拿到棧頂操作數(shù) 3 根穷，此時兩個棧都經(jīng)過了一次彈棧， ops 和 vals 的棧頂元素分別是 + 和 2 导坟，再看代碼屿良，又是一串 if 判斷語句，并且是利用 ops 的彈棧彈出的元素做判斷條件乍迄，而 操作數(shù)棧管引，又得彈棧一次，此時 vals 經(jīng)歷了兩次彈棧闯两，彈出的數(shù)據(jù)分別是 3 和 2褥伴，然后這兩個數(shù)據(jù)進行相應(yīng)的算數(shù)操作，再將兩個數(shù)算數(shù)操作后得出的結(jié)果壓入棧 vals 漾狼，這個時候就相當(dāng)于是 2 + 3 這一段現(xiàn)在用 5 代替重慢。
隨著 while 的再次循環(huán)，再遇見右括號逊躁，還是進行相同的彈棧壓棧操作似踱，最后棧 ops 為空，棧 vals 里面只有一個數(shù)稽煤，這個數(shù)就是最后的計算結(jié)果核芽，這個數(shù)學(xué)表達式，就成功的得出了結(jié)果酵熙。
思考
經(jīng)過上面的不專業(yè)的瞎BB轧简，我發(fā)現(xiàn)這段代碼好像只適合小括號里面只有兩個操作數(shù)的情況，要是把 ( 2 + 3 ) 改成 ( 2 + 3 +6 )匾二，得到的結(jié)果是 182.0 哮独，而不是 221 ，那么察藐，要怎么改善一下皮璧，才能避免這種情況呢，我也是寫到這里才想起來這個問題分飞，沒有代碼實現(xiàn)悴务，說說我現(xiàn)在的想法，我覺得不忽略左括號浸须，將左括號壓入 ops 棧惨寿，然后遇見右括號的時候邦泄，ops 就的彈棧直到遇見右括號删窒，這只是個大概的思路裂垦。。肌索。蕉拢。
