栈的应用,JavaScript描述数据结构,数据结构,逆波兰表示法,汉诺塔

2018-08-10 admin

栈(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] 汉诺塔

原文链接:https://segmentfault.com/a/1190000015951795

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-37668.html

文章标题:栈的应用,JavaScript描述数据结构,数据结构,逆波兰表示法,汉诺塔

相关文章
JavaScript编辑器推荐
主流编辑器有SublimeText,Notepad++,webstorm等,是使用最广泛的编辑器,但也有一些JavaScript编辑器提供有着各自的特性和功能,适应不同人的需求,以下是几款优秀的编辑器,相信你一定能找到自己喜欢的。 1. W...
2015-11-12
js性能优化 如何更快速加载你的JavaScript页面
确保代码尽量简洁 不要什么都依赖JavaScript。不要编写重复性的脚本。要把JavaScript当作糖果工具,只是起到美化作用。别给你的网站添加大量的JavaScript代码。只有必要的时候用一下。只有确实能改善用户体验的时候用一下。 ...
2015-11-12
10个强大的纯CSS3动画案例分享
我们的网页外观主要由CSS控制,编写CSS代码可以任意改变我们的网页布局以及网页内容的样式。CSS3的出现,更是可以让网页增添了不少动画元素,让我们的网页变得更加生动有趣,并且更易于交互。本文分享了10个非常炫酷的CSS3动画案例,希望大家...
2015-11-16
2015年JavaScript或“亲库而远框架”
2014年过去了,作为一个JavaScript开发者很难满怀信心的去“挽回”一个特定的库或技术,即便是强大的Angular,似乎也因为最近的一些事情而动摇。 2014年10月的ng-europe会议上,Angular开发者团队透露了一个关于...
2015-11-12
JavaScript实现PC手机端和嵌入式滑动拼图验证码三种效果
PC和手机端网站滑动拼图验证码效果源码,同时包涵了弹出式Demo,使用ajax形式提交二次验证码所需的验证结果值,嵌入式Demo,使用表单形式提交二次验证所需的验证结果值,移动端手动实现弹出式Demo三种效果 首先要确认前端使用页面,比如...
2017-03-17
JavaScript常用特效chm下载
下载地址:JavaScript常用特效chm下载 对了,如果打开空白,在手册上右键属性解除锁定即可。 ...
2015-11-12
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
12个你未必知道的CSS小知识
虽然CSS并不是一种很复杂的技术,但就算你是一个使用CSS多年的高手,仍然会有很多CSS用法/属性/属性值你从来没使用过,甚至从来没听说过。 1.CSS的color属性并非只能用于文本显示 对于CSS的color属性,相信所有Web开发人员...
2015-11-12
ajax为什么令人惊异?ajax的优缺点
使用Ajax的最大优点,就是能在不更新整个页面的前提下维护数据。这使得Web应用程序更为迅捷地回应用户动作,并避免了在网络上发送那些没有改变的信息。 Ajax不需要任何浏览器插件,但需要用户允许JavaScript在浏览器上执行。就像DHT...
2015-11-12
HTML5的5个不错的开发工具推荐
HTML5规范终于在今年正式定稿,对于从事多年HTML5开发的人员来说绝对是一个重大新闻。数字天堂董事长,DCloud CEO王安也发表了文章,从开发者和用户两个角度分析了HTML对两个人群的优势。其实,关于HTML5的开发工具,我们以往的...
2015-11-12
回到顶部