如何用JavaScript手动实现一个栈

什么是栈(Stack)

  • 栈是一种遵从后进先出(LIFO)原则的有序集合
  • 新添加的或待删除的元素都保存在栈的末尾,称为栈顶,另一端叫栈底
  • 在栈里,新元素都靠近栈顶,旧元素都接近栈底

现实中的例子

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

手动实现一个栈

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

function Stack () { }

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

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

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

push(element(s));   //添加新元素到栈顶pop();              //移除栈顶的元素,同时返回被移除的元素peek();             //返回栈顶的元素,不对栈做任何修改isEmpty();          //如果栈里没有任何元素就返回true,否则falseclear();            //移除栈里的所有元素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());            //控制台输出2stack.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));      //输出1000001000console.log(divideBy2(10));       //输出1010console.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));      //输出10011001111console.log(baseConverter(1231,8));      //输出2317console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

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

原文:https://hx-dl.github.io/hx-dl.github.io/2018/06/15/如何用JavaScript手动实现一个栈/ 作者:行无忌

觉得本文对你有帮助?请分享给更多人。

原文发布于微信公众号 - 程序员宝库(chengxuyuanbaoku)

原文发表时间:2018-06-25

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

19910
来自专栏程序你好

如何比较一个List对象Java 7 vs Java 8

1112
来自专栏个人分享

Scala第一章学习笔记

  面向对象编程是一种自顶向下的程序设计方法。用面向对象方法构造软件时,我们将代码以名词(对象)做切割,每个对象有某种形式的表示服(self/this)、行为(...

1052
来自专栏大神带我来搬砖

程序员的职业素养真是完全靠不住的东西

这里面<T extends Comparable<? super T>>有什么用?

471
来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

1301
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

1150
来自专栏python全栈布道师

2017年8月28日技术日记

4086
来自专栏格子的个人博客

Java源码阅读之LinkedList - JDK1.8

前文基于缓冲数组的ArrayList已经分析过,那么同样作为List实现的LinkedList又有什么不一样呢?

972
来自专栏浪淘沙

关于栈的几个小算法

    想法就是创建一个index变量,index指向含有值得下一个数组空间(假设数组中有两个值,index指向2)

997
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4225

扫码关注云+社区

领取腾讯云代金券