JS數據結構0x002：棧

noONE 發布于2019-08-23 12:44 / 2921人閱讀

摘要：概述今天玩得是棧，棧的用處非常廣泛啊，比如函數的調用棧啊，的的的啊，之類的，一坨一坨的。

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

云服務器 GPU云服務器 js技術棧 JS調用棧 js遞歸棧溢出 js數組棧方法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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