上一篇咱們聊完了數據結構中最基礎的「 數組 」和「 鏈表 」，今天咱們再來繼續看看「 堆棧 」吧，我寫技術文章很少 show code，所以經常有人吐槽。好吧，這個算法系列的文章我打算每一篇的結尾處都找一道算法題寫出代碼示例，這總可以了吧。
一、「 堆棧 」是什么？
堆棧（stack）是一種先進后出的、操作受限的線性表，也可以直接稱為 棧。
可以把棧想象成一個桶一樣，往這個桶里面一層一層的放東西，先放進去的在里面，后放進去的東西依次在外面。但取東西的時候就是先取靠近外面的，再依次一層層取里面的。這就是 后進先出（ Last In-First Out ）的原則。
因此「 棧 」雖然是線性的，有2個端：頂端和底端，但它只允許從一端進行插入和刪除數據，這就是為啥前面說「 棧 」是操作受限的了。
棧只有兩種操作：Push 和 Pop 。我們用Push（壓入）來表示往棧中插入數據，也叫入棧，用Pop（彈出）來表示從棧中刪除數據，也叫出棧。我們可以既可以用 「 數組 」 來實現一個棧，也可以用 「 鏈表 」 來實現一個棧。
- 用數組實現的棧，叫做 順序棧：
- 順序棧的實現非常簡單，這里就不寫代碼了，寫一下思路。先初始化一個數組，然后再用一個變量給這個數組里的元素進行計數，當有新元素需要入棧的時候，將這個新元素寫入到數組的最后一個元素的后面，然后計數器加一。當需要做出棧操作時，將數組中最后一個元素返回，計數器減一。
- 當然在入棧前需要判斷數組是否已經滿了，如果數組大小等于計數器大小，則表明數組是滿的。
- 出棧的時候也需要判斷數組是不是空數組，如果計數器是0，則表明數組是空的。
- 從上面的實現流程可以看出，通過數組實現的棧，其入棧和出棧都是對單個元素進行操作，因此其入棧和出棧的時間復雜度都是O(1)，并且其入棧和出棧操作并沒有額外開銷更多空間，因此其空間復雜度也是O(1)的。
- 用鏈表實現的棧，叫做 鏈式棧：
- 實現思路是先定義一個鏈表節點的類，基于這個類去定義一個頭節點Head。當有新元素需要入棧的時候，將這個新元素的Next指針指向頭結點Head的Next節點，然后再將Head的Next指向這個新節點。當需要做出棧操作時，直接將Head所指向的節點返回，同時讓Head指向下一個節點。
- 當然，在入棧和出棧時都需要判斷鏈表是否為空的情況。
- 鏈式棧的入棧和出棧都是在處理頭部節點，所以操作很簡單，其時間和空間復雜度均為O(1)。
二、「 堆棧 」的算法實踐？
我們來看一個基于用 棧 來完成的 算法題（來源leetcode）：
算法題：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
舉例：字符串 "()"有效、"()[]{}"有效、"(]"無效、"([)]"無效、"{[]}"有效。
解題思路：
使用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技術 等。
