JS数据结构0x002：栈 - HelloWorld开发者社区

0x000 概述

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

0x001 什么是栈

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

push：将数据推入栈中
pop：将数据弹出栈

JS数据结构0x002：栈

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以内任意数量的加法和减法，完整的波兰计算器可以看另一个我的完整实现

效果

JS数据结构0x002：栈

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

<div class="container">
    <input type="text" class="form-control" id="inputText">
    <button class="btn btn-primary mt-1" id="btnCalculate">计算</button>
    <hr>
    <p id="pResult">

    </p>
</div>
<script src="index.js"></script>
<script>
    let $btnCalculate = document.getElementById('btnCalculate')
    let $inputText = document.getElementById('inputText')
    let $pResult = document.getElementById('pResult')
    $btnCalculate.onclick = () => {
        $pResult.textContent=calculate($inputText.value)
    }
</script>

核心的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`