js數(shù)據(jù)結(jié)構(gòu)-棧

Apollo 發(fā)布于2019-08-23 14:22 / 992人閱讀

摘要：棧棧是一種遵循后進先出的數(shù)據(jù)結(jié)構(gòu)，其總共就兩個主要的操作，分別是和。學(xué)習(xí)前端的同學(xué)可能對于數(shù)據(jù)結(jié)構(gòu)和算法復(fù)雜度相對于其他語言的工程師會稍弱一些，但是這些對于一個向深入學(xué)習(xí)前端的來說還是非常重要。

棧

棧是一種遵循后進先出(LIFO)的數(shù)據(jù)結(jié)構(gòu)，其總共就兩個主要的操作，分別是push和pop。

看上面這張圖可以大致的知道，棧的幾個特點：

初始化：

有一塊連續(xù)的存儲空間

棧頂

棧的長度

push操作：

向棧中添加新的元素

棧頂向后挪動一個位置，指向最新的數(shù)據(jù)地址

如果棧滿了繼續(xù)push的化，會拋出overflow的錯誤

pop操作：

返回棧頂數(shù)據(jù)

棧頂向前挪動一個位置，指向前一個數(shù)據(jù)地址

如果棧中沒有數(shù)據(jù)繼續(xù)pop的話，會拋出underflow的錯誤

通過上面的幾個特點，來看一看js如何用代碼實現(xiàn)一個棧

    class Stack {
       /**
        * 初始化
        */
        constructor(max = 100) {
            // 存儲空間
            this.data = new Array(max);
            // 棧在最初是化的時候里面沒有任何數(shù)據(jù),所以棧頂指向-1
            this.top = -1;
            // 棧空間的大小
            this.max = max;
        }
        
       /**
        * push操作
        */
        push(x) {
            if(this.top === this.max - 1){
                throw "overflow";
            }
            // push一個新的數(shù)據(jù)，棧頂?shù)闹赶蛞餐瑫r像后挪動一位，指向最新的數(shù)據(jù)地址
            this.top++;
            // 將新的數(shù)據(jù)添加進棧
            this.data[this.top] = x;
        }
        
       /**
        * pop操作
        */
        pop() {
            if(this.top === -1){
                throw "underflow"
            }
            // 獲得棧頂數(shù)據(jù)
            const x = this.data[this.top];
            this.top--;
            return x;
        }
        
       /**
        * 獲取棧的長度
        */
        get length(){
            return this.top + 1
        }
    }

通過上面的代碼演示，對于棧應(yīng)該會有一個大致的了解，后面會繼續(xù)介紹其他的數(shù)據(jù)結(jié)構(gòu)，并且可能會介紹如何使用棧來實現(xiàn)其他的數(shù)據(jù)結(jié)構(gòu)，以及數(shù)據(jù)結(jié)構(gòu)的一些應(yīng)用。
學(xué)習(xí)前端的同學(xué)可能對于數(shù)據(jù)結(jié)構(gòu)和算法復(fù)雜度相對于其他語言的工程師會稍弱一些，但是這些對于一個向深入學(xué)習(xí)前端的來說還是非常重要。

最后如果文章有講錯或講的不對的地方，請大家留言更正哈。

GPU云服務(wù)器云服務(wù)器 js技術(shù)棧 JS調(diào)用棧 js遞歸棧溢出 js數(shù)組棧方法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100515.html

相關(guān)文章

JS 棧

摘要：棧學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法讀書筆記。棧又名堆棧，是一種遵循后進先出原則的有序集合。新添加或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端稱作棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。棧《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》讀書筆記。棧（stack）又名堆棧，是一種遵循后進先出（LIFO）原則的有序集合。新添加或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端稱作棧底。在棧里，...

Lin_R 2019-08-22 10:35 評論0 收藏0
js 調(diào)用棧機制與ES6尾調(diào)用優(yōu)化介紹

摘要：調(diào)用棧的運行機制機制程序運行到一個函數(shù)，它就會將其添加到調(diào)用棧中，當從這個函數(shù)返回的時候，就會將這個函數(shù)從調(diào)用棧中刪掉。在調(diào)用棧中每個調(diào)用偵都對應(yīng)一個函數(shù)，最上方的調(diào)用幀稱為當前幀，調(diào)用棧是由所有的調(diào)用偵形成的。 showImg(https://segmentfault.com/img/remote/1460000019244497?w=900&h=600); 調(diào)用棧的英文名叫做Cal...

AaronYuan 2019-08-26 13:52 評論0 收藏0
js數(shù)據(jù)結(jié)構(gòu)和算法（二）棧和隊列

摘要：對于棧來說，這個表尾稱為棧的棧頂，相應(yīng)的表頭稱為棧底。棧和隊列的區(qū)別棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。出棧操作出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作。基本概念棧和隊列都是動態(tài)的集合，在棧中，可以去掉的元素是最近插入的哪一個。棧實現(xiàn)了后進先出。在隊列中，可以去掉的元素總是在集合中存在的時間最長的那一個。隊列實現(xiàn)了先進先出的策略。棧的官...

jsummer 2019-08-21 12:30 評論0 收藏0
JS 調(diào)用棧機制與 ES6 尾調(diào)用優(yōu)化介紹

摘要：在調(diào)用棧中每個調(diào)用偵都對應(yīng)一個函數(shù)，最上方的調(diào)用幀稱為當前幀，調(diào)用棧是由所有的調(diào)用偵形成的。我們應(yīng)該在日常的中，有意識的使用的尾調(diào)用優(yōu)化，來減少調(diào)用棧的長度，節(jié)省客戶端內(nèi)存。調(diào)用棧的英文名叫做Call Stack，大家或多或少是有聽過的，但是對于js調(diào)用棧的工作方式以及如何在工作中利用這一特性，大部分人可能沒有進行過更深入的研究，這塊內(nèi)容可以說對我們前端來說就是所謂的基礎(chǔ)知識，咋一看好像用處...

jemygraw 2019-05-22 19:43 評論0 收藏0
你不知道的 JS 錯誤和調(diào)用棧常識

摘要：錯誤堆棧包含了產(chǎn)生該錯誤時完整的調(diào)用棧信息?？偨Y(jié)通過本文的描述，相信你對中的調(diào)用棧對象錯誤堆棧有了清晰的認識，在遇到錯誤的時候不在慌亂。本文首發(fā)知乎專欄：《前端周刊》。全文共 6988 字，讀完需 10 分鐘，速讀需 3 分鐘。通過剖析 JS 中調(diào)用棧的工作機制，講解錯誤拋出、處理的正確姿勢，以及錯誤堆棧的獲取、清理處理方法，希望大家對這個少有人關(guān)注但極其有用的知識點能夠有所理解和掌...

tainzhi 2019-08-21 11:33 評論0 收藏0
js數(shù)據(jù)結(jié)構(gòu)之棧

摘要：向一個棧插入新元素又稱作進棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素從一個棧刪除元素又稱作出棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素...

LeviDing 2019-08-20 18:05 評論0 收藏0