堆棧的應用——用JavaScript描述數據結構

Hydrogen 發布于2019-08-23 10:54 / 3404人閱讀

摘要：一實現一個棧類基于堆棧的特性，可以用數組做線性表進行存儲。出棧出棧同樣是利用數組的方法，在數組尾部推出數據。聚合最后，將所有功能聚合后，如下所示，一個堆棧的數據結構就搞定了。堆棧的經典算法應用，首推就是漢諾塔。

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。

一、實現一個棧類Stack

基于堆棧的特性，可以用數組做線性表進行存儲。
初始化Stack類的結構如下：

function Stack(){
    this.space = [];
}

Stack.prototype = {
    constructor: Stack,
    /* 接口code */
};

接下來，就是在原型上，對入棧、出棧、清空棧、讀取棧頂、讀取整個棧數據這幾個接口的實現。
Stack類默認以數組頭部做棧底，尾部做棧頂。

1.1 入棧 push

入?？梢岳胘s數組的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)的求值。

進入主題前，有必要先了解以下的數學理論：

中綴表示法（或中綴記法）是一個通用的算術或邏輯公式表示方法，操作符是以中綴形式處于操作數的中間（例：3 + 4）。

逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式，在逆波蘭記法中，所有操作符置于操作數的后面，因此也被稱為后綴表示法。逆波蘭記法不需要括號來標識操作符的優先級。

常規中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5 +”

調度場算法（Shunting Yard Algorithm）是一個用于將中綴表達式轉換為后綴表達式的經典算法，由艾茲格·迪杰斯特拉引入，因其操作類似于火車編組場而得名。

提前說明，這只是簡單版實現。所以規定有兩個：

數字要求為整數

不允許表達式中出現多余的空格

實現代碼如下：

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;
    }
}

實現思路：

采用調度場算法，對中綴表達式進行讀取，對結果進行合理運算。

臨界點采用operatorStack.readTop() !== "undefined"進行判定。有些書采用#做結束標志，個人覺得有點累贅。

將字符串表達式用split進行拆分，然后進行遍歷讀取，壓入堆棧。有提前要計算結果的，進行對應的出棧處理。

將計算部分結果的方法，封裝為獨立的方法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 桿：

每次只能移動一個圓盤；

大盤不能疊在小盤上面。

堆棧的經典算法應用，首推就是漢諾塔。

理解該算法，要注意以下幾點：

不要深究每次的移動，要抽象理解

第一步：所有不符合要求的盤，從A塔統一移到B塔緩存

第二步：將符合的盤移動到C塔

第三步：把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] 漢諾塔

喜歡我文章的朋友，可以通過以下方式關注我：

「star」 或 「watch」 我的GitHub blog

RSS訂閱我的個人博客：王先生的基地

GPU云服務器云服務器描述人工智能在生活中應用的場景 javascript堆棧 javascript的應用數據存儲的描述

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/96804.html

React系列——React Fiber 架構介紹資料匯總（翻譯+中文資料）

摘要：它的主體特征是增量渲染能夠將渲染工作分割成塊，并將其分散到多個幀中。實際上，這樣做可能會造成浪費，導致幀丟失并降低用戶體驗。當一個函數被執行時，一個新的堆?？蚣鼙惶砑拥蕉褩Ｖ?。該堆棧框表示由該函數執行的工作。原文 react-fiber-architecture 介紹 React Fibre是React核心算法正在進行的重新實現。它是React團隊兩年多的研究成果。 React ...

taohonghui 2019-08-22 13:48 評論0 收藏0
搞懂JavaScript引擎運行原理

摘要：同步一次執行一件事，同步引擎一次只執行一行，是同步的。調用函數將其推入堆棧并從函數返回將其彈出堆棧。執行上下文當函數放入到調用堆棧時由創建的環境。執行結果它會立即被推到回調隊列，但它仍然會等待調用堆棧為空才會執行。為了保證可讀性，本文采用意譯而非直譯。想閱讀更多優質文章請猛戳GitHub博客,一年百來篇優質文章等著你！一些名詞 JS引擎 — 一個讀取代碼并運行的引擎，沒有單一的J...

lastSeries 2019-08-23 18:15 評論0 收藏0
你所不知道的JavaScript數組

摘要：原始緩沖區的創建通過這個構造函數可以創建一個原始緩沖區從控制臺可以看到實例擁有一個的屬性，用于獲取的，一個只有以及支持的方法，用于對長度進行截取操作。所有數組類型的長度均固定。本文同步自我的博客園：http://www.cnblogs.com/hustskyking/ 相信每一個 javascript 學習者，都會去了解 JS 的各種基本數據類型，數組就是數據的組合，這是一個很基本...

KnewOne 2019-08-19 14:35 評論0 收藏0
Emscripten教程之如何調試代碼（六）

摘要：值啟用了更詳細的堆棧保護檢查，它以犧牲一些性能的代價提供更精確的。這種可以由任何類型的編碼錯誤引起，但表現為函數指針錯誤，因為在運行時的預期表中無法找到函數。翻譯：云荒杯傾本文是Emscripten-WebAssembly專欄系列文章之一，更多文章請查看專欄。也可以去作者的博客閱讀文章。歡迎加入Wasm和emscripten技術交流群，群聊號碼：939206522。調試Emscri...

cod7ce 2019-08-22 11:12 評論0 收藏0

發表評論

登陸后可評論

0條評論

Hydrogen

男|高級講師

我要關注我要私信

TA的文章

tensorflow正則化

閱讀 2999·2023-04-26 00:23
華為鴻蒙 HarmonyOS 將推出數字人民幣原子化服務：支持收付款，卡片一鍵流轉到智能手表

閱讀 3410·2021-09-13 10:28
搬瓦工VPS：DC2機房CN2 VPS整理，電信雙程CN2 GT，聯通/移動雙程直連

閱讀 2195·2021-08-31 14:18
記美國面試經驗，前端開發，提前預告，目前已經進背調了

閱讀 2897·2019-08-30 15:54
jQuery帶次數帶彈窗的大轉盤抽獎代碼（支持h5）

閱讀 1953·2019-08-30 15:43
如何居中一個元素（終結版）

閱讀 1289·2019-08-29 16:56
NPM酷庫：classnames 快速組合CSS類

閱讀 2813·2019-08-29 14:16
Y分鐘學CSS

閱讀 2066·2019-08-28 17:51

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

堆棧的應用——用JavaScript描述數據結構

相關文章

React系列——React Fiber 架構介紹資料匯總（翻譯+中文資料）

**搞懂JavaScript引擎運行原理**

**你所不知道的JavaScript數組**

Emscripten教程之如何調試代碼（六）

發表評論

0條評論

Hydrogen

男|高級講師

TA的文章

tensorflow正則化

華為鴻蒙 HarmonyOS 將推出數字人民幣原子化服務：支持收付款，卡片一鍵流轉到智能手表

搬瓦工VPS：DC2機房CN2 VPS整理，電信雙程CN2 GT，聯通/移動雙程直連

記美國面試經驗，前端開發，提前預告，目前已經進背調了

jQuery帶次數帶彈窗的大轉盤抽獎代碼（支持h5）

如何居中一個元素（終結版）

NPM酷庫：classnames 快速組合CSS類

Y分鐘學CSS

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

堆棧的應用——用JavaScript描述數據結構

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！