作者：獅子也瘋狂
專欄：《算法詳解》
愿你生如夏花之絢爛，幸運永遠(yuǎn)與你相伴，瘋狂常在。

一. 🦁 Stack容器的來歷

Stack 棧容器是 Vector 的一個子類，它實現(xiàn)了一個標(biāo)準(zhǔn)的后進(jìn)先出(LIFO：Last In Frist Out)的棧。它通過 5 個操作方法對 Vector 進(jìn)行擴展，允許將向量視為堆棧。

1.1 操作棧的方法

Modifier and Type	Method and Description
boolean	enpty() :判斷該棧是否為空
E	peek(): 查看棧頂元素
E	pop(): 刪除棧頂元素，并返回該值
E	push(E item):將元素推入棧頂
int	search(object o) : 返回該元素的位置

二. 🦁 Stack的使用

這里以力扣第20題為實戰(zhàn)案例：查看

2.1 題目

給定一個只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應(yīng)的相同類型的左括號

2.2 分析

這一道題明顯是可以使用棧的結(jié)構(gòu)來做，實例化一個棧（Stack< String >）,對字符串做一次循環(huán)遍歷，在遍歷過程中，遇到左括號（無論是什么左括號（{ （ [），都將其對應(yīng)的右括號放進(jìn)stack容器中；如果遇到右括號c，則會從stack頂中彈出一個棧頂元素x，將x與c比較，使用flag這一布爾值（默認(rèn)為true，即匹配）來判斷是否匹配，如果不匹配則修改flag為false。到最后遍歷結(jié)束，如果stack ——>!empty(),則也修改flag為false，最后返回flag。
注意到有效字符串的長度一定為偶數(shù)，因此如果字符串的長度為奇數(shù)，我們可以直接返回 False，省去后續(xù)的遍歷判斷過程。

2.3 詳細(xì)算法實現(xiàn)

class Solution {public boolean isValid(String s) {Stack<String> stack = new Stack<>();boolean flag = true;for(int i = 0;i<s.length();i++){char str = s.charAt(i);if(str == '('){stack.push(")");}if(str == '['){stack.push("]");}if(str == '{'){stack.push("}");}if(str == ')'||str == ']'||str == '}'){if(stack.empty()){return false;}String c = stack.pop();if(c.charAt(0) != str){flag = false;break;}}}if(!stack.empty()){flag = false;}return flag;}
}

2.4 力扣AC截圖

三. 🦁 總結(jié)

Leetcode的一道難度為簡單的算法題，可以幫助大家很好的理解Stack這個數(shù)據(jù)結(jié)構(gòu)，希望大家喜歡。更多專欄請點擊

專欄	名字
🔥Elasticsearch專欄	es
🔥spring專欄	spring開發(fā)
redis專欄	redis學(xué)習(xí)筆記
🔥項目專欄	項目集錦
修bug專欄	bug修理廠