棧

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

屏幕快照 2018-12-28 下午2.54.16.png

看上面這張圖可以大致的知道，棧的幾個(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ù)地址
  • 如果棧中沒有數(shù)據(jù)繼續(xù)pop的話，會(huì)拋出underflow的錯(cuò)誤

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

    class Stack {
       /**
        * 初始化
        */
        constructor(max = 100) {
            // 存儲(chǔ)空間
            this.data = new Array(max);
            // 棧在最初是化的時(shí)候里面沒有任何數(shù)據(jù),所以棧頂指向-1
            this.top = -1;
            // 棧空間的大小
            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
        }
    }

通過上面的代碼演示，對(duì)于棧應(yīng)該會(huì)有一個(gè)大致的了解，后面會(huì)繼續(xù)介紹其他的數(shù)據(jù)結(jié)構(gòu)，并且可能會(huì)介紹如何使用棧來實(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í)前端的來說還是非常重要。

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