安科网

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

姜皓

姜皓

2019-06-28

关注 关注
栈（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 汉诺塔

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

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

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

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

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

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

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

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

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

堆栈 数据结构 数组

姜皓

姜皓

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

动图演示：手撸堆栈的两种实现方法！

正式开始之前，先和各位朋友聊聊公众号后期的一些打算，后面的文章计划写一些关于数据结构和算法的内容，原因很简单「底层结构决定上层建筑嘛」，对于框架满天飞的今天，我们不止要学习如何使用框架，更要了解它的原理以及底层数据结构，只有这样我们才能更好的应用它。当然，

omyrobin 2020-09-23

容器管理方面的四大考量

Red Hat的Martin Percival撰文道，兴趣激增证明了容器技术为企业带来的好处。容器让您可以使用整个运行时环境打包和隔离应用程序，这个环境包括运行它所需的所有必要“后端”软件，比如配置文件、依赖项和库。由于Kubernetes的兴起，过去这几

gocuber 2020-07-16

2020年开发运维工具清单：选择开发运维工具堆栈吧

开发运维改革终于成为主流，人们对开发运维工具的欢迎程度暴增。根据谷歌趋势的显示，“开发运维工具”的搜索量稳定增长，且会继续保持增长。由于DevOps包括整个软件开发周期，可供选择的工具很多。但有几种工具的性能已经成熟，可以为几乎所有情况提供广泛的支持。成功

贤时间 2020-07-06

结合中断上下文切换和进程上下文切换分析Linux内核的一般执行过程

调用了 copy_process 函数，复制当前进程产生子进程，并且传入关键参数为子进程设置响应进程上下文。调用 wake_up_new_task 函数，将子进程放入调度队列中，从而有机会 CPU 调度并得以运行。初始化与调度有关的数据结构，调用了sche

hickwu 2020-06-14

结合中断上下文切换和进程上下文切换分析Linux内核一般执行过程

　　系统调用是一种特殊的中断，中断分外部中断和内部中断，内部中断?称为异常，异常?分为故障和陷阱，系统调?但是，一般从用户态进入内核态，是由两种方式触发，第一种是硬件中断，就是当硬件中断信号来到的时候，就会执行这个中断对应的中断服务例程。第二种是用户态程序

xushxbigbear微信 2020-06-12

Servlet 单例多线程详解

Servlet如何处理多个请求访问？Servlet容器默认是采用单实例多线程的方式处理多个请求的：1.当web服务器启动的时候，Servlet就被加载并实例化；2.容器初始化化Servlet主要就是读取配置文件（例如tomcat,可以通过servlet.x

shayuchaor 2020-06-07

git stash

将堆栈中的内容应用到当前目录，不同于git stash pop，该命令不会将内容从堆栈中删除，也就说该命令能够将堆栈的内容多次应用到工作目录中，适应于多个分支的情况

乾坤一碼農 2020-05-19

揭秘AI基础设施堆栈，更快部署AI项目

在这个快速发展的环境中，仅仅评估不断扩大的AI工具和服务生态系统是个重大挑战，这些工具和服务常常是为不同的用户和目的设计的。在英特尔资本公司，这有助于我们确定我们认为将对AI未来产生最大积极影响的投资，但它也有助于开发人员和工程师确定他们需要的资源，以最卓

平凡的程序员 2020-05-07

现代Web开发堆栈工具DevExtreme——增强数据可视化功能

DevExtreme拥有高性能的HTML5 / JavaScript小部件集合，使您可以利用现代Web开发堆栈构建交互式的Web应用程序。从Angular和Reac，到ASP.NET Core或Vue，DevExtreme包含全面的高性能和响应式UI小部件

IT小牛的IT见解 2020-04-30

数据结构--2--stack, heap, queue, tree

ElementType Data[MaxSize];

xhao 2020-03-28

迈向全栈开发，程序员必须知道的19个框架和库

全栈开发是程序员圈子中最炙手可热的话题之一，关于全栈应用程序开发需要掌握哪些技能的讨论从未间断过。全栈开发者是指具有综合能力的开发人员，他们掌握各种技能并使用这些技能来独立完成产品。那么，程序员就需要了解各种堆栈流，包括移动堆栈，Web堆栈或本机应用程序堆

BlueSkyUSC 2020-03-22

JavaScript内部原理：浏览器的内幕

Javascript 是一种奇怪语言，有些人喜欢它，有些人讨厌它。它有许多独特的机制，这些机制在其他流行语言中不存在，也没有对应的机制，还有突出明显的就是代码的执行顺序。了解浏览器环境，它的组成以及它的工作原理会让我们在编写 JS 时更加自信，并为可能发

淼寒儿 2020-03-12

数据结构实验之栈与队列八：栈的基本操作

堆栈具有两种基本操作方式，push 和 pop。push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。首先输入整数t，代表测试的组数，以后是 t 组输入。而后的n行，每行的第一个字符可能是‘P’或者‘O’或者‘A’；

范范 2020-02-26

关于JVM线上故障排查基本操作

对于后端程序员，特别是 Java 程序员来讲，排查线上问题是不可避免的。各种 CPU 飚高，内存溢出，频繁 GC 等等，这些都是令人头疼的问题。那么，遇到这些问题该如何解决呢？首先，出现问题，肯定要先定位问题所在，然后分析问题原因，再然后解决问题，最后进行

渴望就奋力追寻 2020-01-28

【数据结构】【C++】堆栈的实现与应用

堆栈可以认为是具有一定约束的线性表，插入和删除的操作都在栈顶的位置，先进入的元素将在后进入的元素之后取出，与生活中的桶类似，故又称为后入先出表。Stack CreateStack:生成空堆栈，其最大长度为MaxSize；bool IsFull:判断堆栈S是

alicelmx 2020-01-24

c语言基础----堆栈队列链表

堆则是一种经过排序的树形数据结构，常用来实现优先队列，他的特点在于形成某种优先的结构。在计算机经常用到，比如优先队列，或者是优先进程管理。在数据结构中，栈是一种可以实现“先进后出”的存储结构。，an-1），则称 a0为栈底，an-1为栈顶。对栈而言，一般用

Joymine 2020-01-17

0155 简单数据类型和复杂数据类型（含堆栈）

复杂数据类型，首先在栈里面存放地址， 十六进制表示 ，然后这个地址指向堆里面的数据。其操作方式类似于数据结构中的栈；console.log; // 4. 这个输出什么 ?

hitxueliang 2020-01-07

数据结构的深入理解

　　数据结构是组织存储数据，以便我们有效的访问、更改数据。堆栈、队列是计算机中定义最早的数据结构。堆栈是后进先出，队列是先进先出的数据组织和存储形式。lists.append(‘a‘)　　#堆栈添加数据，可以把它理解成一个挤进地铁的人最新进入的认会被挤到最

roseying 2019-12-28

Python实现堆栈和队列详解

python实现堆栈堆栈是一个后进先出的数据结构，其工作方式就像一堆汽车排队进去一个死胡同里面，最先进去的一定是最后出来。我们可以设置一个类，用列表来存放栈中元素的信息，利用列表的append()和pop()方法可以实现栈的出栈pop和入栈push的操作，

cxcxrs 2019-12-21

C语言函数调用

需要注意的是，backtrace_symbols的返回值调用了malloc以分配存储空间，为了防止内存泄露，我们要手动调用free来释放这块内存。

Joymine 2019-12-19
姜皓

姜皓

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号