數(shù)據(jù)結(jié)構(gòu)JavaScript描述（一）

scq000 發(fā)布于2019-08-21 18:18 / 2987人閱讀

摘要：本文主要用實(shí)現(xiàn)一些常用的數(shù)據(jù)結(jié)構(gòu)，并帶上相應(yīng)的講解，本系列中的所有代碼并非所有都由本人編寫，但出于學(xué)習(xí)目的，在此分享出來(lái)并帶上一定的解釋，方便大家學(xué)習(xí)。相應(yīng)的數(shù)據(jù)結(jié)構(gòu)有隊(duì)列棧單鏈表雙向鏈表二叉樹相應(yīng)代碼已上傳地址。

本文主要用JavaScript實(shí)現(xiàn)一些常用的數(shù)據(jù)結(jié)構(gòu)，并帶上相應(yīng)的講解，本系列中的所有代碼并非所有都由本人編寫，但出于學(xué)習(xí)目的，在此分享出來(lái)并帶上一定的解釋，方便大家學(xué)習(xí)。

相應(yīng)的數(shù)據(jù)結(jié)構(gòu)有：

隊(duì)列

棧

單鏈表

雙向鏈表

二叉樹

相應(yīng)代碼已上傳GitHub地址：https://github.com/HolyZheng/...   。

本文先給大家介紹隊(duì)列和棧，其他的在后續(xù)的文章中給大家?guī)?lái)。

隊(duì)列

隊(duì)列 的概念應(yīng)該不用多說(shuō)了吧，一句話：先進(jìn)先出（first in first out），就跟我們平時(shí)排隊(duì)一樣，先排隊(duì)的就先到。

代碼實(shí)現(xiàn)：

/**
 *       使用javascript實(shí)現(xiàn)一個(gè)隊(duì)列
 *       具有enqueue、dequeue、show三個(gè)方法
 */
function Queue () {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.size = function () {
    return this._newestIndex - this._oldestIndex;
}

Queue.prototype.enqueue = function (data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
}

Queue.prototype.dequeue = function () {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;
    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;
        return deletedData;
    }
    return;
}

Queue.prototype.show = function () {
    console.log(this._storage);
}

這個(gè)隊(duì)列主要有三個(gè)方法：enqueue、dequeue、show，分別為入隊(duì)，出隊(duì)，查看隊(duì)列。
enqueue跟show都很簡(jiǎn)單，相信這里不用我來(lái)講，大家一看就能懂，所以就講一下dequeue函數(shù)：

enqueue 函數(shù)：

Queue.prototype.dequeue = function () {
    var oldestIndex = this._oldestIndex,  //記錄隊(duì)頭位置
        newestIndex = this._newestIndex,  //記錄隊(duì)尾位置
        deletedData;                      //記錄要?jiǎng)h除的數(shù)據(jù)，并返回。
    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;
        return deletedData;
    }
    return;
}

刪除元素的時(shí)候，只需要用先判斷隊(duì)列是否為空了，如果不空就用 delete 方法把相應(yīng)的對(duì)象屬性刪除，然后對(duì)頭位置加一就行了。

棧

棧跟隊(duì)列就剛好相反，“先進(jìn)后出”，就像往桶里放球，后面放的在上方，可以先拿到。

代碼實(shí)現(xiàn)：

/**
 *       使用javascript實(shí)現(xiàn)一個(gè)棧
 *       具有push、pop、show三個(gè)方法
 */
function Stack () {
    this._size = 0;
    this._storage = {};
}


Stack.prototype.push = function (data) {
    var size = ++this._size;
    this._storage[size] = data;
}

Stack.prototype.pop = function () {
    var size = this._size;
    var deletedData;
    if (size) {
        deletedData = this._storage[size];
        delete this._storage[size];
        this._size--;
        return deletedData;
    }
}

Stack.prototype.show = function () {
    var len = 1;
    while (len <= this._size) {
        console.log(this._storage[len]);
        len++;
    }
}

var stackA = new Stack();

這個(gè) 棧主要有三個(gè)方法：push、pop、show 三個(gè)方法，同樣我們挑一個(gè)相對(duì)較難的方法來(lái)講一下：

Stack.prototype.pop = function () {
    var size = this._size; //指向棧頭
    var deletedData;
    if (size) {
        deletedData = this._storage[size];
        delete this._storage[size];
        this._size--;
        return deletedData;
    }
}

pop 元素的時(shí)候，先判斷棧是否為空，如果不為空的話，就 delete 掉棧頭的元素，即最上方最先拿到的元素，然后this._size --指向下一個(gè)元素。

總結(jié)

隊(duì)列，先進(jìn)先出，就像我們平時(shí)排隊(duì)

棧，先進(jìn)后出，就像往桶里放球，后放的在上方，可以先拿到

因?yàn)殛?duì)列和棧相對(duì)簡(jiǎn)單，所以本文篇幅比較短，下一篇文章我會(huì)為大家?guī)?lái)難度高一點(diǎn)的 單鏈表 和 雙向鏈表 的代碼實(shí)現(xiàn)和講解，文章也會(huì)相對(duì)詳細(xì)，歡迎大家關(guān)注。