[ JavaScript ] 数据结构与算法 —— 栈

everfight 发布于2019-08-26 13:31 / 2602人阅读

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

前言

JavaScript是当下最流行的编程语言之一，它可以做很多事情：

数据可视化（D3.js，Three.js，Chart.js）;

移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程序);

服务端(Express.js,Koa2)；

桌面应用(Electron,nw.js);

游戏,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);

等等。。。

而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。

本篇主要有三部分

什么是栈

栈的实现

栈的应用

源码地址：https://github.com/yhtx1997/S...

什么是栈 较官方解释

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

个人理解

上面看不懂？没关系，接下来我用生活中比较常见的事来解释。
大家应该都搬过家，旅行，或者上学时住宿，这个过程中都会用到行李箱。

栈：现在这个旅行箱就是我们的栈；

栈里边的元素：我们往旅行箱放叠好的衣服或其他的东西，这些东西就是栈里边的元素；

栈底：我们放衣服时都是是先放旅行箱的最底下，不可能说什么东西都没有就让它飘着是吧，这个旅行箱最底下衣服在的位置就是栈底

栈顶：相对应的最后放进去的一件衣服的位置就是栈顶；

压栈：把元素放进去（把衣服放进旅行箱）的动作就是压栈；

出栈：把元素拿出来（把衣服拿出来）的动作就是出栈；

堆栈溢出：一般是指栈满了放不下了（旅行箱满了怎么塞塞不下了）；

后进先出：放衣服时一件一件的放，但是往外拿衣服的时候是先拿放的时候最后放的，最后拿出来的是放的时候最先放的；可能有人拿衣服直接翻到最下边然后拿出来，这个过程可以看做，先将除了栈底的元素依次出栈并保存，等拿到栈底的元素在依次压栈，把元素放回去

有序集合：额，就是一个挨着一个，有顺序的，一些有相同属性的东西

栈的实现

添加元素

删除元素

返回栈顶元素

是否为空

元素数量

清空元素

打印所有元素

class Stack {
    constructor() {
        this.count = 0; // 长度
        this.items = {}; // 栈
    }
    push(element) {
        // 添加元素
    }
    pop() {
        // 删除元素
    }
    peek() {
        // 返回栈顶元素
    }
    isEmpty() {
        // 是否为空
    }
    size() {
       // 元素数量
    }
    clear() {
       // 清空元素
    }
    toString() {
       // 打印所有元素
    }
}

添加元素

push(element) {
    this.items[this.count] = element;
    this.count++; // 长度加1
}

删除元素

 pop() {
    if (this.isEmpty()) { // 如果是空直接返回 undefined
        return undefined;
    }
    this.count--;
    let item = this.items[this.count];
    delete this.items[this.count];
    return item
}

返回栈顶元素

peek() {
    if (this.isEmpty()) {
        return undefined;
    }
    return this.items[this.count - 1];
}

是否为空

isEmpty() {
    return this.count === 0;
}

元素数量

size() {
    return this.count;
}

清空元素

clear() {
    this.count = 0;
    this.items = {};
}

打印所有元素

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

栈的应用

进制转换

括号匹配检验

迷宫求解

进制转换

栈因为是先进后出，所以如果将一组数据全部压栈，再出栈并保存每次出栈的元素，这样一来相当于将这一组元素的顺序进行倒序。
十进制转换二进制的过程就是一个数除以2，取余数，最后将余数结果进行倒序排列。
现在栈可以进行倒序，而进制转换需要倒序，所以就可以将栈应用到进制的转换中。
代码如下：

function DecimalToBinary(number) {
    let stack = new Stack(); // 新建栈
    let rem = 0; // 余数
    let binary = ""; // 结果
    while (number > 0) {
        rem = Math.floor(number % 2); // 取余数
        stack.push(rem); // 将余数压栈
        number = Math.floor(number / 2); // 去掉余数除以二
    }
    while (!stack.isEmpty()) { // 不为空
        binary += stack.pop(); // 将元素全部出栈
    }
    return binary;
}

括号匹配检验

正常括号嵌套是这样的

{{{[([({()})])]}}}

可以发现，在某个位置分为了左右两部分，右边第一个，与左边最后一个相对应
右边最后一个与左边第一个相对应
左侧相当于进行了倒序，而倒序就可以用栈来解决

我们可以将所有的左侧括号都依次压入栈中，然后依次判断右侧是否与栈顶元素相匹配
但是相匹配的括号并不相等

可以采用键值对的形式存储一下

{
    "}": "{",
    "]": "[",
    ")": "("
}

或者下标的形式

["{","[","("]
["}","]",")"]

最终代码如下

function parenthesesChecker(symbols) {
    let stack = new Stack(); // 新建栈
    let balanced = true; // 检验括号匹配是否正确
    const leftBrackets = "{[("; // 左侧的括号
    const rightBrackets = "}])"; // 右侧的括号
    for (let i = 0; i < symbols.length && balanced; i++) {
        current = symbols[i]; // 取单个符号
        if (leftBrackets.indexOf(current) >= 0) { // 如果是左侧的括号
            stack.push(current); // 将其压栈
        } else if (stack.isEmpty()) { // 不是左侧括号，且栈为空，括号匹配错误
            balancd = false;
        } else { // 不是左侧括号，且栈不为空，视为没有新的左侧括号，剩下的都是右侧括号
            let top = stack.pop();
            if (!(leftBrackets.indexOf(top) === rightBrackets.indexOf(current))) { 
            // 检查栈顶（最后一个左侧括号）符号在 leftBrackets 的位置以及当前符号在 rightBrackets 的位置，位置相同视为配对成功
                balanced = false;
            }
        }
    }
    
    return balanced; // 返回结果
}

迷宫求解

这个比较复杂，之后会写个小实例，敬请期待......

混合云服务器托管 javascript全栈视频 javascript全栈教程 javascript全栈开发 javascript快速全栈开发

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

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

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

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

Flink_China 2019-08-19 17:23 评论0 收藏0
JavaScript数据结构与算法—— 栈

摘要：栈数据结构栈是一种遵循后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，叫做栈顶，另一端叫栈底。在栈中，新元素靠近栈顶，旧元素接近栈底。我们可以在数组的任何位置上删除或者添加元素，但有时候我们还需要在元素的添加或删除时有更多控制的数据结构，有两种数据结构类似于数组，但在添加或删除元素时更为可控，它们就是栈和队列。本节主要介绍栈。 1.栈数据结构栈是一种遵循后进先出（...

王岩威 2019-08-23 15:11 评论0 收藏0
JavaScript的数据结构与算法（一） —— 栈

摘要：栈是一种遵从后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。提供可操作的方法入栈出栈，但是会移掉栈中的数据。栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。 javascript提供可操作的...

quietin 2019-08-21 17:12 评论0 收藏0
JavaScript 数据结构与算法之美 - 栈内存与堆内存、浅拷贝与深拷贝

摘要：栈内存与堆内存浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。栈内存与堆内存中的变量分为基本类型和引用类型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想写好前端，先练好内功。栈内存与堆内存、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。笔者写的 JavaScrip...

dailybird 2019-08-23 18:26 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

Jonathan Shieber 2019-08-29 12:33 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

SHERlocked93 2019-08-22 11:04 评论0 收藏0