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

来源:https://www.cnblogs.com/walls/archive/2018/08/10/9452059.html
-Advertisement-
Play Games

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是 僅允許在表的一端進行插入和刪除運算 。這一端被稱為棧頂，相對地，把另一端稱為棧底。 一、實現一個棧類Stack 基於堆棧的特性，可以用數組做線性表進行存儲。 初始化 類的結構如下： 接下來，就是在原型上，對 、`出棧 清空棧 讀取棧頂 讀 ...


棧（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 +”
  3. 調度場演算法（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 漢諾塔

漢諾塔

漢諾塔（港台：河內塔）是根據一個傳說形成的數學問題：
有三根桿子A，B，C。A桿上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 桿：

  1. 每次只能移動一個圓盤；
  2. 大盤不能疊在小盤上面。

4個圓盤的漢諾塔的移動

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

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

  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] 漢諾塔


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 點擊底部input輸入框，彈出的軟鍵盤擋住input（蘋果手機使用第三方輸入法 ）
    測試移動端頁面的時候，偶然發現點擊底部input輸入框時，彈出的虛擬鍵盤偶爾會擋住input輸入框。 輸入框固定在頁面底部，如圖所示： input固定底部設計圖.png 點擊底部input輸入框喚起軟鍵盤時，軟鍵盤擋住輸入框。如圖所示： 點擊input鍵盤擋住圖.png 測試過多台真機發現安卓的手機 ...
  • iOS崩潰日誌ips文件解析
    iOS崩潰日誌ips文件解析 一 簡介 測試組的同事在進行穩定性測試時，通常會遇到一些崩潰，然後他們會將這些崩潰日誌（一般是ips格式的文件）反饋給開發進行分析，但是這些ips文件中的內容通常是如下圖這樣的，都是一些十六進位的堆棧地址，如果僅僅根據這些堆棧地址，我們基本無法做任何事情，連最基本的崩潰 ...
  • 截屏狀態監聽 - iOS
    既接到電話狀態監聽的需求之後再次添加了截屏狀態的監聽,當使用 App 時若用戶執行截屏操作需要對當前狀態進行監聽操作,下麵有兩種方法,其中可以替換截屏的圖片內容(Plan A),也可以彈出提示框(Plan B),廢話不多說步驟如下. 此次分享到此結束,希望內容能對大家實際有所幫助,有什麼不足之處歡迎 ...
  • Android 8.1 源碼_啟動篇（一） -- 深入研究 init
    前言 init進程，它是一個由內核啟動的用戶級進程，當Linux內核啟動之後，運行的第一個進程是init，這個進程是一個守護進程，確切的說，它是Linux系統中用戶控制項的第一個進程，所以它的進程號是1。它的生命周期貫穿整個linux 內核運行的始終， linux中所有其它的進程的共同始祖均為init ...
  • webstorm常用快捷鍵
    1. ctrl + shift + n: 打開工程中的文件，目的是打開當前工程下任意目錄的文件。 2. ctrl + j: 輸出模板 3. ctrl + b: 跳到變數申明處 4. ctrl + alt + T: 圍繞包裹代碼(包括zencoding的Wrap with Abbreviation) ...
  • 【代碼筆記】Web-HTML-標題
    一，效果圖。 二，代碼。 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>html標題</title> </head> <body> <!--標題--> <h1>這是標題h1</h1> <h2>這是標題h2</h2> <h3>這 ...
  • HTML基礎實例
    本節列舉了一些簡單的HTML例子，幫助大家更感性地認識HTML標簽。是不是對一些標簽還不熟悉？別擔心，後面幾個章節會有詳細說明，先跑幾個例子看看效果吧。 HTML文檔相關標簽所有HTML文檔必須以<!DOCTYPE html>聲明開頭。 HTML文檔則以<html>開頭，以</html>結尾。 HT ...
  • 什麼是HTML？
    什麼是HTML？HTML是一種標準的標記語言，用這種語言可以創建web頁面。 HTML是一種超文本標記語言HTML使用一些標記來描述頁面的結構HTML中的元素(elements)是構建頁面的基礎HTML用標簽(tags)代表網頁元素各種不同的標簽(如頭部標簽，表格標簽，圖片標簽)彼此分工又相互組合， ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類