20. 有效的括號(hào)
題目鏈接：https://leetcode.cn/problems/valid-parentheses/
解答： https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
有效字符串需滿足：
1. 左括號(hào)必須用相同類型的右括號(hào)閉合。
2. 左括號(hào)必須以正確的順序閉合。
3. 注意空字符串可被認(rèn)為是有效字符串。
return false 的情況：
第一種情況：已經(jīng)遍歷完了字符串，但是棧不為空，說明有相應(yīng)的左括號(hào)沒有右括號(hào)來匹配，所以return false
第二種情況：遍歷字符串匹配的過程中，發(fā)現(xiàn)棧里沒有要匹配的字符。所以return false
第三種情況：遍歷字符串匹配的過程中，棧已經(jīng)為空了，沒有匹配的字符了，說明右括號(hào)沒有找到對(duì)應(yīng)的左括號(hào)return false
return true的情況：
字符串遍歷完之后，棧是空的，就說明全都匹配了。
http://www.itdecent.cn/p/ae28d514003c
由于歷史原因，在Java中，官方不建議使用Stack類，而是使用Deque代替，也就是說，接口Deque是棧和雙端隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的集合體。
關(guān)于LinkedList/Dequue中的添加和刪除操作：
· add 和 remove 是一對(duì)，源自Collection，所以添加到隊(duì)尾，從隊(duì)頭刪除；
· offer 和 poll是一對(duì)，源自Queue，（先進(jìn)先出 => 尾進(jìn)頭出），所以添加到隊(duì)尾，從隊(duì)頭刪除；
· push 和 pop是一對(duì)，源自Deque，其本質(zhì)是棧，先進(jìn)后出 => 頭進(jìn)頭出），所以添加到隊(duì)頭，從隊(duì)頭刪除；
· offerFisrt/offerLast 和 pollFirst/pollLast是一對(duì)，源自Deque，其本質(zhì)是雙端隊(duì)列，offerFirst添加到隊(duì)頭，offerLast添加到隊(duì)尾，pollFirst從隊(duì)頭刪除，pollLast從隊(duì)尾刪除；
1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)
題目鏈接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
我們?cè)趧h除相鄰重復(fù)項(xiàng)的時(shí)候，其實(shí)就是要知道當(dāng)前遍歷的這個(gè)元素，我們?cè)谇耙晃皇遣皇潜闅v過一樣數(shù)值的元素，那么如何記錄前面遍歷過的元素呢？
所以就是用棧來存放，那么棧的目的，就是存放遍歷過的元素，當(dāng)遍歷當(dāng)前的這個(gè)元素的時(shí)候，去棧里看一下我們是不是遍歷過相同數(shù)值的相鄰元素。
注意??：
1. ArrayDeque會(huì)比LinkedList在除了刪除元素這一點(diǎn)外會(huì)快一點(diǎn)
參考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character>deque=new ArrayDeque<>();
2. 最后所有字符出棧的時(shí)候，是按照從后往前的順序出棧的
str=deque.pop()+str; // String str;
sb.reverse(); // StringBuffer sb;
150. 逆波蘭表達(dá)式求值
題目鏈接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
逆波蘭表達(dá)式：是一種后綴表達(dá)式，所謂后綴就是指運(yùn)算符寫在后面。
逆波蘭表達(dá)式主要有以下兩個(gè)優(yōu)點(diǎn)：
1、去掉括號(hào)后表達(dá)式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據(jù)次序計(jì)算出正確結(jié)果。
2、適合用棧操作運(yùn)算：遇到數(shù)字則入棧；遇到運(yùn)算符則取出棧頂兩個(gè)數(shù)字進(jìn)行計(jì)算，并將結(jié)果壓入棧中。
遞歸就是用棧來實(shí)現(xiàn)的：所以棧與遞歸之間在某種程度上是可以轉(zhuǎn)換的！?這一點(diǎn)我們?cè)诤罄m(xù)講解二叉樹的時(shí)候，會(huì)更詳細(xì)的講解到。那么來看一下本題，其實(shí)逆波蘭表達(dá)式相當(dāng)于是二叉樹中的后序遍歷。 大家可以把運(yùn)算符作為中間節(jié)點(diǎn)，按照后序遍歷的規(guī)則畫出一個(gè)二叉樹。
中綴表達(dá)式對(duì)于計(jì)算機(jī)來說不友好，二后綴表達(dá)式計(jì)算機(jī)可以利用棧來順序處理，不需要考慮優(yōu)先級(jí)了。也不用回退了，?所以后綴表達(dá)式對(duì)計(jì)算機(jī)來說是非常友好的。
注意??：除法和減法的兩個(gè)運(yùn)算數(shù)是有先后順序的
除法：
int temp1=stack.pop();
int temp2=stack.pop();
stack.push(temp2/temp1);
