js--用javaScript来实现栈数据结构

前言

　　作为科班出身的小伙伴在大学肯定学习过数据结构这么课程，数据结构作为一门必修课，话说对数据结构的掌握程度决定程序员阶级水平，侧面反映程序员的收入状况，同样数据结构也是工作面试必考的知识点，这里记录一下我在这方面的学习笔记，希望看到的小伙伴也能查漏补缺，帮助到大家。

正文

　　1.栈是什么

　　作为前端开发工程师，平常用到最多的应该是数组这种数据结构，数组是使用一个单独的变量来存放一系列的值，这些值在内存中被存放在一块连续的空间中，因此可以通过下标的方式来访问数组中的每一个成员。

　　栈，在没了解之前，暂且可以理解为一种特殊的数组，特殊之处在哪里呢?栈和数组一样，是一种线性存储方式，一种线性的数据结构，但是又不同与数组，栈对元素的进出顺序又严格的要求，栈只允许在同一端进行插入和删除的操作，这就好比放在餐桌上的一摞盘子，你要不在上面继续放盘子，叠加的盘子只能出现在这一摞的最上面，你要想取走一个盘子，同样有限拿走上面的盘子。在比如手枪里面装子弹，最先被装进去的最后被打出来，最后装进去的最先被打出来，生活中好多这种类似的数栈结构例子。因此，不难理解，栈就是这种 “先进后出，后进先出”的一种数据结构。

　　栈顶：栈的最上面的元素称为栈顶元素，最后进来，最先出去，

　　栈底：栈的最下面的元素称为栈底元素，最早进来，最后出去。

　　出栈，入栈：栈内元素的进入，出去称为出入栈。

　　空栈：当栈内没有元素的时候，栈顶与栈底合并，栈中元素长度为0，此时称为空栈。

　　2.栈的方法总结

　　这里总结一下栈的主要操作方法：

　　（1）push() 入栈

　　（2）pop ()出栈

　　（3）peek() 获取栈顶元素

　　（4）isEmpty() 判断栈是否为空

　　（5）size() 获取栈中元素的长度

　　（6）toString() 输出栈中全部元素

　　3.用js实现栈的方法

　　这里使用了数组来模拟栈的方法，对数组进行包装，使其具有栈的特性

      //  基于数组的实现代码
      function Stack() {
        // 栈中的属性
        this.items = [];

        // 栈的相关操作
        // 1.将元素入栈 
        // this.push = function (){}//这种方法相当于给某个对象的实例添加了一个方法
        Stack.prototype.push = function (element) {
          // 这种方法相当于给某个类添加了这个方法，节省内存
          this.items.push(element);
        };

        // 2.将元素出栈
        Stack.prototype.pop = function () {
          return this.items.pop();
        };

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

        // 4.判断栈是否为空
        Stack.prototype.isEmpty = function () {
          return this.items.length === 0 ? true : false;
        };

        // 5.获取占中元素的个数
        Stack.prototype.size = function () {
          return this.items.length;
        };

        // 6.toString方法实现
        Stack.prototype.toString = function () {
          return this.items.join(" ");
        };
      }   
       // 栈的使用
        var s = new Stack();
        console.log("isEmpty:", s.isEmpty());//true
        s.push(11);
        s.push(22);
        s.push(33);
        console.log("size:", s.size());//3
        console.log("s", s.items);//[11,22,33]
        console.log("peek", s.peek());//33
        s.pop();
        console.log("s", s.items);//[11,22]
        console.log("toString", s.toString());//11 22

　　4.栈结构的应用

　　十进制转二进制，计算100转为二进制

         /*
            100/2  50余数为0
            50/2   25 余数为0
            25/2   12 余数为1
            12/2   6 余数为0
            6/2     3 余数为0
            3/2    1 余数为 1
            1/2    0 余数为1
            因此100的二进制为 1100100
        */
      function toBin(decNumber) {
        //   1 定义一个栈对象
        let stack = new Stack();
        //  2  循环操作
        while (decNumber > 0) {
          // 2.1 获取余数并放入到栈中
          stack.push(decNumber % 2);
          // 2.2获取每次的商 ，作为下一次的被除数
          decNumber = Math.floor(decNumber / 2);
        }
        // 3 从栈中取出存入的元素
        var binaryStr = "";
        while (!stack.isEmpty()) {
          binaryStr += stack.pop();
        }
        return binaryStr
      }
      console.log("toBin", toBin(100));// 1100100

总结

　　以上就是本文的全部内容，希望给读者带来些许的帮助和进步，方便的话点个关注，小白的成长踩坑之路会持续更新一些工作中常见的问题和技术点。

js--用javaScript来实现栈数据结构

推荐阅读