https://developer.51cto.com/art/202103/647812.htm

前言

說完了連結串列，我們再看看棧。

理解棧

棧是什麼，很金典的比喻就是把 棧 比喻成疊盤子，一個個疊上去，然後拿的時候會先拿最上面的，也就是最後疊上去的那個。

先進者後出、後進者先出，這就是棧結構。

實際應用

那麼棧在實際應用中有什麼場景呢?

可太多了，比如Activity中的任務棧，編譯器實現方法表示式，瀏覽器的前進後退。

這裡拿瀏覽器的前進後退做例子。

在瀏覽器中，每開啟一個頁面，就把這個頁面入棧，然後點選後退的時候就將頁面出棧。這是不是挺像Activity頁面的任務棧的。如果有前進功能，那麼就再需要一個棧，當點選後退的時候，就把頁面從A棧出，然後進入B棧，這樣點選前進的時候，就能從B棧重新回到A棧了。

1)瀏覽網頁，每開啟一個網頁就入棧A。比如這裡打開了網頁M和網頁N。

Java中的棧類

在Java中，棧的對應類為Stack。

//初始化棧 Stack<String> stack =new Stack<String>(); //入棧 stack.push("test"); //出棧，返回出棧的元素 String str=stack.pop();

演算法題

還是老樣子，來一題棧相關的演算法題。

題目

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效。

有效字串需滿足：

左括號必須用相同型別的右括號閉合。左括號必須以正確的順序閉合。

示例 1：輸入：s = "()" 輸出：true

示例 2：輸入：s = "()[]{}" 輸出：true

示例 4：輸入：s = "([)]" 輸出：false

示例 5：輸入：s = "{[]}" 輸出：true

解法

解法就是利用棧了。

遇到左括號入棧，遇到右括號就把相應的左括號出棧，如果右括號和要出棧的這個元素不一致，就說明括號沒有成對。

關於左括號和右括號的對應關係，可以用HashMap來儲存，來一起看看：

public boolean isValid(String s) {         int n = s.length();         if (n % 2 == 1) {             return false;         }          Map<Character, Character> pairs = new HashMap<Character, Character>() {{             put(')', '(');             put(']', '[');             put('}', '{');         }};         Deque<Character> stack = new LinkedList<Character>();         for (int i = 0; i < n; i++) {             char ch = s.charAt(i);             if (pairs.containsKey(ch)) {                 if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {                     return false;                 }                 stack.pop();             } else {                 stack.push(ch);             }         }         return stack.isEmpty();     } 

也有比較靈活的辦法，就是入棧的時候就確定好括號的對應關係，直接入棧左括號對應的右括號。

public boolean isValid(String s) {         if(s.isEmpty())             return true;         Stack<Character> stack=new Stack<Character>();         for(char c:s.toCharArray()){             if(c=='(')                 stack.push(')');             else if(c=='{')                 stack.push('}');             else if(c=='[')                 stack.push(']');             else if(stack.empty()||c!=stack.pop())                 return false;         }         if(stack.empty())             return true;         return false;     } 

時間複雜度

需要遍歷字串，所以時間複雜度為 O(n)

空間複雜度

棧的字元數量最大為n，Map數量為3，所以空間複雜度就是O(n)

參考

https://time.geekbang.org/column/article/41222