资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/javascript的数据结构--实现一个栈

javascript的数据结构--实现一个栈

defcon / 1925人阅读

摘要：栈不管是在哪个语言，，还有咱们的都有这个数据结构，很多从别的行业转开发的朋友都会经过这个学习过程。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。移除栈顶的元素，同时返回被移除的元素。

栈：不管是在哪个语言，c/c++,java,python，还有咱们的javascript都有这个数据结构，很多从别的行业转开发的朋友都会经过这个学习过程。

栈：一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的
同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

在现实生活中也能发现很多栈的例子。例如，下图里的一摞书或者餐厅里堆放的盘子。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

创建一个栈 （直接用ES6的class来写吧）

先熟悉一下栈的一些方法：

push(element(s)) ：添加一个（或几个）新元素到栈顶。
pop() ：移除栈顶的元素，同时返回被移除的元素。
peek() ：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
isEmpty() ：如果栈里没有任何元素就返回 true ，否则返回 false 。
clear() ：移除栈里的所有元素。
size() ：返回栈里的元素个数。这个方法和数组的 length 属性很类似。
class Stack {
    constructor () {
        this.items = []; //{1}
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        this.items.pop();
    ｝
    peek() {
        return items[items.length-1];
    }
    isEmpty() {
        return items.length == 0;
    }
    size() {
        return items.length;
    }
    clear() {
        items = [];
    }
    print() {
        console.log(items);
    }
}

尽管代码看起来更简洁、更漂亮，变量 items 却是公共的。ES6的类是基于原型的。虽然基
于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性（变量）
或方法。而且，在这种情况下，我们希望 Stack 类的用户只能访问暴露给类的方法。否则，就有
可能从栈的中间移除元素（因为我们用数组来存储其值），这不是我们希望看到的。

1. 用ES6的限定作用域 Symbol 实现类

ES6新增了一种叫作 Symbol 的基本类型，它是不可变的，可以用作对象的属性。看看怎么用
它来在 Stack 类中声明 items 属性：

let _items = Symbol(); //{1}
class Stack {
    constructor () {
        this[_items] = []; //{2}
    }
    //Stack方法
}

在上面的代码中，我们声明了 Symbol 类型的变量 _items （行 {1} ），在类的 constructor 函
数中初始化它的值（行 {2} ）。要访问 _items ，只需把所有的 this.items 都换成 this[_items] 。
这种方法创建了一个假的私有属性，因为ES6新增的 Object.getOwnPropertySymbols 方
法能够取到类里面声明的所有 Symbols 属性。下面是一个破坏 Stack 类的例子：

let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 输出 5, 8, 1

从以上代码可以看到，访问 stack[objectSymbols[0]] 是可以得到 _items 的。并且，
_items 属性是一个数组，可以进行任意的数组操作，比如从中间删除或添加元素。我们操作的
是栈，不应该出现这种行为。

2. 用ES6的 WeakMap 实现类

有一种数据类型可以确保属性是私有的，这就是 WeakMap 。我们会在第7章深入探讨 Map 这
种数据结构，现在只需要知道 WeakMap 可以存储键值对，其中键是对象，值可以是任意数据类型。

如果用 WeakMap 来存储 items 变量， Stack 类就是这样的：

const items = new WeakMap(); //{1}
class Stack {
    constructor () {
        items.set(this, []); //{2}
    }
    push(element) {
        let s = items.get(this); //{3}
        s.push(element);
    }
    pop() {
        let s = items.get(this);
        let r = s.pop();
        return r;
    }
    //其他方法
}

行 {1} ，声明一个 WeakMap 类型的变量 items 。
行 {2} ，在 constructor 中，以 this （ Stack 类自己的引用）为键，把代表栈的数组存入 items。
行 {3} ，从 WeakMap 中取出值，即以 this 为键（行 {2} 设置的）从 items 中取值。
现在我们知道， items 在 Stack 类里是真正的私有属性了，但还有一件事要做。 items 现在
仍然是在 Stack 类以外声明的，因此谁都可以改动它。我们要用一个闭包（外层函数）把 Stack
类包起来，这样就只能在这个函数里访问 WeakMap ：

let Stack = (function () {
    const items = new WeakMap();
    class Stack {
        constructor () {
            items.set(this, []);
        }
        //其他方法
    }
    return Stack; //{4}
})();

当 Stack 函数里的构造函数被调用时，会返回 Stack 类的一个实例（行 {4} ）。

一个例子（把十进制的数转换成任意进制的数）

function baseConverter(decNumber, base){
    var remStack = new Stack(),
        rem,
        baseString = "",
        digits = "0123456789ABCDEF"; //{5}
    while (decNumber > 0){
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    while (!remStack.isEmpty()){
        baseString += digits[remStack.pop()]; //{6}
    }
    return baseString;
}

我们只需要改变一个地方。在将十进制转成二进制时，余数是0或1；在将十进制转成八进制
时，余数是0到7之间的数；但是将十进制转成16进制时，余数是0到9之间的数字加上A、B、C、
D、E和F（对应10、11、12、13、14和15）。因此，我们需要对栈中的数字做个转化才可以（行
{5} 和行 {6} ）。

参考：《Javascript数据结构与算法》

服务器托管 私有云 java 手写一个栈 python实现栈 javascript全栈视频 javascript全栈教程

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

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

相关文章

  • JavaScript数据结构《栈》

    摘要：我们都知道数组是里面比较常用的一种数据结构，栈和数组类似，定义如下栈是一种遵从后进先出原则的有序集合。新增加和待删除的元素都保存在栈的尾部，也称栈顶，相反的另一端就叫栈底，在栈的这种数据结构里面，我们新增的元素都在栈顶，旧的元素都在栈底。 由于不是计算机专业出身，对数据结构这些了解的比较少，最近看了一些相关的书籍，这里做一些总结。本篇要说的是栈。我们都知道数组是JavaScript里面...

    nanchen2251 评论0 收藏0

  • Javascript实现基本的数据结构 一 栈

    摘要：今天实现的是最基本的数据结构之一栈栈在中有着非常重要，基本类型会存储在栈中，你可以操作实际的值。要定义一个栈，首先需要明白，栈的基本结构有哪些，需要遵循哪些规则。首先创建一个函数对象表示栈。 Javascript工程师，总会面对一个问题，数据结构和算法会成为自己的短板，不仅是对非科班，甚至一些科班出身的工程师来说也是自己的短板，于是就有了这系列文章。基础决定深度，前端入门易，上升困难，...

    seanlook 评论0 收藏0

  • Javascript实现基本的数据结构 一 栈

    摘要：今天实现的是最基本的数据结构之一栈栈在中有着非常重要，基本类型会存储在栈中，你可以操作实际的值。要定义一个栈，首先需要明白，栈的基本结构有哪些，需要遵循哪些规则。首先创建一个函数对象表示栈。 Javascript工程师，总会面对一个问题，数据结构和算法会成为自己的短板，不仅是对非科班，甚至一些科班出身的工程师来说也是自己的短板，于是就有了这系列文章。基础决定深度，前端入门易，上升困难，...

    cnio 评论0 收藏0

  • 学习javascript数据结构(一)——栈和队列

    摘要：原文地址学习数据结构一栈和队列博主博客地址的个人博客几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。他们就是栈和队列。我们称作栈顶，而另一端我们称作栈底。移除栈顶的元素，同时返回被移除元素。 前言 只要你不计较得失，人生还有什么不能想法子克服的。 原文地址：学习javascript数据结构(一)——栈和队列 博主博客地址：Damonare的个人博客 几乎所有的编程...

    doodlewind 评论0 收藏0

  • 学习JavaScript数据结构与算法（一）：栈与队列

    摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列 本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

    Flink_China 评论0 收藏0

发表评论

登陆后可评论

0条评论

defcon

男|高级讲师
我要私信

TA的文章

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