堆栈的应用——用JavaScript描述数据结构

Hydrogen 发布于2019-08-23 10:54 / 3396人阅读

摘要：一实现一个栈类基于堆栈的特性，可以用数组做线性表进行存储。出栈出栈同样是利用数组的方法，在数组尾部推出数据。聚合最后，将所有功能聚合后，如下所示，一个堆栈的数据结构就搞定了。堆栈的经典算法应用，首推就是汉诺塔。

栈（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)的求值。

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

中缀表示法（或中缀记法）是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4）。

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

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

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

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

数字要求为整数

不允许表达式中出现多余的空格

实现代码如下：

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;
    }
}

实现思路：

采用调度场算法，对中缀表达式进行读取，对结果进行合理运算。

临界点采用operatorStack.readTop() !== "undefined"进行判定。有些书采用#做结束标志，个人觉得有点累赘。

将字符串表达式用split进行拆分，然后进行遍历读取，压入堆栈。有提前要计算结果的，进行对应的出栈处理。

将计算部分结果的方法，封装为独立的方法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 杆：

每次只能移动一个圆盘；

大盘不能叠在小盘上面。

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

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

不要深究每次的移动，要抽象理解

第一步：所有不符合要求的盘，从A塔统一移到B塔缓存

第二步：将符合的盘移动到C塔

第三步：把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] 汉诺塔

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

「star」 或 「watch」 我的GitHub blog

RSS订阅我的个人博客：王先生的基地

云服务器 GPU云服务器描述人工智能在生活中应用的场景 javascript堆栈 javascript的应用数据存储的描述

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

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

React系列——React Fiber 架构介绍资料汇总（翻译+中文资料）

摘要：它的主体特征是增量渲染能够将渲染工作分割成块，并将其分散到多个帧中。实际上，这样做可能会造成浪费，导致帧丢失并降低用户体验。当一个函数被执行时，一个新的堆栈框架被添加到堆栈中。该堆栈框表示由该函数执行的工作。原文 react-fiber-architecture 介绍 React Fibre是React核心算法正在进行的重新实现。它是React团队两年多的研究成果。 React ...

taohonghui 2019-08-22 13:48 评论0 收藏0
搞懂JavaScript引擎运行原理

摘要：同步一次执行一件事，同步引擎一次只执行一行，是同步的。调用函数将其推入堆栈并从函数返回将其弹出堆栈。执行上下文当函数放入到调用堆栈时由创建的环境。执行结果它会立即被推到回调队列，但它仍然会等待调用堆栈为空才会执行。为了保证可读性，本文采用意译而非直译。想阅读更多优质文章请猛戳GitHub博客,一年百来篇优质文章等着你！一些名词 JS引擎 — 一个读取代码并运行的引擎，没有单一的J...

lastSeries 2019-08-23 18:15 评论0 收藏0
你所不知道的JavaScript数组

摘要：原始缓冲区的创建通过这个构造函数可以创建一个原始缓冲区从控制台可以看到实例拥有一个的属性，用于获取的，一个只有以及支持的方法，用于对长度进行截取操作。所有数组类型的长度均固定。本文同步自我的博客园：http://www.cnblogs.com/hustskyking/ 相信每一个 javascript 学习者，都会去了解 JS 的各种基本数据类型，数组就是数据的组合，这是一个很基本...

KnewOne 2019-08-19 14:35 评论0 收藏0
Emscripten教程之如何调试代码（六）

摘要：值启用了更详细的堆栈保护检查，它以牺牲一些性能的代价提供更精确的。这种可以由任何类型的编码错误引起，但表现为函数指针错误，因为在运行时的预期表中无法找到函数。翻译：云荒杯倾本文是Emscripten-WebAssembly专栏系列文章之一，更多文章请查看专栏。也可以去作者的博客阅读文章。欢迎加入Wasm和emscripten技术交流群，群聊号码：939206522。调试Emscri...

cod7ce 2019-08-22 11:12 评论0 收藏0