[ JavaScript ] 數據結構與算法 —— 棧

everfight 發布于2019-08-26 13:31 / 2757人閱讀

摘要：而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

前言

JavaScript是當下最流行的編程語言之一，它可以做很多事情：

數據可視化（D3.js，Three.js，Chart.js）;

移動端應用(React Native,Weex,AppCan,Flutter,Hybrid App,小程序);

服務端(Express.js,Koa2)；

桌面應用(Electron,nw.js);

游戲,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);

等等。。。

而且目前大部分編程語言的高級應用都會用到數據結構與算法以及設計模式。

本篇主要有三部分

什么是棧

棧的實現

棧的應用

源碼地址：https://github.com/yhtx1997/S...

什么是棧 較官方解釋

棧是一種遵從后進先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的
同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

個人理解

上面看不懂？沒關系，接下來我用生活中比較常見的事來解釋。
大家應該都搬過家，旅行，或者上學時住宿，這個過程中都會用到行李箱。

棧：現在這個旅行箱就是我們的棧；

棧里邊的元素：我們往旅行箱放疊好的衣服或其他的東西，這些東西就是棧里邊的元素；

棧底：我們放衣服時都是是先放旅行箱的最底下，不可能說什么東西都沒有就讓它飄著是吧，這個旅行箱最底下衣服在的位置就是棧底

棧頂：相對應的最后放進去的一件衣服的位置就是棧頂；

壓棧：把元素放進去（把衣服放進旅行箱）的動作就是壓棧；

出棧：把元素拿出來（把衣服拿出來）的動作就是出棧；

堆棧溢出：一般是指棧滿了放不下了（旅行箱滿了怎么塞塞不下了）；

后進先出：放衣服時一件一件的放，但是往外拿衣服的時候是先拿放的時候最后放的，最后拿出來的是放的時候最先放的；可能有人拿衣服直接翻到最下邊然后拿出來，這個過程可以看做，先將除了棧底的元素依次出棧并保存，等拿到棧底的元素在依次壓棧，把元素放回去

有序集合：額，就是一個挨著一個，有順序的，一些有相同屬性的東西

棧的實現

添加元素

刪除元素

返回棧頂元素

是否為空

元素數量

清空元素

打印所有元素

class Stack {
    constructor() {
        this.count = 0; // 長度
        this.items = {}; // 棧
    }
    push(element) {
        // 添加元素
    }
    pop() {
        // 刪除元素
    }
    peek() {
        // 返回棧頂元素
    }
    isEmpty() {
        // 是否為空
    }
    size() {
       // 元素數量
    }
    clear() {
       // 清空元素
    }
    toString() {
       // 打印所有元素
    }
}

添加元素

push(element) {
    this.items[this.count] = element;
    this.count++; // 長度加1
}

刪除元素

 pop() {
    if (this.isEmpty()) { // 如果是空直接返回 undefined
        return undefined;
    }
    this.count--;
    let item = this.items[this.count];
    delete this.items[this.count];
    return item
}

返回棧頂元素

peek() {
    if (this.isEmpty()) {
        return undefined;
    }
    return this.items[this.count - 1];
}

是否為空

isEmpty() {
    return this.count === 0;
}

元素數量

size() {
    return this.count;
}

清空元素

clear() {
    this.count = 0;
    this.items = {};
}

打印所有元素

toString() {
    if (this.isEmpty()) {
        return "";
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
        objString = `${objString},${this.items[i]}`;
    }
    return objString;
}

棧的應用

進制轉換

括號匹配檢驗

迷宮求解

進制轉換

棧因為是先進后出，所以如果將一組數據全部壓棧，再出棧并保存每次出棧的元素，這樣一來相當于將這一組元素的順序進行倒序。
十進制轉換二進制的過程就是一個數除以2，取余數，最后將余數結果進行倒序排列。
現在棧可以進行倒序，而進制轉換需要倒序，所以就可以將棧應用到進制的轉換中。
代碼如下：

function DecimalToBinary(number) {
    let stack = new Stack(); // 新建棧
    let rem = 0; // 余數
    let binary = ""; // 結果
    while (number > 0) {
        rem = Math.floor(number % 2); // 取余數
        stack.push(rem); // 將余數壓棧
        number = Math.floor(number / 2); // 去掉余數除以二
    }
    while (!stack.isEmpty()) { // 不為空
        binary += stack.pop(); // 將元素全部出棧
    }
    return binary;
}

括號匹配檢驗

正常括號嵌套是這樣的

{{{[([({()})])]}}}

可以發現，在某個位置分為了左右兩部分，右邊第一個，與左邊最后一個相對應
右邊最后一個與左邊第一個相對應
左側相當于進行了倒序，而倒序就可以用棧來解決

我們可以將所有的左側括號都依次壓入棧中，然后依次判斷右側是否與棧頂元素相匹配
但是相匹配的括號并不相等

可以采用鍵值對的形式存儲一下

{
    "}": "{",
    "]": "[",
    ")": "("
}

或者下標的形式

["{","[","("]
["}","]",")"]

最終代碼如下

function parenthesesChecker(symbols) {
    let stack = new Stack(); // 新建棧
    let balanced = true; // 檢驗括號匹配是否正確
    const leftBrackets = "{[("; // 左側的括號
    const rightBrackets = "}])"; // 右側的括號
    for (let i = 0; i < symbols.length && balanced; i++) {
        current = symbols[i]; // 取單個符號
        if (leftBrackets.indexOf(current) >= 0) { // 如果是左側的括號
            stack.push(current); // 將其壓棧
        } else if (stack.isEmpty()) { // 不是左側括號，且棧為空，括號匹配錯誤
            balancd = false;
        } else { // 不是左側括號，且棧不為空，視為沒有新的左側括號，剩下的都是右側括號
            let top = stack.pop();
            if (!(leftBrackets.indexOf(top) === rightBrackets.indexOf(current))) { 
            // 檢查棧頂（最后一個左側括號）符號在 leftBrackets 的位置以及當前符號在 rightBrackets 的位置，位置相同視為配對成功
                balanced = false;
            }
        }
    }
    
    return balanced; // 返回結果
}

迷宮求解

這個比較復雜，之后會寫個小實例，敬請期待......

GPU云服務器云服務器 javascript全棧視頻 javascript全棧教程 javascript全棧開發 javascript快速全棧開發

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

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

學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0
JavaScript數據結構與算法—— 棧

摘要：棧數據結構棧是一種遵循后進先出原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，叫做棧頂，另一端叫棧底。在棧中，新元素靠近棧頂，舊元素接近棧底。我們可以在數組的任何位置上刪除或者添加元素，但有時候我們還需要在元素的添加或刪除時有更多控制的數據結構，有兩種數據結構類似于數組，但在添加或刪除元素時更為可控，它們就是棧和隊列。本節主要介紹棧。 1.棧數據結構棧是一種遵循后進先出（...

王巖威 2019-08-23 15:11 評論0 收藏0
JavaScript的數據結構與算法（一） —— 棧

摘要：棧是一種遵從后進先出原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾。稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。提供可操作的方法入棧出棧，但是會移掉棧中的數據。棧是一種遵從后進先出(LIFO)原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾。稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都靠近棧底。 javascript提供可操作的...

quietin 2019-08-21 17:12 評論0 收藏0
JavaScript 數據結構與算法之美 - 棧內存與堆內存、淺拷貝與深拷貝

摘要：棧內存與堆內存淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。棧內存與堆內存中的變量分為基本類型和引用類型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想寫好前端，先練好內功。棧內存與堆內存、淺拷貝與深拷貝，可以說是前端程序員的內功，要知其然，知其所以然。筆者寫的 JavaScrip...

dailybird 2019-08-23 18:26 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0