JS数据结构0x002：栈

noONE 发布于2019-08-23 12:44 / 2813人阅读

摘要：概述今天玩得是栈，栈的用处非常广泛啊，比如函数的调用栈啊，的的的啊，之类的，一坨一坨的。

0x000 概述

今天玩得是栈，栈的用处非常广泛啊，比如函数的调用栈啊，h5的history的state的api啊，之类的，一坨一坨的。

0x001 什么是栈

栈就是一个后入先出的数组，并且这个数组只能从一端进来，再从这一端出去，就像是放在长筒纸盒里面的羽毛球，他只有两个动作

push：将数据推入栈中

pop：将数据弹出栈

0x002 初始化

依旧使用数组来模拟栈

function init() {
    return []
}

0x003 推入

function push(stack, data) {
    stack.push(data)
}

0x004 弹出

function pop(stack) {
    return stack.pop()
}

0x005 使用

function main() {
    let stack = init() // stack: []
    stack = push(stack, 1) // stack: [1]
    stack = push(stack, 2) // stack: [1, 2]
    stack = push(stack, 3) // stack: [1, 2, 3]
    pop(stack) // 3 stack:[1, 2]
    pop(stack) // 2 stack:[1]
    pop(stack) // 1 stack:[]
}

main()

0x006 注意

平常我们依旧不会这么使用，而是

let stack=[] // []
stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]
stack.pop() // 3
stack.pop() // 2 
stack.pop() // 1

0x007 栗子：10以内的波兰计算器

这是一个中缀转后缀并计算表达式结果的栗子，为了简单只实现10以内任意数量的加法和减法，完整的波兰计算器可以看另一个我的完整实现

效果

页面其实可有可无，这里还是实现了一下

核心的calculate函数

function calculate(input) {
    let tokenStack = input.split("").reverse() 
    let rpnStack = []
    let operationStack = []

    // 第一个循环 
    while (tokenStack.length) {  
        let t = tokenStack.pop()
        if (t.match(/[0-9]/)) {
            rpnStack.push(t)
            continue
        }
        if (t.match(/[+-]/)) {
            while (operationStack.length) {
                rpnStack.push(operationStack.pop())
            }
            operationStack.push(t)
            continue
        }

        throw `error: unknow charactor: ${t}`
    }
    while (operationStack.length) {
        rpnStack.push(operationStack.pop())
    }
    rpnStack = rpnStack.reverse()
    
    
    let resultStack = []
    while (rpnStack.length) {
        let t = rpnStack.pop()+""
        if (t.match(/[0-9]/)) {
            resultStack.push(+t)
            continue
        }
        if (t === "+") {
            let num1 = resultStack.pop()
            let num2 = resultStack.pop()
            rpnStack.push(num2 + num1)
            continue
        }
        if (t === "-") {
            let num1 = resultStack.pop()
            let num2 = resultStack.pop()
            rpnStack.push(num2 - num1)
            continue
        }
    }


    return resultStack[0]
}

说明
这个函数中用了4个栈

tokenStack：用来存放词素

operationStack：在中缀转后缀的过程中临时存放操作符

rpnStack：存放后缀表达式

resultStack：存放计算过程中的数字

过程说明

将表达式分割成数组，但是不是我们要的顺序，所以reverse一下：1+2-3+4-5->["5","-","4","+","3","-","2","+,"1"]

上面分割之后是中缀表达式，这里要转化为后缀表达式：["5","-","4","+","3","-","2","+,"1"]->["1","2","+","3","-","4","+","5","-"]

将后缀表达式元素取出，如果是数组，就推入resultStack,如果是+、-，就从resultStack中取出数按符号做操作，将结果再推入resultStack，直到rpnStack为空：["1","2","+","3","-","4","+","5","-"]->-1`

0x008 资源

源代码：https://github.com/followWinter/data-structure

云服务器混合云 js技术栈 JS调用栈 js递归栈溢出 js数组栈方法

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

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

React入门0x002: jsx

摘要：概述也是，如是说。属性集合，比如等属性对应，是关键词，所以用代替，也可以是自定义的属性。形式送方外上人送上人孤云将野鹤，岂向人间住。莫买沃洲山，时人已知处。 0x000 概述 jsx也是js，如是说。 0x001 语法在上文React入门0x001-环境配置和 helloworld中，出现了一句奇怪的代码： Hello, world! 这在html中没有任何问题，但问题是他出现在...

hedzr 2019-08-26 12:17 评论0 收藏0
es6基础0x002：var、let、const、块级作用域、暂存死区

摘要：但是如果使用，作用域块级作用域内，在还没使用声明一个变量的时候，访问该变量，将会获得，从作用域开始到语句之间，就是暂存死区。 0x001 var 语法 var varname1 [= value1 [, varname2 [, varname3 ... [, varnameN]]]]; 使用 var a, b=2 // 声明多个变量，可以赋值，也可以不赋值 a=1 // 先声...

scola666 2019-08-23 12:53 评论0 收藏0
JS数据结构0x004：链表

摘要：概述这篇文章是说链表，链表这种数据结构非常普遍，有时候我们根本就没有意识到用的是链表啥是链表链表就是用绳子连起来的酒瓶子，酒就是数据，每个酒瓶子都连着下一个酒瓶子。 0x000 概述这篇文章是说链表，链表这种数据结构非常普遍，有时候我们根本就没有意识到用的是链表 0x001 啥是链表链表就是用绳子连起来的酒瓶子，酒就是数据，每个酒瓶子都连着下一个酒瓶子。 showImg(https...

sumory 2019-08-23 12:47 评论0 收藏0
java笔记0x002：操作符

摘要：算数运算符自增自减关系操作符逻辑操作符直接操作符三元运算符字符串类型转化转化会被舍去转化会被舍去 0x001 算数运算符 int num1 = 1, num2 = 2; System.out.println(num1 + num2); // 3 System.out.println(num1 - num2); // -1 ...

liaoyg8023 2019-08-15 15:47 评论0 收藏0
SpringBoot入门0x002：URL 映射

摘要：概述将某个请求映射到某个方法上这个注解可以加在某个或者某个方法上，如果加在上，则这个中的所有路由映射都将会加上这个前缀下面会有栗子，如果加在方法上，则没有前缀下面也有栗子。 0x000 概述将某个http请求映射到某个方法上 0x001 @RequestMapping 这个注解可以加在某个Controller或者某个方法上，如果加在Controller上，则这个Controller...

jlanglang 2019-08-19 10:48 评论0 收藏0