专栏首页前端路桥Javascript[0x02] -- 栈

Javascript[0x02] -- 栈

栈是一种遵从后进先出(LIFO)原则的有序集合

知识点:

  • 栈数据结构
  • 向栈添加元素
  • 从栈移除元素
  • 如何使用Stack类
  • 十进制转二进制(经典)

栈的一些方法:

  • push(element(s)):添加一个(或几个)新元素到栈顶。
  • pop():移除栈顶的元素,同时返回被移除的元素。
  • peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。
  • isEmpty():如果栈里没有任何元素就返回true,否则返回false。
  • isFull(): 如果栈满了,返回false, 在我通过阅读《学习JavaScript数据结构与算法(第二版)》中了解到,没有这个,而现实很多例子像堆栈溢出就有栈满这么一说,一琢磨,加吧。
  • clear():移除栈里的所有元素。
  • size():返回栈里的元素个数。这个方法和数组的length属性很类似。

生活中栈的例子:

生活中栈的例子有很多,像子弹压膛然后发射、课代表把作业交给老师,总是最上面最迟交的那个人先挨批、搞计算机经常听到的内存堆栈溢出等等。

窃以为,栈就是一个稳态。当有一个叫push的家伙往里面塞东西,此时,栈被它改变了。

然后,又有一个叫pop的家伙,从栈的”天灵盖“上一个一个拿走push这位仁兄塞进来的东西。

这样一种客观实在我们称之为”栈“。为了记录push和pop这两位选手在栈中搞事情,于是,我们强烈要求peek、isEmpty、isFull、size、clear、show同志加入其中,组成我们今天要讲的”栈“。

在Javascript中栈和数组实在是太像了,那么我们缕一缕更健康。数组它是可以访问任意一个元素的,而栈它不批准你这样子,你只能访问它最顶上的那位;在内存允许的情况下,数组你可以在任意位置怎么开心怎么插,但是栈你只能往栈顶插入,出去也是一样的;这里有个疑问是栈是不是每次只能传一个,愚以为,只要你能实现,传多个也是可以的啊,所以我这里是认为它可以有,传多个值。

本文目录如下:

Part1 - 我抄书的代码

这里的话,是参考一个外国小姐姐写的《学习Javascript数据结构与算法(第二版)》中的栈,基于ES5的语法写的,后续的话会继续改成ES6的,然后用Typescript也实现下吧,多练练。

整体脉络

我们要明确我们要做什么,我们要实现一个栈。不用太伤害脑子的,我们可以事先做的事,就是罗列下,我们大致需要实现那些功能,能不能符合预期,我们另外说。

stack.js

// 你要实现的栈
function Stack() {
    // 一个数组,拿来存放栈里的元素
    let items = [];
    
    // 1、push方法,实现元素进栈
    this.push = function (element) {
    };
    // 2、pop方法,实现元素出栈
    this.pop = function () {
    };
    // 3、peek方法,查看栈顶元素
    this.peek = function () {
        return items[items.length - 1];
    };
    // 4、判空
    this.isEmpty = function () {
    };
    // 5、获取栈的长度
    this.size = function () {
        return items.length;
    };
    // 6、清除栈内数据
    this.clear = function () {
        items = [];
    };
    // 7、打印栈的内容
    this.print = function () {
        console.log(items.toString());
    }

}

大致是需要实现楼上这些吧,接下来我们一个一个来。

1、push方法

前面我们讲过,用数组来存嘛,那这里自然而然的想到数组的push嘛,所以若楼下所示:

this.push = function (element) {
        items.push(element);
    };

2、pop方法

这个跟楼上也类似的,数组也有pop方法,那就直接用呗,如楼下所示:

this.pop = function () {
       return items.pop();
    };

3、peek方法

我们想知道栈这位选手它的栈顶是什么?在数组的背景下,也就是拿出数组中的最后一个对吧。而数组的下标是从0开始的,那么这里就是lenght - 1对吧,具体的如下:

 this.peek = function () {
        return items[items.length - 1];
    };

4、isEmpty方法

什么情况下栈是空的,当且仅当栈的长度为0的时候,在这里也就是数组的长度为0的时候,具体的看楼下:

  this.isEmpty = function () {
        return items.length === 0;
    };

5、size方法

就说我们想知道栈的长度,在这里也就是求数组的长度。

 this.size = function () {
        return items.length;
    };

6、clear方法

想要清空栈,这里用的是数组,那么,一顿操作猛如虎的做法就是arr = [],如楼下所示:

this.clear = function () {
        items = [];
    };

7、print方法

打印直接打数组似乎有点不美观,这里就转成字符串,更符合审美吧,如楼下:

this.print = function () {
        console.log(items.toString());
    }

至此我们通过JavaScript语言简单地实现了一个栈,关于测试部分,我这里放到第二部分来讲。

Part2 - 我自己实现的代码

期望: 我想实现一个栈,它的长度可控,也就是说,在创建一个栈的对象的时候,你可以传个参数,也可以不传个参数。在进栈方面,我期望它一次可以进一个也可以进多个,出栈方面也是同理,这里你可以选择传参和不传参。除此之外,因为长度可控,那么我们势必要增加一个判满对吧。最后就是格式的输出,这里的话会涉及到一个进制转换问题,那么为了美观,4个一输出,不够补0。

思路: 记得去年有幸在王跃大哥的指导下,用C++写过一版栈。凭着模糊的记忆憋一憋还阔以吧。大致是在外面加入一个计数,然后在对应的方法中讨论极值(这里我也不确切放极端还是极值好,暂且极值吧)问题。因为楼上已经大致讲过一次栈了,所以这里就不费笔墨了,直接贴代码吧。

stack3.0.js

/**
 * @description 基于JavaScript的数据结构 - 栈
 * @param n n参数可传可不传
 * @constructor
 * @author Jiangtao Zheng(ataola)
 * @contact zjt613@gmail.com
 * @github https://github.com/ataola
 */
function Stack(n) {
    let items = n === undefined ? [] : new Array(n);  //赋予数组状态
    let count = 0;  //记数
    /**
     * @description 入栈, 支持插入一个或多个, 多个请用数组传值
     * @param element 可以单个插入,也可以多个插入,多个插入传数组
     */
    this.push = function (element) {
        // 当n不为undefined且栈满的时候,此时插入我不批准
        if (n !== undefined && this.isFull()) {
            console.log("入栈错误报警:栈满请注意,栈满请注意,栈满请注意!");
            return;
        }
        if (element instanceof Array) {
            element.map(value => {
                items[count] = value;
                count++;
            })
        } else {
            items[count] = element;
            count++;
        }
    };

    /**
     * @description 出栈,可以出一个或多个元素
     * @param m m可以不传,数字代表出栈个数
     * @returns {*}  返回出栈元素
     */
    this.pop = function (m) {
        //当n为undefined或者栈空时
        if ((n === undefined && count === 0) || this.isEmpty()) {
            console.log("出栈错误报警:栈空请注意,栈空请注意,栈空请注意!");
            return;
        }
        if (m === undefined) {
            let cur = items[count - 1];
            items[count - 1] = undefined;
            count--;
            return cur;
        }

        if (m > 0) {
            let res = [];
            while (m !== 0) {
                res.push(items[count - 1]);
                items[count - 1] = undefined;
                count--;
                m--;
            }
            return res.toString();
        } else {
            let res = items[count - 1];
            count--;
            return res;

        }
    };

    /**
     * @description 判空
     * @returns {boolean}
     */
    this.isEmpty = function () {
        return count === 0;
    };

    /**
     * @description 判满
     * @returns {boolean}
     */
    this.isFull = function () {
        if (count === 0 && n === undefined) {
            return false;
        }
        return count === items.length;
    };

    /**
     * @description 查栈顶元素
     * @returns {*} 返回栈顶的元素
     */
    this.peek = function () {
        return items[count - 1];
    };

    /**
     * @description 清除栈所有元素
     */
    this.clear = function () {
        items.fill(undefined, 0, count);
        count = 0;
    };

    /**
     * @description 查栈的长度
     * @returns {*} 返回栈的长度
     */
    this.size = function () {
        return items.length;
    };

    /**
     * @description 查栈实体部分长度
     * @returns {number} 返回栈实体部分长度
     */
    this.currSize = function () {
        return count;
    };

    /**
     * @description 打印栈的所有元素
     */
    this.show = function () {
       return items.toString();
    };

    /**
     * @description 打印栈的实体元素
     */
    this.currShow = function () {
       return items.slice(0, count).toString();
    }

}

Part3 - 测试

代码不经过测试是一件极其危险且不负责任的事,而测试用例的选取,很有门道,运气好,错的也能测成对的,就看你怎么思考用例了,那我们接下来思考下这边要测什么?

很显然,我们想把楼上写的方法都测一遍或者多遍(排除偶然性),那么我们就要思考测试用例怎么写?

组织下语言大致是这样子,我们创建了一个栈对象,我们先来一波判空,这个时候我们期望得到的答案是对的也就是true。紧接着我们测push,往里面塞0-9个正整数,这个时候我们判断的依据是有 10个元素。然后我们开始测pop,把最后面5个给干掉,这个时候我们意思下来个判空和判满,预期都是false。然后我们开始测peek,如果我们思考是同步的话,那么答案应该是4,我们再测下size,也就是这个栈的总长度,应该是10,再测下currSize,当前的长度,因为出去了5个,所以现在还剩5个,最后我们把它全清空。经过摩卡测试,结果符合预期。

问题思考

数组中的空,占“坑”吗?

愚以为是占“坑”位的,就说我们通过let arr = new Array(20), 然后通过arr.push(21),我们发现它是第21个,而前面20个空的是undefined。

做个进制转换的例子

这里就是存的时候取余和整除,然后存的时候整理下输出,如楼下:

const Stack = require('./stack3.0');

function binaryConver() {
    this.decToBin = function (num) {
        let stack = new Stack();
        let count = 0;
        let cur = num;
        while(cur !== 0) {
            stack.push(cur % 2);
            cur = Math.floor(cur / 2);
            count ++;
        }
        while(count % 4 !== 0) {
            stack.push(0);
            count ++;
        }
        return stack.currShow().split(",").reverse().join("");
    }
}

我们分别取613、2019、1997、1023、521作为测试用例,经过摩卡测试,还阔以。

以上就是今天的全部内容,感谢您的收听,祝您生活愉快!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 软件推荐(幕布) -- 极简大纲笔记

    具体的可以看下这个https://mubu.com/doc4-ijdDSvuLl,写的很详细很详细。

    丰臣正一
  • 网页中Office和pdf相关文件导出

    最近被派去维护和开发一些做了一半、年久失修的项目。有一部分内容是关于word文件导出,顺带着把excel、pdf文件的导出也调研下吧,我想未来开发我应该会遇到的...

    丰臣正一
  • 可以Online Coding的网站哦

    起初是今天问了方老师一个问题,后来方老师贴了个链接,真好用。遂研究了下,还有就是上次旭鸿大哥给我的一个面试链接,能够看到面试者的实时答题情况,今天心血来潮想研究...

    丰臣正一
  • JavaScript创建栈结构

    在数据结构中栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都...

    OECOM
  • 无约束优化

    Quasi-Newton Method (拟牛顿法)。在介绍无约束优化问题之前,我们首先会从直观上引入无约束优化的概念,并在此基础上引入解这类问题的两个重要概念...

    用户2188327
  • PHP设计模式之PHP迭代器模式讲解

    迭代器有时又称光标(cursor)是程式设计的软件设计模式,可在容器物件(container,例如list或vector)上遍访的接口,设计人员无需关心容器物件...

    砸漏
  • 【SLAM】麻省理工 开源 | 重磅! LIO-SAM:紧耦合的实时激光雷达惯性里程计和建图,性能优于LIO-GPS、LOAM等

    论文地址:https://arxiv.org/pdf/2007.00258.pdf

    CNNer
  • Vue中使用setTimeout()定时器延迟执行方法不生效的原因及解决

    直接使用上面的代码执行 closeModal() 方法会报错 Uncaught TypeError: this.showModal is not a funct...

    德顺
  • VBA指针Pointer

    与VarPtr得到的变量地址(假设是pv)关系是,pv这个地址保存的4个字节(32位电脑)的值就是ps。

    xyj
  • Android解析ClassLoader(二)Android中的ClassLoader

    前言 在上一篇文章我们学习了Java的ClassLoader,很多同学会把Java和Android的ClassLoader搞混,甚至会认为Android中的Cl...

    用户1269200

扫码关注云+社区

领取腾讯云代金券