一学一记:栈

¶栈结构

¶概念解释：

• 对栈结构的理解生活中有个很类似的例子 – 叠盘子：最先洗好的盘子放在最下面，然后一个一个往上叠加；取盘子用的时候也是从上面开始取用，不会从中间抽一个盘子出来。
• 基于这种场景，再类比栈的特点：先进后出，后进先出；只允许在栈顶进行入栈，出栈操作； 和前面的数组以及链表不同，栈结构是一种操作受限的结构，从王争的《数据结构和算法之美》的栈一章节里面，看到这样一句话:特定的数据结构是对特定场景的抽象，这样结合栈的实际使用场景就能更好地理解栈结构。

---

¶栈实现

• 基于数据和链表都可以实现栈结构，前者称为顺序栈，后者称为链式栈；

• 联想到数组和链表的特性，数组初始化时容量固定，适用于元素数量固定的场景，不需要进行扩容，避免产生更高的开销；

• 链式栈不存在容量的限制，在需要自动扩容的不定长栈场景中可以采用这种实现。

• 顺序栈

  static class ArrayStack{
  	   
      // 差点写成泛型类
      private String[] items;
      //栈容量
      private int length;
      //元素数量
      private int size = 0;
  
      ArrayStack(int length){
          length = length <=0 ? 8 :length;
          this.items = new String[length];
          this.length = length;
      }
  
      ArrayStack(){
          this.length = 8;
          this.items = new String[length];
      }
  
      public String getTop(){
          return this.items[size-1];
      }
  
      //压栈
      public void push(String item){
  
          if(!sizeCheck()){
              this.items = new ArrayStack().items;
          }
          //数组的拷贝扩容
          if(size >= length){
              String[] newItem = new String[length*2];
              for(int i = 0;i<length;i++){
                  newItem[i] = items[i];
              }
              this.items = newItem;
          }
          items[size] = item;
          size++;
      }
  
      //弹栈
      public String pop(){
          if(size == 0) {
              return null;
          }
          String value = items[size-1];
          if(sizeCheck()){
              items[size-1] = null;
          }
          size-=1;
          return value;
      }
  
      //容量检查
      private  boolean sizeCheck(){
          if(null == this.items || length == 0){
              return false;
          }
          return true;
      }
  
  }

• 只有压栈(push)，弹栈(pop)操作。这里的实现增加了栈扩容，也就是对存放元素的数组进行拷贝移动，返回一个新的 2 倍长的数组

¶栈的应用场景:

• 四则运算：对于我们来说，数学的四则运算是比较简单的，按照运算符优先级直接计算就是了，但是对于计算机而言，识别不同的运算符，还得和对应的数字按照优先级进行四则运算，是比较困难的；

• 一个解决思路是：使用两个栈，一个保存操作数，一个保存运算符；当运算符压栈的时候，比较它和当前栈顶运算符的优先级，优先级高的情况下，先从操作数栈弹出两个数计算出结果再重新压入操作数栈；如此循环直到操作数栈剩下最终的运算结果

  public static int noBracketsStackArithmetic(String expression){
  
      final String operator = "*/+-";
      final String mdOperator = "*/";
      final String pdOperator = "+-";
      final String numStr = "0123456789";
      ArrayStack numberStack = new ArrayStack(10);
      ArrayStack operateStack = new ArrayStack(10);
  
      String[] numberOperator = expression.split("");
      // 将操作数和运算符压栈
      for(String str : numberOperator){
  
          if(StringUtils.isNotBlank(str)){
              //                System.out.println(str);
              if(numStr.indexOf(str)>-1){
                  // 操作数压栈
                  numberStack.push(str);
              }else if(operator.indexOf(str)>-1){
                  //运算符压栈
                  if(numberStack.size%2==1){
  
                      if(pdOperator.indexOf(str)>-1 && operateStack.size>1 && mdOperator.indexOf(operateStack.getTop()) > -1){
                          // 当前运算符优先级低于栈顶运算符，低于栈顶操作运算符
                          Integer num1 = Integer.valueOf(numberStack.pop());
                          Integer num2 = Integer.valueOf(numberStack.pop());
                     		numberStack.push(al(num1,num2,operateStack.pop()).toString());
                      }
                  }
                  operateStack.push(str);
              }else{
                  System.out.println(str);
              }
          }
      }
  
      //顺序遍历栈内容
      while(true){
          Integer num1 = 0;
          Integer num2 = 0;
          String opera = "";
          if(numberStack.size<=0){
              break;
          }
  
          while(numberStack.size > 0){
              num1 = Integer.valueOf(numberStack.pop());
              num2 = Integer.valueOf(numberStack.pop());
              break;
          }
  
          //操作数栈
          while(operateStack.size > 0){
              opera = operateStack.pop();
              break;
          }
  
          // 一次弹栈之后根据下次弹栈的结果决定是否进行计算
          Integer result = 0;
          if(pdOperator.indexOf(opera) >-1){
              numberStack.push(al(num1,num2,opera));
          }
          if(numberStack.size==1){
              return Integer.valueOf(numberStack.pop());
          }
      }
      return 0;
  }
  
  //四则运算
  public static Integer al(Integer num1,Integer num2,String opera){
      Integer result = 0;
      switch(opera){
          case "*":
              result = num2 * num1;
              break;
          case "/":
              result = num2 / num1;
              break;
          case "+":
              result = num2 + num1;
              break;
          case "-":
              result = num2 - num1;
              break;
          default:break;
      }
      return result;
  }

• 实现比较粗糙，没有考虑代码的整洁性和效率

• 思路还是参照刚才思路：当低优先级运算符压栈的时候，比较它和栈顶运算符的优先级；如果低于栈顶运算符优先级，则先取出两个操作数进行运算，将结果压入操作数栈，再将刚才的运算符压栈

• 测试了一下 : 3+5*8-6 这个例子，在弹栈进行计算的时候，忽略了操作数栈为1的情况，出现了下标越界的情况

• 上面这个例子只能用于个位数四则运算，并不完善

¶小结:

• 栈是一种操作受限的数据结构，它只允许从栈顶进行入栈和出栈操作；基于不同基础数据结构实现的栈各自有不同的应用场景；
• 具体的数据结构是对具体场景的抽象，从栈实现的四则运算来看，整个表达式可以划分成成若干个单次运算的子表达式，通过压入的运算符决定计算的优先级，然后将优先级较高的表达式进行计算得出的结果重新压入操作数栈作为下次计算的结果；最后再顺序遍历两个栈进行计算就行了
• 联想一下王争老师提到的问题：为什么要用栈来保存临时变量？
• 栈的一个特点是：后进先出，对于函数调用来说，需要知道被调用函数的结果才能完成自身的局部变量运算，所以选择栈是顺理成章的。
• 对于第二点解释尚未仔细理解：从调用函数进入被调用函数，对于数据(临时变量？？)来说变化的是作用域，所以根本上只要能保证每次进入一个新的函数都是一个新的作用域即可。用栈实现刚好，得到被调用函数的结果后，栈顶就恢复成调用函数，继续进行计算。