1. 全栈程序员必看首页

堆栈的应用——用JavaScript描述数据结构[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 40

堆栈的应用——用JavaScript描述数据结构[通俗易懂]堆栈的应用——用JavaScript描述数据结构

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

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是
仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

一、实现一个栈类Stack

基于堆栈的特性，可以用数组做线性表进行存储。
初始化Stack类的结构如下：

function Stack(){
    this.space = [];
}

Stack.prototype = {
    constructor: Stack,
    /* 接口code */
};

接下来，就是在原型上，对入栈、出栈、清空栈、读取栈顶、读取整个栈数据这几个接口的实现。
Stack类默认以数组头部做栈底，尾部做栈顶。

1.1 入栈 push

入栈可以利用js数组的push方法，在数组尾部压入数据。

Stack.prototype = {
    push: function(value){
        return this.space.push(value);
    }
}

1.2 出栈 pop

出栈同样是利用js数组的pop方法，在数组尾部推出数据。

Stack.prototype = {
    pop: function(){
        return this.space.pop();
    }
}

1.3 清空栈 clear

清空栈相对简单，将存储数据的数组重置为空数组即可。

Stack.prototype = {
    clear: function(){
        this.space = [];
    }
}

1.4 读取栈顶readTop

读取栈顶数据，采用数组下标的方式进行获取。带来的一个好处就是：下标超出数组有效范围时，返回值为undefined。

Stack.prototype = {
    readTop: function(){
        return this.space[this.space.length - 1];
    }
}

1.4 读取整个栈read

读取整个栈数据，直接返回当前数组即可。

Stack.prototype = {
    read: function(){
        return this.space;
    }
}

1.5 聚合

最后，将所有功能聚合后，如下所示，一个堆栈的数据结构就搞定了。

function Stack(){
    this.space = [];
}

Stack.prototype = {
    constructor: Stack,
    push: function(value){
        return this.space.push(value);
    },
    pop: function(){
        return this.space.pop();
    },
    clear: function(){
        this.space = [];
    },
    readTop: function(){
        return this.space[this.space.length - 1];
    },
    read: function(){
        return this.space;
    }
};

二、实战

学数据结构和算法是为了更好、更高效率地解决工程问题。
这里学以致用，提供了几个真实的案例，来体会下数据结构和算法的魅力:)

2.1 数组reverse的实现

当前案例，将用堆栈来实现数组的反转功能。

function reverse(arr){
    var ArrStack = new Stack();

    for(var i = arr.length - 1; i >= 0; i--){
        ArrStack.push(arr[i]);
    }

    return ArrStack.read();
}

如代码所示，可分为以下几个步骤：

  • 实例化一个堆栈用于存储数据
  • 将传入的数组进行倒序遍历，并逐个压入堆栈
  • 最后使用read接口，输出数据

好像很简单，不用担心，复杂的在后面:)

2.2 十进制转换为二进制

数值转换进制的问题，是堆栈的小试牛刀。
讲解转换方法前，先来看一个小例子：

将十进制的13转换成二进制

    2 | 13      1
      ￣￣￣
    2 |  6      0
      ￣￣￣
    2 |  3      1
      ￣￣￣￣
         1      1

如上所示：13的二进制码为1101。
将手工换算，变成堆栈存储，只需将对2取余的结果依次压入堆栈保存，最后反转输出即可。

function binary(number){
    var tmp = number;
    var ArrStack = new Stack();

    if(number === 0){
        return 0;
    }

    while(tmp){
        ArrStack.push(tmp % 2);
        tmp = parseInt(tmp / 2, 10);
    }

    return reverse(ArrStack.read()).join('');
}

binary(14); // 输出=> "1110"
binary(1024); // 输出=> "10000000000"

2.3 表达式求值

这个案例，其实可以理解为简化版的eval方法。
案例内容是对1+7*(4-2)的求值。

进入主题前，有必要先了解以下的数学理论：

  1. 中缀表示法（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。
  2. 逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

常规中缀记法的“3 – 4 + 5”在逆波兰记法中写作“3 4 – 5 +”

  1. 调度场算法（Shunting Yard Algorithm）是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。

提前说明，这只是简单版实现。所以规定有两个：

  1. 数字要求为整数
  2. 不允许表达式中出现多余的空格

实现代码如下：

function calculate(exp){
    var valueStack = new Stack(); // 数值栈
    var operatorStack = new Stack(); // 操作符栈 
    var expArr = exp.split(''); // 切割字符串表达式
    var FIRST_OPERATOR = ['+', '-']; // 加减运算符
    var SECOND_OPERATOR = ['*', '/']; // 乘除运算符
    var SPECIAL_OPERATOR = ['(', ')']; // 括号
    var tmp; // 临时存储当前处理的字符
    var tmpOperator; // 临时存储当前的运算符

    // 遍历表达式
    for(var i = 0, len = expArr.length; i < len; i++){
        tmp = expArr[i];
        switch(tmp){
            case '(':
                operatorStack.push(tmp);
                break;
            case ')':
                // 遇到右括号，先出栈括号内数据
                while( (tmpOperator = operatorStack.pop()) !== '(' && 
                    typeof tmpOperator !== 'undefined' ){
                    valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
                }
                break;
            case '+':
            case '-':
                while( typeof operatorStack.readTop() !== 'undefined' && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
                    (SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){
                    // 栈顶为乘除或相同优先级运算，先出栈
                    valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            case '*':
            case '/':
                while( typeof operatorStack.readTop() != 'undefined' && 
                    FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && 
                    tmp != operatorStack.readTop()){
                    // 栈顶为相同优先级运算，先出栈
                    valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            default:
                valueStack.push(tmp);
        }
    }

    // 处理栈内数据
    while( typeof (tmpOperator = operatorStack.pop()) !== 'undefined' ){
        valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop()));
    }

    return valueStack.pop(); // 将计算结果推出

    /*
        @param operator 操作符
        @param initiativeNum 主动值
        @param passivityNum 被动值
    */
    function calculator(operator, passivityNum, initiativeNum){
        var result = 0;

        initiativeNum = typeof initiativeNum === 'undefined' ? 0 : parseInt(initiativeNum, 10);
        passivityNum = typeof passivityNum === 'undefined' ? 0 : parseInt(passivityNum, 10);

        switch(operator){
            case '+':
                result = initiativeNum + passivityNum;
                console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
                break;
            case '-':
                result = initiativeNum - passivityNum;
                console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
                break;
            case '*':
                result = initiativeNum * passivityNum;
                console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
                break;
            case '/':
                result = initiativeNum / passivityNum;
                console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
                break;
            default:;
        }

        return result;
    }
}

实现思路：

  1. 采用调度场算法，对中缀表达式进行读取，对结果进行合理运算。
  2. 临界点采用operatorStack.readTop() !== 'undefined'进行判定。有些书采用#做结束标志，个人觉得有点累赘。
  3. 将字符串表达式用split进行拆分，然后进行遍历读取，压入堆栈。有提前要计算结果的，进行对应的出栈处理。
  4. 将计算部分结果的方法，封装为独立的方法calculator。由于乘除运算符前后的数字，在运算上有区别，所以不能随意调换位置。

2.4 中缀表达式转换为后缀表达式（逆波兰表示法）

逆波兰表示法，是一种对计算机友好的表示法，不需要使用括号。
下面案例，是对上一个案例的变通，也是用调度场算法，将中缀表达式转换为后缀表达式。

function rpn(exp){
    var valueStack = new Stack(); // 数值栈
    var operatorStack = new Stack(); // 操作符栈 
    var expArr = exp.split('');
    var FIRST_OPERATOR = ['+', '-'];
    var SECOND_OPERATOR = ['*', '/'];
    var SPECIAL_OPERATOR = ['(', ')'];
    var tmp;
    var tmpOperator;

    for(var i = 0, len = expArr.length; i < len; i++){
        tmp = expArr[i];
        switch(tmp){
            case '(':
                operatorStack.push(tmp);
                break;
            case ')':
                // 遇到右括号，先出栈括号内数据
                while( (tmpOperator = operatorStack.pop()) !== '(' && 
                    typeof tmpOperator !== 'undefined' ){
                    valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
                }
                break;
            case '+':
            case '-':
                while( typeof operatorStack.readTop() !== 'undefined' && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 &&
                    (SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){
                    // 栈顶为乘除或相同优先级运算，先出栈
                    valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            case '*':
            case '/':
                while( typeof operatorStack.readTop() != 'undefined' && 
                    FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 && 
                    SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && 
                    tmp != operatorStack.readTop()){
                    // 栈顶为相同优先级运算，先出栈
                    valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop()));
                }
                operatorStack.push(tmp);
                break;
            default:
                valueStack.push(tmp);
        }
    }

    while( typeof (tmpOperator = operatorStack.pop()) !== 'undefined' ){
        valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop()));
    }

    return valueStack.pop(); // 将计算结果推出

    /*
        @param operator 操作符
        @param initiativeNum 主动值
        @param passivityNum 被动值
    */
    function translate(operator, passivityNum, initiativeNum){
        var result = '';

        switch(operator){
            case '+':
                result = `${initiativeNum} ${passivityNum} +`;
                console.log(`${initiativeNum} + ${passivityNum} = ${result}`);
                break;
            case '-':
                result = `${initiativeNum} ${passivityNum} -`;
                console.log(`${initiativeNum} - ${passivityNum} = ${result}`);
                break;
            case '*':
                result = `${initiativeNum} ${passivityNum} *`;
                console.log(`${initiativeNum} * ${passivityNum} = ${result}`);
                break;
            case '/':
                result = `${initiativeNum} ${passivityNum} /`;
                console.log(`${initiativeNum} / ${passivityNum} = ${result}`);
                break;
            default:;
        }

        return result;
    }
}

rpn('1+7*(4-2)'); // 输出=> "1 7 4 2 - * +"

2.5 汉诺塔

汉诺塔

汉诺塔（港台：河内塔）是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

  1. 每次只能移动一个圆盘；
  2. 大盘不能叠在小盘上面。

4个圆盘的汉诺塔的移动

堆栈的经典算法应用，首推就是汉诺塔。

理解该算法，要注意以下几点：

  1. 不要深究每次的移动，要抽象理解
  2. 第一步：所有不符合要求的盘，从A塔统一移到B塔缓存
  3. 第二步：将符合的盘移动到C塔
  4. 第三步：把B塔缓存的盘全部移动到C塔

以下是代码实现：

var ATower = new Stack(); // A塔
var BTower = new Stack(); // B塔
var CTower = new Stack(); // C塔 (目标塔)
var TIER = 4; // 层数

for(var i = TIER; i > 0; i--){
    ATower.push(i);
}

function Hanoi(n, from, to, buffer){
    if(n > 0){
        Hanoi(n - 1, from, buffer, to);  // 所有不符合要求的盘（n-1），从A塔统一移到B塔缓存
        to.push(from.pop()); // 将符合的盘（n）移动到C塔
        Hanoi(n - 1, buffer, to, from); // 把B塔缓存的盘全部移动到C塔
    }
}

Hanoi(ATower.read().length, ATower, CTower, BTower);

汉诺塔的重点，还是靠递归去实现。把一个大问题，通过递归，不断分拆为更小的问题。然后，集中精力解决小问题即可。

三、小结

不知不觉，写得有点多ORZ。
后面章节的参考链接，还是推荐看看。也许配合本文，你会有更深的理解。

参考

[1] 中缀表示法
[2] 后缀表示法
[3] 调度场算法
[4] 汉诺塔

喜欢我文章的朋友，可以通过以下方式关注我：

wall的个人博客

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107368.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2022年4月20日 下午1:00
下一篇 2022年4月20日 下午1:20


相关推荐

  • ABAP开发关键字总结

    ABAP开发关键字总结

    ABAP开发关键字总结关健字是语句的第一个词 它决定整个语句的意义 有四种不同类型的关健字 nbsp nbsp 1 说明性关健字 nbsp nbsp nbsp nbsp nbsp TYPES DATA TABLES 这些关健字说明定义数据类型或者说明程序可以访问的数据对象 nbsp nbsp nbsp nbsp nbsp TYPES nbsp nbsp nbsp nbsp 用来定义数据结构类型 nbsp nbsp nbsp nbsp nbsp nbsp DATA nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp 用来定义数据结构对象 nbsp nbsp nbsp nbsp nbsp nbsp TABLES nbsp 用来声明 Table nbsp

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月19日
    1
  • JSTL —[什么是JSTL,JSTL标签]

    JSTL —[什么是JSTL,JSTL标签]

    JSTL —[什么是JSTL,JSTL标签]文章目录什么是 JSTLJSTL 环境搭建什么是 JSTLJSP 标准标识库 使用 JSTL 可实现 JSP 页面的逻辑处理 可用于编写各种动态 JSP 页面 JSTL Javaserverpa 即 JSP 标准标签库 是由 JCP Javacommunit 所制定的标准规范 它主要提供给 JavaWeb 开发人员一个标准通用的标签库 并由 Apache 的 Jakarta 小组来维护 开发人员可以利用这些标签取代 JSP 页面上的 Java 代码 从而提高程序的可

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月17日
    2
  • Matlab 直方图均衡化

    Matlab 直方图均衡化

    Matlab 直方图均衡化Matlab 直方图均衡化 1 直方图均衡化介绍直方图均衡化是图像增强的一种基本方法 可提高图像的对比度 即 将较窄的图像灰度范围以一定规则拉伸至较大 整个灰度级范围内 的范围 目的是在得到在整个灰度级范围内具有均匀分布的图像 实现步骤如下 读入图像对每个通道分别统计像素值 0 255 出现的次数 对每个通道分别求像素值 0 255 出现的概率 得到概率直方图 对每个通道分别求像素值

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月26日
    2
  • R假设检验之Bartlett球形检验（Bartlett’s Test of Sphericity）

    R假设检验之Bartlett球形检验（Bartlett’s Test of Sphericity）

    R假设检验之Bartlett球形检验（Bartlett’s Test of Sphericity）参考：R参考：AGuidetoBartlett’sTestofSphericity

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月18日
    47
  • 各种有趣vbs，bat脚本[通俗易懂]

    各种有趣vbs，bat脚本[通俗易懂]

    各种有趣vbs，bat脚本[通俗易懂]短信轰炸.vbs门罗币挖矿.vbs开机自启.vbs开3389+非net创建管理用户+Shift后门+自删除脚本.vbs去密码.vbs清除3389远程桌面连接痕迹.bat清除日志.bat

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月5日
    13
  • 一维数组当成二维使用[通俗易懂]

    一维数组当成二维使用[通俗易懂]

    一维数组当成二维使用

    全栈程序员-站长的头像 全栈程序员-站长
    2022年1月31日
    40

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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