- 用數組實現的棧，叫做 順序棧：
- 順序棧的實現非常簡單，這里就不寫代碼了，寫一下思路。先初始化一個數組，然后再用一個變量給這個數組里的元素進行計數，當有新元素需要入棧的時候，將這個新元素寫入到數組的最后一個元素的后面，然后計數器加一。當需要做出棧操作時，將數組中最后一個元素返回，計數器減一。
- 當然在入棧前需要判斷數組是否已經滿了，如果數組大小等于計數器大小，則表明數組是滿的。
- 出棧的時候也需要判斷數組是不是空數組，如果計數器是0，則表明數組是空的。
- 從上面的實現流程可以看出，通過數組實現的棧，其入棧和出棧都是對單個元素進行操作，因此其入棧和出棧的時間復雜度都是O(1)，并且其入棧和出棧操作并沒有額外開銷更多空間，因此其空間復雜度也是O(1)的。
- 用鏈表實現的棧，叫做 鏈式棧：
- 實現思路是先定義一個鏈表節點的類，基于這個類去定義一個頭節點Head。當有新元素需要入棧的時候，將這個新元素的Next指針指向頭結點Head的Next節點，然后再將Head的Next指向這個新節點。當需要做出棧操作時，直接將Head所指向的節點返回，同時讓Head指向下一個節點。
- 當然，在入棧和出棧時都需要判斷鏈表是否為空的情況。
- 鏈式棧的入棧和出棧都是在處理頭部節點，所以操作很簡單，其時間和空間復雜度均為O(1)。
算法題：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
舉例：字符串 "()"有效、"()[]{}"有效、"(]"無效、"([)]"無效、"{[]}"有效。
解題思路：
使用1個堆棧即可解決，依次遍歷這個字符串，如果遇到是左括號就入棧到堆棧中，如果遇到的是右括號，則從堆棧中取出棧頂的第一個左括號，比對一下這個左括號和當前遇到的右括號是否匹配，如果不匹配這認為這整個字符串無效。如果能匹配，則OK，刪除這個左括號和右括號，繼續往后走，繼續遍歷字符串中剩下的字符，只要遇到左括號就入棧，只要遇到右括號就與將棧頂的左括號出棧與之比較。一直走到字符串結束，再來檢查堆棧中是否還有元素，如果還有元素，則這個字符串同樣無效，如果堆棧為空，則字符串有效。
就以這個思路實現一個初版代碼：
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();
}
}
這個代碼的時間復雜度o(n),空間復雜度o(n)搞定。
但是想了想，好像代碼不是很優雅，寫了一個優化版，提前將左右括號放入到MAP中，這個方法的時間和空間復雜度跟上面的一樣。
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();
}
}
繼續思考有沒有更簡潔的方法，竟然在leetcode上找到了一個：
但是這個方法并沒有用到堆棧哦，它的思路是不斷的遍歷這個字符串，將字符串中的(){}[]全部調換成空字符串，如果最后全部替換完成了，并且字符串為空了，就說明字符串是有效的，否者就是無效的字符串。
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;
}
}
不過這個方法的時間復雜度要高一些。
以上，就是對數據結構中「 堆棧 」的一些思考。
碼字不易啊，喜歡的話不妨轉發朋友，或點擊文章右下角的“在看”吧。
本文原創發布于微信公眾號「 不止思考 」，歡迎關注。涉及 思維認知、個人成長、架構、大數據、Web技術 等。
聲明：本文由網站用戶香香發表，超夢電商平臺僅提供信息存儲服務，版權歸原作者所有。若發現本站文章存在版權問題，如發現文章、圖片等侵權行為，請聯系我們刪除。
