棧(Stack)

說實話, 自己在開發的這兩年中, 真的沒怎麼用過堆棧, 隻記得在阿裡面試的時候, 回來查查答案, 應該使用堆棧才能解決他那個題目, 最後我也會把這個題目分享處理啊, 讓大家一起參考.

棧的特點: 棧的最大特點就是後進先出, 對于棧中的資料來說, 所有操作都是在棧的頂部完成的, 隻可以檢視棧頂部的元素, 隻能夠向棧的頂部壓入資料, 也隻能從棧的頂部彈出資料

實作: 利用一個單連結清單來是實作棧的資料結構, 而且, 因為我們都隻針對棧頂元素進行操作, 所有借用單連結清單的頭就能讓所有的操作在O(1)的時間内完成

應用場景: 在解決某些問題的時候, 隻需要關心最近的一次的操作, 并且在操作完成之後, 需要向前查找到更前一次的操作.

如果打算用給一個數組外加一個指針來是吸納相似的效果, 那麼, 一旦數組的長度發生變化, 哪怕隻是在最後添加一個新的元素, 時間複雜度都不在是O(1), 而且, 空間複雜度也得不到變化.

注意: 很多leetcode中等難度偏上的題目裡面經常需要用到的資料結構, 掌握好它是十分必要的.

1. 例題分析一

leetcode 20題:

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

有效字元串需滿足：

左括号必須用相同類型的右括号閉合。左括号必須以正确的順序閉合。注意空字元串可被認為是有效字元串。

示例 1:

輸入: "()"

輸出: true

示例 2:

輸入: "()[]{}"

示例 3:

輸入: "(]"

輸出: false

示例 4:

輸入: "([)]"

示例 5:

輸入: "{[]}"

2. 解題思路

利用一個棧, 不斷的往裡面壓左括号, 一直遇到一個右括号, 我們就得把棧定的左括号彈出來, 表示這是一個合法的組合, 依次類推, 直到最後判斷棧裡還有沒有左括号剩餘

3. 代碼示例

class Solution {
 private HashMap<Character, Character> mappings;
 public Solution() {
   this.mappings = new HashMap<Character, Character>();
   this.mapping.put(')', '(');
   this.mapping.put('}', '{');
   this.mapping.put(']', '[');
}

 public boolean isValid(String s) {
   Stack<Character> stack = new Stack<Character>();
   for (int i = 0; i < s.length(); i++) {
     char c = s.charAt(i);
     // 如果是右括号
     if (this.mappings.containsKey(c)) {
       // 如果stack不為空, 就出棧,
       char topElement = stack.empty() ? '#' : stack.pop();
       if (topElement != this.mapping.get(c)) {
         return false;
      }
     // 左括号, 直接壓入到棧中
    } else {
       stack.push(c);
    }
  }
   return stack.isEmpty();
}
}           

4. 例題分析二

一般遇到括号的問題, 我們都會想到使用棧的資料結構, 下面我來舉也給例子, 就是我原來面試的時候遇到的一個問題, 以為從來都沒有總結過棧的使用,肯定是挂了的, 是以給大家列出來, 大家來看一下吧

計算: 3[a2[sd]]的計算結果為: asdsdasdsdasdsd

其實類似于正規表達式的計算, 括号前面的資料, 代表括号内的字母倍數

分析:

我們也是通過棧的方式來進行計算的, 以上的資料肯定是符合左右括号的标準的, 這個不用去擔心

1. 我們遇到不是"]"的全部入棧
2. 如果遇到"]", 則需要出棧, 把出棧的元素保留下來, 組合成字元串
3. 知道遇到"[", 才算停止進行字元字元串
4. 在"["的前一個元素, 肯定是數字n, 這個應該是有保證的
5. 是以我們把原來組合成的字元串 * n, 得到其中的一個子串
6. 如果字元串結束, 輸出結果, 如果字元串沒有結束, 我們把子串在進行入棧,
7. 然後在接着進行循環1-6,直到傳回結果

public class Solution{
   public String getAllResult(String s) {
       if (s == null || s.length() == 0) {
           return "";
      }
       Stack<String> stack = new Stack<String>();
       for(int i = 0; i < s.length(); i++) {
           if ("]".equals(String.valueOf(s.charAt(i)))) {
               String temp = "";
               while(!stack.empty()){
                   String item = stack.pop();
                   if ("[".equals(stack.pop())) {
                       // 如果遇到"[", 那就相當于子字元串相加完成了, 我們需要擷取到"["前面的數字
                       Integer count = Integer.valueOf(stack.pop());
                       for (int j = 0; j < count; j++) {
                           // 字元串疊加count遍
                           temp += temp;
                      }
                       // 還需要把算出來的子字元串重新放入棧中, 然後跳出, 在進行字元串的判斷, 就是分析裡面所說的第6步
                       stack.push(temp);
                       break;
                  }else {
                       // 字元串相加的時候, 應該是出棧的永遠在後面
                       temp = item + temp;
                  }
              }

          } else {
               // 如果不是"]", 我們直接存放在棧中, 隻有當存放的是"]"的時候, 這個時候才進行計算
               stack.push(String.valueOf(s.charAt(i)));
          }
      }
       // 最後所有的子字元串都合并成一個大的字元串, 直接進行pop, 就可以得到最終的結果
       return stack.pop();
  }
}