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

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

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

棧

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

看上面這張圖可以大致的知道，棧的幾個(gè)特點(diǎn)：

初始化：

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

棧頂

棧的長(zhǎng)度

push操作：

向棧中添加新的元素

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

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

pop操作：

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

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

如果棧中沒(méi)有數(shù)據(jù)繼續(xù)pop的話，會(huì)拋出underflow的錯(cuò)誤

通過(guò)上面的幾個(gè)特點(diǎn)，來(lái)看一看js如何用代碼實(shí)現(xiàn)一個(gè)棧

    class Stack {
       /**
        * 初始化
        */
        constructor(max = 100) {
            // 存儲(chǔ)空間
            this.data = new Array(max);
            // 棧在最初是化的時(shí)候里面沒(méi)有任何數(shù)據(jù),所以棧頂指向-1
            this.top = -1;
            // ?？臻g的大小
            this.max = max;
        }
        
       /**
        * push操作
        */
        push(x) {
            if(this.top === this.max - 1){
                throw "overflow";
            }
            // push一個(gè)新的數(shù)據(jù)，棧頂?shù)闹赶蛞餐瑫r(shí)像后挪動(dòng)一位，指向最新的數(shù)據(jù)地址
            this.top++;
            // 將新的數(shù)據(jù)添加進(jìn)棧
            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;
        }
        
       /**
        * 獲取棧的長(zhǎng)度
        */
        get length(){
            return this.top + 1
        }
    }

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

最后如果文章有講錯(cuò)或講的不對(duì)的地方，請(qǐng)大家留言更正哈。

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/100515.html

相關(guān)文章

JS 棧

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

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

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

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

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

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

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

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

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

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

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

LeviDing 2019-08-20 18:05 評(píng)論0 收藏0