上篇數(shù)據(jù)結(jié)構(gòu)那些事（一）已經(jīng)介紹了數(shù)組，列表和棧。這篇我們將介紹隊列，鏈表，字典。

隊列也是一種列表，遵循先進(jìn)先出的規(guī)則。

隊列的兩種主要操作是：向隊列中插入新元素和刪除隊列中的元素。入隊操作在隊尾插入新元素，出隊在隊頭刪除元素。 接下來，我們來設(shè)計一個隊列Queue類：

function Queue(){this.dataStore = [];//存儲this.enqueue = enqueue;//入隊this.dequeue = dequeue;//出隊this.front = front;//隊首this.back = back;//隊尾this.toString = toString;//顯示隊列元素this.empty = empty;//清除 } 復(fù)制代碼

實現(xiàn)上面的操作方法：

function enqueue(e){this.dataStore.push(e); } function dequeue(e){this.dataStore.shift(e) } function front(){return this.dataStore[0] } function back(){return this.dataStore[this.dataStore.length - 1] } function toString(){let retStr = "";for (let i = 0; i<this.dataStore.length; ++i){retStr += this.dataStore[i] + "\n";}return retStr; } function empty(){if(this.dataStore.length === 0){return true;}else{return false;} } 復(fù)制代碼

上面我們實現(xiàn)了一個基礎(chǔ)的隊列。但現(xiàn)實生活中，可能會出現(xiàn)類似軍人優(yōu)先，重病患優(yōu)先這樣的場景，那樣我們上面的隊列就無法滿足了。這時，我們需要一個優(yōu)先隊列。 從優(yōu)先隊列中刪除元素時，需要考慮優(yōu)先權(quán)的限制。我們來定義一下存儲在隊列中的元素：

function Person(name, code){this.name = name;this.code = code; //表示優(yōu)先級，越小優(yōu)先級越高 } 復(fù)制代碼

現(xiàn)在，需要重新定義dequeue()方法。

function dequeue(){let p = this.dataStore[0].code;for(let i =1 ; i < this.dataStore.length; ++i){if(this.dataStore[i].code < p){p = i}}return this.dataStore.splice(p, 1); } 復(fù)制代碼

鏈表：有時候我們使用數(shù)組效率比較低的時候就可以考慮使用鏈表。當(dāng)然，如果你的場景需要隨機(jī)訪問，數(shù)組仍然比鏈表更合適。

鏈表元素依靠相互之間的關(guān)系進(jìn)行引用。遍歷鏈表，就是跟著鏈表，從鏈表的首元素一直走到尾元素，鏈表的尾元素一般指向null。

下圖演示了在eggs后插入cookies操作

下圖演示了刪除操作

從上面的幾張圖，我們能直觀的感受到，鏈表做這些插入和刪除操作比數(shù)組要便捷的多。因為數(shù)組執(zhí)行插入刪除操作時還需要對應(yīng)的改變數(shù)組中其他元素的索引。而鏈表只需要改變對應(yīng)節(jié)點的指向即可完成操作，兩者不可同日而語。

明白了鏈表的好處，接下來我們來設(shè)計實現(xiàn)一個鏈表：

我們設(shè)計的鏈表包含兩個類。Node類用來表示節(jié)點，LinkedList類提供插入，刪除，顯示元素等方法。

function Node(e){this.element = e;this.next = null; } function LList(){this.head = new Node("head");this.find = find; //遍歷鏈表，查找給定數(shù)據(jù)this.findPrev = findPrev; //遍歷鏈表，查找給定數(shù)據(jù)前面一個節(jié)點this.insert = insert; //插入一個節(jié)點this.remove = remove; //刪除this.display = display; //顯示 } 復(fù)制代碼

實現(xiàn)上面的方法：

function find(e){let currNode = this.head;while(currNode.element !== e){currNode = currNode.next;}return currNode; }function insert(newEl, e){let newNode = new Node(newEl);let current = this.find(e);newNode.next = current.next;current.next = newNode; }function display(){let currNode = this.head;while(currNode.next !== null){console.log(currNode.next.element);corrNode = currNode.next;} }function findPrev(e){let currNode = this.head;while(currNode.next !== null && currNode.next.element !== e){currNode = currNode.next;}return currNode; }function remove(e){let prev = this.findPrev(e);if(prev.next !== null){prev.next = prev.next.next;} } 復(fù)制代碼

上面定義的基礎(chǔ)鏈表存在一個問題：很難從后向前遍歷

這時，我們可以考慮實現(xiàn)一個雙向鏈表：

按照上圖的理解：我們先要給Node類增加一個先前連接的屬性

function Node(element) {this.element = element;this.next = null;this.previous = null; } 復(fù)制代碼

我們還要修改對應(yīng)的insert方法，因為他現(xiàn)在需要建立兩個連接

function insert(newElement, item) {var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;newNode.previous = current;current.next = newNode; } 復(fù)制代碼

雙向鏈表的remove()方法比單向鏈表的效率更高，因為不需要查找前驅(qū)節(jié)點了。

function remove(item) {var currNode = this.find(item);if (!(currNode.next == null)) {currNode.previous.next = currNode.next;currNode.next.previous = currNode.previous;currNode.next = null;currNode.previous = null;} } 復(fù)制代碼

還有一種鏈表是循環(huán)鏈表：和單向鏈表類似，唯一的區(qū)別是，在創(chuàng)建循環(huán)列表時，讓其頭結(jié)點的next屬性指向它本身。

創(chuàng)建循環(huán)列表，我們只需要改變一下LList類即可：

function LList() {this.head = new Node("head");this.head.next = this.head; //讓頭結(jié)點的next指向它自己this.find = find;this.insert = insert;this.display = display;this.findPrevious = findPrevious;this.remove = remove; } 復(fù)制代碼

字典：字典是一種以鍵值對形式存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

JavaScript中的Object類就是以字典形式設(shè)計的。所以字典的實現(xiàn)就像對象一樣，感覺實在沒什么值得寫的，這里給一個demo。

function Dictionary(){this.dataStore = new Array(); }function add(key, value){this.dataStore[key] = value; }function find(key){return this.dataStore[key]; }function remove(key){delete this.dataStore[key] }function show(){for( let key in Object.keys(this.dataStore)){console.log(key + this.dataStore[key])} } 復(fù)制代碼

轉(zhuǎn)載于:https://juejin.im/post/5d00b3fff265da1bb67a1121

總結(jié)

以上是生活随笔為你收集整理的数据结构那些事（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。