? ? ? ?戳藍(lán)字“CSDN云計算”關(guān)注我們哦！

今天咱們再來繼續(xù)看看「 堆棧 」吧，我寫技術(shù)文章很少 show code，所以經(jīng)常有人吐槽。好吧，這個算法系列的文章我打算每一篇的結(jié)尾處都找一道算法題寫出代碼示例，這總可以了吧。

一、「 堆棧 」是什么？

堆棧（stack）是一種先進(jìn)后出的、操作受限的線性表，也可以直接稱為棧。

可以把棧想象成一個桶一樣，往這個桶里面一層一層的放東西，先放進(jìn)去的在里面，后放進(jìn)去的東西依次在外面。但取東西的時候就是先取靠近外面的，再依次一層層取里面的。這就是 后進(jìn)先出（ Last In-First Out ）的原則。

因此「 棧 」雖然是線性的，有2個端：頂端和底端，但它只允許從一端進(jìn)行插入和刪除數(shù)據(jù)，這就是為啥前面說「 棧 」是操作受限的了。

棧只有兩種操作：Push 和 Pop 。我們用Push（壓入）來表示往棧中插入數(shù)據(jù)，也叫入棧，用Pop（彈出）來表示從棧中刪除數(shù)據(jù)，也叫出棧。我們可以既可以用 「 數(shù)組 」 來實現(xiàn)一個棧，也可以用 「 鏈表 」 來實現(xiàn)一個棧。

用數(shù)組實現(xiàn)的棧，叫做順序棧：順序棧的實現(xiàn)非常簡單，這里就不寫代碼了，寫一下思路。先初始化一個數(shù)組，然后再用一個變量給這個數(shù)組里的元素進(jìn)行計數(shù)，當(dāng)有新元素需要入棧的時候，將這個新元素寫入到數(shù)組的最后一個元素的后面，然后計數(shù)器加一。當(dāng)需要做出棧操作時，將數(shù)組中最后一個元素返回，計數(shù)器減一。

當(dāng)然在入棧前需要判斷數(shù)組是否已經(jīng)滿了，如果數(shù)組大小等于計數(shù)器大小，則表明數(shù)組是滿的。

出棧的時候也需要判斷數(shù)組是不是空數(shù)組，如果計數(shù)器是0，則表明數(shù)組是空的。

從上面的實現(xiàn)流程可以看出，通過數(shù)組實現(xiàn)的棧，其入棧和出棧都是對單個元素進(jìn)行操作，因此其入棧和出棧的時間復(fù)雜度都是O(1)，并且其入棧和出棧操作并沒有額外開銷更多空間，因此其空間復(fù)雜度也是O(1)的。

用鏈表實現(xiàn)的棧，叫做鏈?zhǔn)綏?#xff1a;實現(xiàn)思路是先定義一個鏈表節(jié)點的類，基于這個類去定義一個頭節(jié)點Head。當(dāng)有新元素需要入棧的時候，將這個新元素的Next指針指向頭結(jié)點Head的Next節(jié)點，然后再將Head的Next指向這個新節(jié)點。當(dāng)需要做出棧操作時，直接將Head所指向的節(jié)點返回，同時讓Head指向下一個節(jié)點。當(dāng)然，在入棧和出棧時都需要判斷鏈表是否為空的情況。鏈?zhǔn)綏５娜霔：统鰲６际窃谔幚眍^部節(jié)點，所以操作很簡單，其時間和空間復(fù)雜度均為O(1)。

二、「 堆棧 」的算法實踐？

我們來看一個基于用 棧 來完成的 算法題（來源leetcode）： 算法題：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。 有效字符串需滿足： 左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。 舉例：字符串 "()"有效、"()[]{}"有效、"(]"無效、"([)]"無效、"{[]}"有效。 解題思路： 使用1個堆棧即可解決，依次遍歷這個字符串，如果遇到是左括號就入棧到堆棧中，如果遇到的是右括號，則從堆棧中取出棧頂?shù)牡谝粋€左括號，比對一下這個左括號和當(dāng)前遇到的右括號是否匹配，如果不匹配這認(rèn)為這整個字符串無效。如果能匹配，則OK，刪除這個左括號和右括號，繼續(xù)往后走，繼續(xù)遍歷字符串中剩下的字符，只要遇到左括號就入棧，只要遇到右括號就與將棧頂?shù)淖罄ㄌ柍鰲Ｅc之比較。一直走到字符串結(jié)束，再來檢查堆棧中是否還有元素，如果還有元素，則這個字符串同樣無效，如果堆棧為空，則字符串有效。 就以這個思路實現(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; } }

以上，就是對數(shù)據(jù)結(jié)構(gòu)中「 堆棧 」的一些思考。

?

福利

掃描添加小編微信，備注“姓名+公司職位”，加入【云計算學(xué)習(xí)交流群】，和志同道合的朋友們共同打卡學(xué)習(xí)！

推薦閱讀：

• 記一道字節(jié)跳動的算法面試題

• AI ProCon圓滿落幕，五大技術(shù)專場精彩瞬間不容錯過

• 開源sk-dist，超參數(shù)調(diào)優(yōu)僅需3.4秒，sk-learn訓(xùn)練速度提升100倍

• 拯救 CPU！

• 馬化騰、張一鳴……大佬真實朋友圈，竟然藏著這些秘密

• 揭秘沃爾瑪、騰訊、京東、浙商銀行的供應(yīng)鏈管理方案

真香，朕在看了！

總結(jié)

以上是生活随笔為你收集整理的算法一看就懂之「 堆栈 」的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。