【js4agls】數(shù)據(jù)結(jié)構(gòu)JavaScript描述-棧篇

psychola 發(fā)布于2019-08-19 18:13 / 690人閱讀

摘要：列表項目棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出棧或者彈棧，添加一個元素叫做入棧或者壓棧首先構(gòu)建我們的抽象數(shù)據(jù)類型棧頂元素位置保存數(shù)據(jù)的數(shù)組壓棧出棧查看棧頂元素清空棧棧的長度輸出棧元素描述模擬輸出

列表項目

棧是一種后進(jìn)先出(LIFO)的數(shù)據(jù)結(jié)構(gòu)，我們所能操作的都是棧頂元素，刪除一個棧頂元素叫做出棧或者彈棧，添加一個元素叫做入棧或者壓棧.

ADT

首先構(gòu)建我們的抽象數(shù)據(jù)類型.

Stack
top // 棧頂元素位置
dataStore //保存數(shù)據(jù)的數(shù)組
push // 壓棧
pop // 出棧
peek // 查看棧頂元素
empty // 清空棧
length // 棧的長度
print // 輸出棧元素

Javascript 描述

function Stack () {
    this.top = 0;
    this.dataStore = [];
}
Stack.prototype = {
    constructor: Stack,
    push: function (element) {
        return this.dataStore[this.top++] = element;
    },
    pop: function () {
        return this.dataStore.length ? 
                this.dataStore.splice(--this.top, 1) :
                false;
    },
    peek: function () {
        return this.dataStore[this.top - 1];
    },
    empty: function () {
        this.dataStore.length = 0;    
    },
    length: function () {
        return this.dataStore.length;
    },
    // 模擬輸出棧結(jié)構(gòu)
    print: function () {
        for (var i = this.length() - 1; i >= 0; i--) {
            console.log(this.dataStore[i] + "
");
        }
    }
}

測試

var stack = new Stack();
// 入棧
stack.push("jiavan");
stack.push("jiavan2");
stack.push("jiavan3");
stack.push("jiavan4");

// jiavan4
// jiavan3
// jiavan2
// jiavan
stack.print();

// jiavan4
stack.pop();
// jiavan3
stack.peek();
// 3
stack.top;
// jiavan3
// jiavan2
// jiavan
stack.print();

應(yīng)用

對num數(shù)進(jìn)行n進(jìn)制的轉(zhuǎn)換，大致算法如下：

對num和n進(jìn)行求余和想除取整

將余數(shù)入棧push

回到第一步直至除到值為0

function transformNum(num, base) {
    var res = parseInt(num / base);
    var stack = new Stack();
    stack.push(num % base);
    while (parseInt(res)) {
        stack.push(parseInt(res % base));
        res /= base;
    }
    stack.print();
}

// transformNum(10, 2)， 1010
// transformNum(10, 8)， 12

棧的應(yīng)用還有很多，比如匹配括號以及表達(dá)式求值等等.

系列文章原文地址https://github.com/Jiavan/js4... GitHub repo上有源碼和更好的閱讀體驗，若有錯誤歡迎發(fā)PR，若對你有所幫助也歡迎star!