Javascript与数据结构系列（一）——栈的实现

Travis 发布于2019-08-19 18:05 / 3027人阅读

摘要：栈的实现实现一个栈当务之急是决定存储数据的底层数据结构。变量记录栈顶位置被构造函数初始化为表示栈顶对应数组的起始位置。这是因为栈是空的栈顶没有任何元素。假设想将数字转换为以为基数的数字实现转换的算法如下。

栈的实现

实现一个栈,当务之急是决定存储数据的底层数据结构。这里采用的是数组。我们的实现以定义 Stack 类的构造函数开始:

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

我们用数组 dataStore 保存栈内元素,构造函数将其初始化为一个空数组。变量 top 记录栈顶位置,被构造函数初始化为 0,表示栈顶对应数组的起始位置 0。如果有元素被压入栈,该变量的值将随之变化。
先来实现 push() 方法。当向栈中压入一个新元素时,需要将其保存在数组中变量 top 所对应的位置,然后将 top 值加 1,让其指向数组中下一个空位置。代码如下所示:

function push(element) {
    this.dataStore[this.top++] = element;
}

这里要特别注意 ++ 操作符的位置,它放在 this.top 的后面,这样新入栈的元素就被放在 top 的当前值对应的位置,然后再将变量 top 的值加 1,指向下一个位置。
pop() 方法恰好与 push() 方法相反——它返回栈顶元素,同时将变量 top 的值减 1:

function pop() {
    return this.dataStore[--this.top];
}

peek() 方法返回数组的第 top-1 个位置的元素,即栈顶元素:

function peek() {
    return this.dataStore[this.top-1];
}

如果对一个空栈调用 peek() 方法,结果为 undefined。这是因为栈是空的,栈顶没有任何
元素。
有时候需要知道栈内存储了多少个元素。length() 方法通过返回变量 top 值的方式返回栈内的元素个数:

function length() {
    return this.top;
}

最后,可以将变量 top 的值设为 0,轻松清空一个栈:

function clear() {
    this.top = 0;
}

代码归纳

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}

function push(element) {
    this.dataStore[this.top++] = element;
}

function peek() {
    return this.dataStore[this.top-1];
}

function pop() {
    return this.dataStore[--this.top];
}

function clear() {
    this.top = 0;
}

function length() {
    return this.top;
}

栈的应用 数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数的数字,实现转换的算法如下。

最高位为 n % b,将此位压入栈。

使用n/b代替n。

重复步骤 1 和 2,直到 n 等于 0,且没有余数。

持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符
串形式。

使用栈,在 JavaScript 中实现该算法就是小菜一碟。下面就是该函数的定义,可以将数字转化为二至九进制的数字:

function mulBase(num, base) {
    var s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor(num /= base);
    } while (num > 0);
    var converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}

后话

当然，学好前端，你还需要关注一个公众号！——每日前端
各位兄弟姐妹，共勉！

云服务器 GPU云服务器栈的实现与应用数据分析与数据分析系列教材 javascript专题系列 javascript深入系列

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

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

【译】JavaScript数据结构（2）：栈与队列

摘要：栈和队列是开发中最常用的两种数据结构。如果又有数据入栈，的值将增加到。如果一个数据从栈中被取出，的值将会减少为。队列与栈类似，队列也是一个线性数据结构。与栈不同的是，队列只删除最先添加的数据。现在，让我们将栈大小的实现应用到队列中。翻译：疯狂的技术宅英文：https://code.tutsplus.com/art...说明：本文翻译自系列文章《Data Structures With...

zlyBear 2019-08-20 18:18 评论0 收藏0
JS 栈

摘要：栈学习数据结构与算法读书笔记。栈又名堆栈，是一种遵循后进先出原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。栈《学习JavaScript数据结构与算法》读书笔记。栈（stack）又名堆栈，是一种遵循后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，...

Lin_R 2019-08-22 10:35 评论0 收藏0
学习JavaScript数据结构与算法（一）：栈与队列

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

Flink_China 2019-08-19 17:23 评论0 收藏0
javasctipt 工作原理之调用栈

摘要：译者注翻译一个对新手比较友好的工作原理解析系列文章注意以下全部是概念经验丰富的老鸟可以离场啦正文从这里开始随着的流行团队们正在利用来支持多个级别的技术栈包括前端后端混合开发嵌入式设备以及更多这篇文章旨在成为深入挖掘和实际上他是怎么工作的系列译者注翻译一个对新手比较友好的 JavaScript 工作原理解析系列文章注意: 以下全部是概念,经验丰富的老鸟可以离场啦正文从这里开始随...

Pines_Cheng 2019-08-23 10:38 评论0 收藏0