用js来实现那些数据结构04(栈01-栈的实现)

其实说到底,在js中栈更像是一种变种的数组,只是没有数组那么多的方法,也没有数组那么灵活。但是栈和队列这两种数据结构比数组更加的高效和可控。而在js中要想模拟栈,依据的主要形式也是数组。从这篇文章开

大家好,又见面了,我是你们的朋友全栈君。

  其实说到底,在js中栈更像是一种变种的数组,只是没有数组那么多的方法,也没有数组那么灵活。但是栈和队列这两种数据结构比数组更加的高效和可控。而在js中要想模拟栈,依据的主要形式也是数组。

  从这篇文章开始,可能会接触到一些原型,原型链,类,构造函数等相关的js概念,但是这里并不会过多的介绍这些概念,必要的时候会进行一些简要的说明,推荐大家去看看汤姆大叔的深入理解Javascript系列,王福朋大神的深入理解Javascript原型和闭包系列。都是极为不错的深度好文,推荐大家可以深入学习。

  要想实现一个数据结构,首先你要明白它的基本原理,那么栈是什么?又是如何工作的呢?

  栈(stack)是一种遵循后进先出(Last In First Out)原则的有序集合。新添加的元素和待删除的元素都保存在栈的同一端,称为栈顶,另一端就叫做栈底。在栈里,新元素都接近栈顶,旧元素都靠近栈底。其实可以把栈简单理解成往一个木桶里堆叠的放入物品,最后放进去的在桶的顶端,也是可以最先拿出来的,而最先放进去的却在桶的底部,只有把所有上面的物品拿出来之后才可以拿走底部的物品。

  对于数组来说,可以添加元素,删除元素,获取数组的长度以及返回对应下标得到值,那么在开始构造一个栈之前,我们需要了解一下栈都有哪些基本操作。

  1、压栈,也称之为入栈,也就是把元素加入栈中。就像是数组中的push一样。

  2、出栈,移除栈顶的元素。就像是数组中的pop一样。

  3、获取栈顶的元素,不对栈做任何其他操作。就像是在数组中通过下标获取对应的值一样。

  4、判断栈是否为空。就像是判断数组的长度是否为0一样。

  5、清空栈,也就是移除栈里的所有元素。就像是把数组的长度设置为0一样。

  6、获取栈里的元素个数。就像是数组的length属性一样。

  那么,我相信我大家已经对栈有了一个基本的了解,那么我们接下来就看看如何通过构造函数来实现一个自己的js栈。

function Stack () {
    var items = [];

    //首先,我们来实现一个入栈的方法,这个方法负责往栈里加入元素,要注意的是,该方法只能添加元素到栈顶,也就是栈的尾部。
    this.push = function (ele) {
        items.push(ele)
    }

}

var stack = new Stack();

  我们声明一个构造函数,并且在构造函数中生命一个私有变量items,作为我们Stack类储存栈元素的基本支持。然后,加入一个push方法,通过this来使其指向调用该方法的实例。下面我们还会通过这样的方式依次添加其他的方法。

function Stack () {
    var items = [];

    //首先,我们来实现一个入栈的方法,这个方法负责往栈里加入元素,要注意的是,该方法只能添加元素到栈顶,也就是栈的尾部。
    this.push = function (ele) {
        items.push(ele);
    }

    //然后我们再添加一个出栈的方法,同样的,我们只能移除栈顶的元素。
    this.pop = function (ele) {
        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())
    }
}

  这样我们就通过构造函数完整的创建了一个栈。我们可以通过new命令实例化一个Stack对象来测试一下我们的栈好不好用。

var stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(1);
stack.print();
stack.push(3);
stack.print();
console.log(stack.isEmpty());//false
console.log(stack.size());//2
stack.push(10);
stack.print();
stack.pop();
stack.print();
stack.clear();
console.log(stack.isEmpty());//true

  我们发现我们的Stack类执行的还算不错。那么还有没有其他的方式可以实现Stack类呢?在ES6之前我可能会遗憾懵懂的对你Say No。但是现在我们可以一起来看看ES6带我们的一些新鲜玩意。

   在开始改造我们的Stack类之前,需要先说一下ES6的几个概念。Class语法Symbol基本类型WeakMap。简单解释一下,以对后面的改造不会一脸懵逼,而大家想要更深入的了解ES6新增的各种语法,可以去自行查阅。

  Class语法简单来说就是一个语法糖,它的功能ES5也是完全可以实现的,只是这样看写起来更加清晰可读,更像是面向对象的语法。

  Symbol是ES6新增的一个基本类型,前面几篇文章说过,ES5只有6中数据类型,但是在ES6中又新增一种数据类型Symbol,它表示独一无二的值。

  WeakMap,简单来说就是用于生成键值对的集合,就像是对象({})一样,WeakMap的一个重要用处就是部署私有属性。

  当然,上面的简单介绍可不仅仅是这样的,真正的内容要比这些多得多。

  那么在大家知道了它们的一些基本意义。咱们开始改造一下Stack类

class Stack {
  constructor() {
    this.items = [];
  }

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

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

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

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

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

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

  toString() {
    return this.items.toString();
  }

  print() {
      console.log(this.items.toString())
  }

}

  这是用class来实现的Stack类,其实我们可以看一下,除了使用了constructor构造方法以外,其实并没有什么本质上的区别。

  那么我们还可以使用Symbol数据类型来实现,简单改造一下:

const _items = Symbol('stackItems');

class Stack {
  constructor() {
    this[_items] = [];
  }

  push(element) {
    this[_items].push(element);
  }

  pop() {
    return this[_items].pop();
  }

  peek() {
    return this[_items][this[_items].length - 1];
  }

  isEmpty() {
    return this[_items].length === 0;
  }

  size() {
    return this[_items].length;
  }

  clear() {
    this[_items] = [];
  }

  print() {
    console.log(this.toString());
  }

  toString() {
    return this[_items].toString();
  }
}

  使用Symbol也没有大的变化,只是声明了一个独一无二的_items来代替构造方法中的数组。

  但是这样的实现方式有一个弊端,那就是ES6新增的Object.getOwnPropertySymbols方法可以读取到类里面声明的所有Symbols属性。

const stack = new Stack();
const objectSymbols = Object.getOwnPropertySymbols(stack);
stack.push(1);
stack.push(3);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 1, 3, 1

  不知道大家注意没有,我们定义的Symbol是在构造函数之外的,因此谁都可以改动它。所以这样的方式还不是很完善的。那么我们还可以使用ES6的WeakMap,然后用闭包实现私有属性。

//通过闭包把声明的变量变成私有属性
let Stack = (function () {
//声明栈的基本依赖
const _items = new WeakMap();
//声明计数器
const _count = new WeakMap();

class Stack {
  constructor() {
//初始化stack和计数器的值,这里的set是WeakMap的自身方法,通过set和get来设置值和取值,这里用this作为设置值的键名,那this又指向啥呢?自行console!
    _count.set(this, 0);
    _items.set(this, {});
  }

  push(element) {
//在入栈之前先获取长度和栈本身
    const items = _items.get(this);
    const count = _count.get(this);
//这里要注意_count可是从0开始的噢
    items[count] = element;
    _count.set(this, count + 1);
  }

  pop() {
//如果为空,那么则无法出栈
    if (this.isEmpty()) {
      return undefined;
    }
//获取items和count,使长度减少1
    const items = _items.get(this);
    let count = _count.get(this);
    count--;
//重新为_count赋值
    _count.set(this, count);
//删除出栈的元素,并返回该元素
    const result = items[count];
    delete items[count];
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    const items = _items.get(this);
    const count = _count.get(this);
//返回栈顶元素
    return items[count - 1];
  }

  isEmpty() {
    return _count.get(this) === 0;
  }

  size() {
    return _count.get(this);
  }

  clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    _count.set(this, 0);
    _items.set(this, {});
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const items = _items.get(this);
    const count = _count.get(this);
    let objString = `${items[0]}`;
    for (let i = 1; i < count; i++) {
      objString = `${objString},${items[i]}`;
    }
    return objString;
  }

  print() {
      console.log(this.toString());
  }
}

return Stack;
})()

const stack = new Stack();
stack.push(1);
stack.push(3);
stack.print(); // 1, 3, 1

  这是最终比较完善的版本了。那么不知道大家注没注意到一个小细节,前面我们只是声明一个变量,先不管他是不是私有的,就是数组,整个Stack构造函数都是基于items数组来进行各种方法的。

但是这里通过WeakMap作为基本,我们却多用了一个_count,前面说了_count是计数器,那么为啥要用计数器?因为WeakMap是键值对的“对象类型”,本身是没有像数组这样的长度之说的,所以需要一个计数器来代替数组的下标,以实现基于Stack的各种方法。

   到这里基本上就完成了我们的栈,下一篇文章会看看如何用我们写好的栈去做一些有趣事情。

 

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

  

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124429.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 自动编码器模型和代码解释

    自动编码器模型和代码解释CNN算法与程序研究 1)      深度学习基本理论方法http://wenku.baidu.com/view/2e630ddfc5da50e2524d7ff3 特征多,给出的信息多,识别准确性会提升。但是,计算复杂度增加,搜索的空间大,可以用来训练的数据在每个特征上就会稀疏。采用层次网络结构,BP一层隐层节点的浅层模型,带有一层隐层节点(如SVM、Boostin

  • python中的ideavim有什么作用_IdeaVim插件施用技巧

    python中的ideavim有什么作用_IdeaVim插件施用技巧IdeaVim插件使用技巧在IDEAIntellij小技巧和插件一文中简单介绍了一下IdeaVim插件。在这里详细总结一下这个插件在日常编程中的一些常用小技巧。供有兴趣使用这个插件,但对Vim还不十分熟悉的朋友参考。当然基本的hjkl移动光标和几种常见模式等等基本概念就略过不提了。为了确保只包含常用操作,这里提到的技巧都没有从现成文档里抄,而是凭记忆列出(不常用自然就不记得了)。估计会有所遗…

  • docker 常用命令总结[通俗易懂]

    注意stop,restart后的容器,或者commit后的镜像启动环境变量需要重新加载,比如source/etc/source我们运行docker容器的时候,使用了-d参数,把容器在后台运行后。1.启动dockerdockerrun-d-i-t&lt;imageID&gt;/bin/bash上述命令执行某些命令回报错FailedtogetD-Busco…

  • 普罗米修斯监控openGauss

    普罗米修斯监控openGauss1、前期准备1.1项目依赖链接依赖开源工程工程链接普罗米修斯https://github.com/prometheus/pushgatewayopengauss_exporthttps://github.com/enmotech/opengauss_exporterpushgatewayhttps://github.com/prometheus/pushgatewayopenGausshttps://gitee.com/opengauss/openGauss

  • webmin 安装后如何登录 用户名和密码

    webmin 安装后如何登录 用户名和密码

  • HbuilderX打包app,Hbuilder怎么打包app,H5打包成app,H5怎么打包成app「建议收藏」

    1.下载HbuilderX之后新建项目2.在这里选则你需要新建的项目类型,本人打包的是h5app,选的5+app3.选择好项目本地存放的地址,编写项目名,之后点击创建4.打开刚刚创建的那个项目,点击打开manifest.json,就是下图这样子5.填写你的h5项目地址6.基本配置(看图),太简单太多自己研究7.SDK配置里可以配置你的项目的appid、key其他配置,比如你的项目…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号