[[384434]]

前言

說完了鏈表，我們再看看棧。

理解棧

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

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

實際應用

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

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

這里拿瀏覽器的前進后退做例子。

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

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

2)點擊后退，網頁N出棧A，入棧B。

3)點擊前進，網頁N出棧B，入棧A。

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

本文轉載自微信公眾號「碼上積木」，可以通過以下二維碼關注。轉載本文請聯系碼上積木公眾號。