- 用數(shù)組實(shí)現(xiàn)的棧，叫做 順序棧：
- 順序棧的實(shí)現(xiàn)非常簡單，這里就不寫代碼了，寫一下思路。先初始化一個數(shù)組，然后再用一個變量給這個數(shù)組里的元素進(jìn)行計(jì)數(shù)，當(dāng)有新元素需要入棧的時候，將這個新元素寫入到數(shù)組的最后一個元素的后面，然后計(jì)數(shù)器加一。當(dāng)需要做出棧操作時，將數(shù)組中最后一個元素返回，計(jì)數(shù)器減一。
- 當(dāng)然在入棧前需要判斷數(shù)組是否已經(jīng)滿了，如果數(shù)組大小等于計(jì)數(shù)器大小，則表明數(shù)組是滿的。
- 出棧的時候也需要判斷數(shù)組是不是空數(shù)組，如果計(jì)數(shù)器是0，則表明數(shù)組是空的。
- 從上面的實(shí)現(xiàn)流程可以看出，通過數(shù)組實(shí)現(xiàn)的棧，其入棧和出棧都是對單個元素進(jìn)行操作，因此其入棧和出棧的時間復(fù)雜度都是O(1)，并且其入棧和出棧操作并沒有額外開銷更多空間，因此其空間復(fù)雜度也是O(1)的。
- 用鏈表實(shí)現(xiàn)的棧，叫做 鏈?zhǔn)綏?/strong>：
- 實(shí)現(xiàn)思路是先定義一個鏈表節(jié)點(diǎn)的類，基于這個類去定義一個頭節(jié)點(diǎn)Head。當(dāng)有新元素需要入棧的時候，將這個新元素的Next指針指向頭結(jié)點(diǎn)Head的Next節(jié)點(diǎn)，然后再將Head的Next指向這個新節(jié)點(diǎn)。當(dāng)需要做出棧操作時，直接將Head所指向的節(jié)點(diǎn)返回，同時讓Head指向下一個節(jié)點(diǎn)。
- 當(dāng)然，在入棧和出棧時都需要判斷鏈表是否為空的情況。
- 鏈?zhǔn)綏５娜霔：统鰲６际窃谔幚眍^部節(jié)點(diǎn)，所以操作很簡單，其時間和空間復(fù)雜度均為O(1)。
算法題：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
舉例：字符串 "()"有效、"()[]{}"有效、"(]"無效、"([)]"無效、"{[]}"有效。
解題思路：
使用1個堆棧即可解決，依次遍歷這個字符串，如果遇到是左括號就入棧到堆棧中，如果遇到的是右括號，則從堆棧中取出棧頂?shù)牡谝粋€左括號，比對一下這個左括號和當(dāng)前遇到的右括號是否匹配，如果不匹配這認(rèn)為這整個字符串無效。如果能匹配，則OK，刪除這個左括號和右括號，繼續(xù)往后走，繼續(xù)遍歷字符串中剩下的字符，只要遇到左括號就入棧，只要遇到右括號就與將棧頂?shù)淖罄ㄌ柍鰲Ｅc之比較。一直走到字符串結(jié)束，再來檢查堆棧中是否還有元素，如果還有元素，則這個字符串同樣無效，如果堆棧為空，則字符串有效。
就以這個思路實(shí)現(xiàn)一個初版代碼：
class Solution {
public boolean isValid(String s) {
Stack<Character> satck = new Stack<Character>();
for(int i=0; i<s.length();i++){
char c = s.charAt(i);
if(c=='(' || c=='{' || c=='['){
satck.push(c);
}else{
if(satck.isEmpty()) return false;
char temp = satck.pop();
if( (temp=='('&&c==')') || (temp=='{'&&c=='}') || (temp=='['&&c==']') ){
continue;
}else{
return false;
}
}
}
return satck.isEmpty();
}
}
這個代碼的時間復(fù)雜度o(n),空間復(fù)雜度o(n)搞定。
但是想了想，好像代碼不是很優(yōu)雅，寫了一個優(yōu)化版，提前將左右括號放入到MAP中，這個方法的時間和空間復(fù)雜度跟上面的一樣。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
HashMap<Character,Character> map = new HashMap<Character,Character>();
map.put('(', ')');
map.put('{','}' );
map.put('[', ']');
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c)){
stack.push(c);
}else{
if(stack.isEmpty()) return false;
char temp = stack.pop();
if(map.get(temp)!=c) return false;
}
}
return stack.isEmpty();
}
}
繼續(xù)思考有沒有更簡潔的方法，竟然在leetcode上找到了一個：
但是這個方法并沒有用到堆棧哦，它的思路是不斷的遍歷這個字符串，將字符串中的(){}[]全部調(diào)換成空字符串，如果最后全部替換完成了，并且字符串為空了，就說明字符串是有效的，否者就是無效的字符串。
class Solution {
public boolean isValid(String s) {
int length = s.length();
do{
length = s.length();
s = s.replaceAll("\\(\\)","").replaceAll("\\{\\}","").replaceAll("\\[\\]","");
}while(s.length()!=length);
return s.length()==0;
}
}
不過這個方法的時間復(fù)雜度要高一些。
以上，就是對數(shù)據(jù)結(jié)構(gòu)中「 堆棧 」的一些思考。
碼字不易啊，喜歡的話不妨轉(zhuǎn)發(fā)朋友，或點(diǎn)擊文章右下角的“在看”吧。
本文原創(chuàng)發(fā)布于微信公眾號「 不止思考 」，歡迎關(guān)注。涉及 思維認(rèn)知、個人成長、架構(gòu)、大數(shù)據(jù)、Web技術(shù) 等。
聲明：本文由網(wǎng)站用戶香香發(fā)表，超夢電商平臺僅提供信息存儲服務(wù)，版權(quán)歸原作者所有。若發(fā)現(xiàn)本站文章存在版權(quán)問題，如發(fā)現(xiàn)文章、圖片等侵權(quán)行為，請聯(lián)系我們刪除。
