栈(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();
  }
}