javascript数据结构-栈

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!

栈的概述

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保留在栈的一端，称作栈顶，另一端就叫栈底。
在栈里，新元素都靠近栈顶，旧元素都靠近栈底。在现实生活中有很多栈的例子。例如，在图书馆中有一摞书。你想要拿到下面的就只能先拿走上面的书。栈在编程中用作内存中保存变量、方法调用等等，也被用于浏览器历史记录（浏览器返回按钮）

如何创建一个栈

栈的创建是有两种方式，一种是基于数组，一种是基于链表，这里我们讲基于数组的栈，在链表会在数据结构链表那章博客讲到

• 首先我们需要创建一个stack.js文件，在其中声明Stack类或者stack构造函数

  function stack(){
          //定义一个数组
          this.items=[];
  }

  这样我们的一个栈就构造好了，之后我们需要添加一些方法，来保存数据或删除，这里的方法有部分本质上就是数组的方法

  栈顶构造函数的一些方法

1. 添加一个或多个元素到栈顶—push(element(s))

   //将元素压入栈
   push(element){
       this.items.push(element);
   }

2. 移出栈底元素–pop()

   //将元素从栈中取出
   pop(){
       return this.items.pop();
   }

3. 返回（查看）栈顶元素，不对栈顶元素做修改–peek()

    //查看栈顶元素
   peek(){
       return this.items[this.items.length-1];
   }

4. 判断栈中是否具有元素(是否为空)–isEmpty()

    //判断栈是否为空
   isEmpty(){
       return (this.items.length==0);
   }

5. 移出栈里所有元素

    //判断栈是否为空
   clear(){
       this.items=[];
   }

6. 查看栈中的元素个数–size()

    //判断栈元素个数
   size(){
      return this.items.length;
   }

   基于栈的方法定义了栈的构造函数

   一般我们将构造函数的方法放到原型上

   /* 创建栈的构造函数 */
       function Stack(){
           //定义一个数组
           this.items=[];
           //将元素压入栈
           Stack.prototype.push=function(element){
               this.items.push(element);
           }
           //将元素从栈中取出
           Stack.prototype.pop=function(){
               return this.items.pop();
           }
           //查看栈顶元素
           Stack.prototype.peek=function(){
               return this.items[this.items.length-1];
           }
           //判断栈是否为空
           Stack.prototype.isEmpty=function(){
               return (this.items.length==0);
           }
            //清空栈
           Stack.prototype.clear=function(){
               this.items.length=[];
           }
           Stack.prototype.size=function(){
               return this.items.length;
          }
           //toString方法
           Stack.prototype.toString=function(){
               let resultString="";
               //遍历栈
               for(var i=0;i<this.items.length;i++){
                   resultString +=this.items[i]+"";
               }
               return resultString;
           }      
       }

   Stack构造函数的使用

   const stack=new Stack()
   console.log(stack.isEmpty())  //输出为true
   stack.push(5);
   stack.push(8);
   
   //调用peek方法，将输出8，因为它是往栈里添加最后一个元素
   console.log(stack.peek()) //输出8
   //再添加一个元素
   stack.push(11);
   //输出元素个数
   console.log(stack.size())  //输出3
   //再添加一个元素
   stack.push(15)

   

   用栈来解决问题

• 十进制与转化为二进制用栈来实现

  /* 编写十进制转化为二进制的函数 */
   function dec2bin(decNumber){   //decNumber为传入的十进制数
        /* 创建栈的构造函数 */
      function Stack(){
          //定义一个数组
          this.items=[];
          //将元素压入栈
          stack.prototype.push=function(element){
              this.items.push(element);
          }
          //将元素从栈中取出
          stack.prototype.pop=function(){
              return this.items.pop();
          }
          //查看栈顶元素
          stack.prototype.peek=function(){
              return this.items[this.items.length-1];
          }
          //判断栈是否为空
          stack.prototype.isEmpty=function(){
              return (this.items.length==0);
          }
          //toString方法
          stack.prototype.toString=function(){
              let resultString="";
              //遍历栈
              for(var i=0;i<this.items.length;i++){
                  resultString +=this.items[i]+"";
              }
              return resultString;
          }
          
      }
        //实例化stack类
        var stack=new Stack();
        //如果不为空，取余
        while(decNumber>0){
            stack.push(decNumber % 2);
            decNumber=Math.floor(decNumber/2);   
        }
        //从栈中取出元素
        var binaryString="";
       //循环遍历取出元素
       while(!stack.isEmpty()){ 
           binaryString+=stack.pop();
       }
       console.log(binaryString)
       return binaryString;  
   }
   //调用十进制转化为二进制方法
  console.log(dec2bin(100))  //1100100
  console.log(dec2bin(12))   //1100