资讯专栏INFORMATION COLUMN

如何用JavaScript手动实现一个栈

taoszu / 1177人阅读

摘要:所以,可以这样写利用数组的方法,就可以实现在栈顶末尾添加新的元素了。因为栈地内部使用数组保存元素,所以数组地就是栈的长度。实现方法,方法用来清空栈中所有的元素。感兴趣可以自行百度去了解原文链接行无忌的成长小屋如何用手动实现一个栈

什么是栈(Stack)

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

新添加的或待删除的元素都保存在栈的末尾,称为栈顶,另一端叫栈底。

在栈里,新元素都靠近栈顶,旧元素都接近栈底

现实中的例子

在生活中也能发现很多栈的例子。例如,厨房里堆放的盘子,总是叠在上方的先被使用;输入框内容进行删除时,总是最后输入的先删除;弹夹中的子弹,越后装入的,越先发射......

手动实现一个栈

首先,创建一个类来表示栈

function Stack () { }

我们需要选择一种数据结构来保存栈里的元素,可以选择数组

function Stack(){
    var items = [];     //用来保存栈里的元素
}

接下来,为栈添加一些方法

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素,同时返回被移除的元素
peek();             //返回栈顶的元素,不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true,否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

我们需要实现的第一个方法时push。用来往栈里添加新元素,有一点很重要:该方法只添加到栈顶,也就是栈的末尾。所以,可以这样写:

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

利用数组的push方法,就可以实现在栈顶末尾添加新的元素了。

接着,来实现pop方法,用来实现移除栈里的元素。栈遵从LIFO(后进先出)原则。移出去的是最后添加进去的元素。因此,可以使用数组的pop方法。

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

这样一来,这个栈自然就遵从了LIFO原则

现在,再来为这个栈添额外的辅助方法。

如果想知道栈里最后添加的元素是什么,可以用peek方法。这个方法将返回栈顶的元素

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

因为类内部是用数组保存元素的,所以这里访问数组最后一个元素用length-1

下一个要实现的方法是isEmpty,如果栈为空的话,就返回true,否则返回false:

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

使用isEmpty方法,就能简单地判断栈内部是否为空。

类似于数组地length属性,我们也可以实现栈地length。

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

因为栈地内部使用数组保存元素,所以数组地length就是栈的长度。

实现clear方法,clear方法用来清空栈中所有的元素。最简单的实现方法是:

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

其实多次调用pop方法也可以,但是没有这个方法来的简单快捷。

最后,为了检查栈里的内容,还需要实现一个辅助方法:print。它会把栈里的元素都输出到控制台:

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

至此,我们就完整地创建了一个!

栈的完整代码
function Stack(){

    var items = [];     //用来保存栈里的元素

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

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

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

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

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

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

    this.print = function () {
        console.log(items.toString());
    }
}
使用Stack类

栈已经创建好了,我们来测试一下

首先,来初始化Stack类。然后,验证一下栈是否为空

var 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

我们往栈里又添加了11。如果调用size方法,输出为3,因为栈里有三个元素(5,8和11)。如果这时候调用isEmpty方法,会看到输出了false(因为此时栈不为空)。最后,再来往里面添加一个元素:

stack.push(15);

然后,调用两次pop方法从栈里移除两个元素:

stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]

到这里,整个栈的功能测试完成。

用栈来解决问题

使用栈来完成进制转换。

现实生活中,我们主要用10进制,但在计算科学中,二进制非常重要,因为计算机里所有的内容都是用二进制数字0和1来表示的。大学的计算机课都会先教进制转换。以二进制为例:

function divideBy2 (decNumber) {

    var remStack = new Stack(),
    rem,
    binaryString = "";

    while (decNumber>0) {  //{1}
        rem = Math.floor(decNumber % 2);  //{2}
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / 2);  //{4}
    }

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

这段代码里,当结果满足和2做整除的条件时,(行{1}),我们会获得当前结果和2的余数,放到栈里(行{2}、{3})。然后让结果和2做整除(行{4})

注:JavaScript有数字类型,但是它不会区分时整数还是浮点数。因此,要使用Math.floor函数让除法的操作仅返回整数部分。

最后,用pop方法把栈中的元素都移除,把出栈的元素连接成字符串(行{5})。

测试一下:

console.log(divideBy2(520));      //输出1000001000
console.log(divideBy2(10));       //输出1010
console.log(divideBy2(1000));     //输出1111101000

接下来,可以很容易的修改上面的算法,使它能够把十进制转化为任何进制。除了让十进制数字和2整除转成二进制数,还可以传入其他任意进制的基数作为参数,就像下面的算法这样:

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = "";
    digits = "0123456789ABCDEF";     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

在将十进制转成二进制时,余数是0或1;在将十进制转成八进制时,余数时0-8之间的数;但是将十进制转成十六进制时,余数时0-9之间的数字加上A、B、C、D、E、F(对应10、11、12、13、14和15)。因此,需要对栈中的数字做个转化才可以(行{6}、{7})。

来测试一下输出结果:

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多,比如平衡圆括号和汉诺塔。感兴趣可以自行百度去了解

原文链接:行无忌的成长小屋:如何用JavaScript手动实现一个栈

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/95481.html

相关文章

  • 何用自己喜欢的 CSS 风格重置网站的样式

    摘要:翻译疯狂的技术宅原文许多前端开发人员都在用为他们的网站设计样式。一些人喜欢在中添加一些自己偏好的样式,我也一样。我认为这是令人难以置信和奇怪的。不同的浏览器为表单元素和按钮设置了不同的边框样式。这种风格的问题是它的特异性低。 翻译:疯狂的技术宅原文:https://medium.freecodecamp.o... 许多前端开发人员都在用 Normalize 为他们的网站设计样式。一些...

    shaonbean 评论0 收藏0
  • vscode一格式化就报错?各种风格问题各种报错烦不胜烦,教你何用好vue的eslint风格配置

    摘要:格式化安装插件如果题主认真读了的的话,应该可以写出下面的配置了。用来格式化和提示格式错误。在编码过程中提示格式错误,养成良好的编码习惯。 前言 感觉搭建一个舒服的前端开发环境,十分的重要定制化的格式化,编辑器自带的格式化各种报错,手动改真的会死人,因此搭建一个编辑器环境必不可少,现在要讲的是vscode中如何定制vue vs code的配置文件: showImg(https://seg...

    Achilles 评论0 收藏0
  • 什么是JavaScript 事件循环 ?

    摘要:此事件队列的美妙之处在于它只是函数等待被调用和移动到调用栈的一个临时存放区域。在事件循环不断监视调用栈是否为空现在确实是空的时候调用创建一个新的调用栈来执行代码。在执行完之后进入了一个新的状态这个状态调用栈为空事件记录表为空事件队列也为空。 这篇文章是对个人认为讲解 JavaScript 事件循环比较清楚的一篇英文文章的简单翻译,原文地址是http://altitudelabs.com...

    tracymac7 评论0 收藏0
  • Day03 - CSS 变量

    摘要:变量作者简介是推出的一个天挑战。这是一个的新特性,和目前都还不支持。命名写法是变量名,在引用这个变量时写法是变量名。如何用改变属性值在中即代表文档根元素。 Day03 - CSS 变量 作者:©liyuechun 简介:JavaScript30 是 Wes Bos 推出的一个 30 天挑战。项目免费提供了 30 个视频教程、30 个挑战的起始文档和 30 个挑战解决方案源代码。目的是...

    dunizb 评论0 收藏0
  • 2017-07-08 前端日报

    摘要:前端日报精选精读与提案知乎专栏第期认识引擎记录一次利用工具进行性能优化的真实案例简书中的使用规则教程继承的实现方法个人文章中文译组件渲染性能探索个人文章周刊第期表单性能的改进实践知乎专栏简单可重用的图表库知乎专栏 2017-07-08 前端日报 精选 精读 TC39 与 ECMAScript 提案 - 知乎专栏【第989期】认识 V8 引擎记录一次利用 Timeline/Perform...

    王岩威 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<