Javascript常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么

這篇文章主要講解了“Javascript常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Javascript常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么”吧！

1. Stack(棧)

Stack的特點是后進先出(last in first  out)。生活中常見的Stack的例子比如一摞書，你最后放上去的那本你之后會最先拿走;又比如瀏覽器的訪問歷史，當(dāng)點擊返回按鈕，最后訪問的網(wǎng)站最先從歷史記錄中彈出。

1. Stack一般具備以下方法：

2. push：將一個元素推入棧頂

3. pop：移除棧頂元素，并返回被移除的元素

4. peek：返回棧頂元素

5. length：返回棧中元素的個數(shù)

Javascript的Array天生具備了Stack的特性，但我們也可以從頭實現(xiàn)一個 Stack類：

function Stack() {   this.count = 0;   this.storage = {};    this.push = function (value) {     this.storage[this.count] = value;     this.count++;   }    this.pop = function () {     if (this.count === 0) {       return undefined;     }     this.count--;     var result = this.storage[this.count];     delete this.storage[this.count];     return result;   }    this.peek = function () {     return this.storage[this.count - 1];   }    this.size = function () {     return this.count;   } }

2. Queue(隊列)

Queue和Stack有一些類似，不同的是Stack是先進后出，而Queue是先進先出。Queue在生活中的例子比如排隊上公交，排在第一個的總是最先上車;又比如打印機的打印隊列，排在前面的最先打印。

• Queue一般具有以下常見方法：

• enqueue：入列，向隊列尾部增加一個元素

• dequeue：出列，移除隊列頭部的一個元素并返回被移除的元素

• front：獲取隊列的第一個元素

• isEmpty：判斷隊列是否為空

• size：獲取隊列中元素的個數(shù)

Javascript中的Array已經(jīng)具備了Queue的一些特性，所以我們可以借助Array實現(xiàn)一個Queue類型：

function Queue() {   var collection = [];    this.print = function () {     console.log(collection);   }    this.enqueue = function (element) {     collection.push(element);   }    this.dequeue = function () {     return collection.shift();   }    this.front = function () {     return collection[0];   }    this.isEmpty = function () {     return collection.length === 0;   }    this.size = function () {     return collection.length;   } }

Priority Queue(優(yōu)先隊列)

Queue還有個升級版本，給每個元素賦予優(yōu)先級，優(yōu)先級高的元素入列時將排到低優(yōu)先級元素之前。區(qū)別主要是enqueue方法的實現(xiàn)：

function PriorityQueue() {    ...    this.enqueue = function (element) {     if (this.isEmpty()) {       collection.push(element);     } else {       var added = false;       for (var i = 0; i < collection.length; i++) {         if (element[1] < collection[i][1]) {           collection.splice(i, 0, element);           added = true;           break;         }       }       if (!added) {         collection.push(element);       }     }   } }

測試一下：

var pQ = new PriorityQueue();  pQ.enqueue(['gannicus', 3]); pQ.enqueue(['spartacus', 1]); pQ.enqueue(['crixus', 2]); pQ.enqueue(['oenomaus', 4]);  pQ.print();

結(jié)果：

[   [ 'spartacus', 1 ],   [ 'crixus', 2 ],   [ 'gannicus', 3 ],   [ 'oenomaus', 4 ] ]

3. Linked List(鏈表)

顧名思義，鏈表是一種鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，鏈上的每個節(jié)點包含兩種信息：節(jié)點本身的數(shù)據(jù)和指向下一個節(jié)點的指針。鏈表和傳統(tǒng)的數(shù)組都是線性的數(shù)據(jù)結(jié)構(gòu)，存儲的都是一個序列的數(shù)據(jù)，但也有很多區(qū)別，如下表：

一個單向鏈表通常具有以下方法：

1. size：返回鏈表中節(jié)點的個數(shù)

2. head：返回鏈表中的頭部元素

3. add：向鏈表尾部增加一個節(jié)點

4. remove：刪除某個節(jié)點

5. indexOf：返回某個節(jié)點的index

6. elementAt：返回某個index處的節(jié)點

7. addAt：在某個index處插入一個節(jié)點

8. removeAt：刪除某個index處的節(jié)點

單向鏈表的Javascript實現(xiàn)：

/**  * 鏈表中的節(jié)點   */ function Node(element) {   // 節(jié)點中的數(shù)據(jù)   this.element = element;   // 指向下一個節(jié)點的指針   this.next = null; }  function LinkedList() {   var length = 0;   var head = null;    this.size = function () {     return length;   }    this.head = function () {     return head;   }    this.add = function (element) {     var node = new Node(element);     if (head == null) {       head = node;     } else {       var currentNode = head;        while (currentNode.next) {         currentNode = currentNode.next;       }        currentNode.next = node;     }     length++;   }    this.remove = function (element) {     var currentNode = head;     var previousNode;     if (currentNode.element === element) {       head = currentNode.next;     } else {       while (currentNode.element !== element) {         previousNode = currentNode;         currentNode = currentNode.next;       }       previousNode.next = currentNode.next;     }     length--;   }    this.isEmpty = function () {     return length === 0;   }    this.indexOf = function (element) {     var currentNode = head;     var index = -1;     while (currentNode) {       index++;       if (currentNode.element === element) {         return index;       }       currentNode = currentNode.next;     }      return -1;   }    this.elementAt = function (index) {     var currentNode = head;     var count = 0;     while (count < index) {       count++;       currentNode = currentNode.next;     }     return currentNode.element;   }    this.addAt = function (index, element) {     var node = new Node(element);     var currentNode = head;     var previousNode;     var currentIndex = 0;      if (index > length) {       return false;     }      if (index === 0) {       node.next = currentNode;       head = node;     } else {       while (currentIndex < index) {         currentIndex++;         previousNode = currentNode;         currentNode = currentNode.next;       }       node.next = currentNode;       previousNode.next = node;     }     length++;   }    this.removeAt = function (index) {     var currentNode = head;     var previousNode;     var currentIndex = 0;     if (index < 0 || index >= length) {       return null;     }     if (index === 0) {       head = currentIndex.next;     } else {       while (currentIndex < index) {         currentIndex++;         previousNode = currentNode;         currentNode = currentNode.next;       }       previousNode.next = currentNode.next;     }     length--;     return currentNode.element;   } }

4. Set(集合)

集合是數(shù)學(xué)中的一個基本概念，表示具有某種特性的對象匯總成的集體。在ES6中也引入了集合類型Set，Set和Array有一定程度的相似，不同的是Set中不允許出現(xiàn)重復(fù)的元素而且是無序的。

一個典型的Set應(yīng)該具有以下方法：

1. values：返回集合中的所有元素

2. size：返回集合中元素的個數(shù)

3. has：判斷集合中是否存在某個元素

4. add：向集合中添加元素

5. remove：從集合中移除某個元素

6. union：返回兩個集合的并集

7. intersection：返回兩個集合的交集

8. difference：返回兩個集合的差集

9. subset：判斷一個集合是否為另一個集合的子集

使用Javascript可以將Set進行如下實現(xiàn)，為了區(qū)別于ES6中的Set命名為MySet：

function MySet() {   var collection = [];   this.has = function (element) {     return (collection.indexOf(element) !== -1);   }    this.values = function () {     return collection;   }    this.size = function () {     return collection.length;   }    this.add = function (element) {     if (!this.has(element)) {       collection.push(element);       return true;     }     return false;   }    this.remove = function (element) {     if (this.has(element)) {       index = collection.indexOf(element);       collection.splice(index, 1);       return true;     }     return false;   }    this.union = function (otherSet) {     var unionSet = new MySet();     var firstSet = this.values();     var secondSet = otherSet.values();     firstSet.forEach(function (e) {       unionSet.add(e);     });     secondSet.forEach(function (e) {       unionSet.add(e);     });     return unionSet;   }    this.intersection = function (otherSet) {     var intersectionSet = new MySet();     var firstSet = this.values();     firstSet.forEach(function (e) {       if (otherSet.has(e)) {         intersectionSet.add(e);       }     });     return intersectionSet;   }    this.difference = function (otherSet) {     var differenceSet = new MySet();     var firstSet = this.values();     firstSet.forEach(function (e) {       if (!otherSet.has(e)) {         differenceSet.add(e);       }     });     return differenceSet;   }    this.subset = function (otherSet) {     var firstSet = this.values();     return firstSet.every(function (value) {       return otherSet.has(value);     });   } }

5. Hash Table(哈希表/散列表)

Hash Table是一種用于存儲鍵值對(key value pair)的數(shù)據(jù)結(jié)構(gòu)，因為Hash  Table根據(jù)key查詢value的速度很快，所以它常用于實現(xiàn)Map、Dictinary、Object等數(shù)據(jù)結(jié)構(gòu)。如上圖所示，Hash  Table內(nèi)部使用一個hash函數(shù)將傳入的鍵轉(zhuǎn)換成一串?dāng)?shù)字，而這串?dāng)?shù)字將作為鍵值對實際的key，通過這個key查詢對應(yīng)的value非?？?，時間復(fù)雜度將達到O(1)。Hash函數(shù)要求相同輸入對應(yīng)的輸出必須相等，而不同輸入對應(yīng)的輸出必須不等，相當(dāng)于對每對數(shù)據(jù)打上唯一的指紋。

一個Hash Table通常具有下列方法：

1. add：增加一組鍵值對

2. remove：刪除一組鍵值對

3. lookup：查找一個鍵對應(yīng)的值

一個簡易版本的Hash Table的Javascript實現(xiàn)：

function hash(string, max) {   var hash = 0;   for (var i = 0; i < string.length; i++) {     hash += string.charCodeAt(i);   }   return hash % max; }  function HashTable() {   let storage = [];   const storageLimit = 4;    this.add = function (key, value) {     var index = hash(key, storageLimit);     if (storage[index] === undefined) {       storage[index] = [         [key, value]       ];     } else {       var inserted = false;       for (var i = 0; i < storage[index].length; i++) {         if (storage[index][i][0] === key) {           storage[index][i][1] = value;           inserted = true;         }       }       if (inserted === false) {         storage[index].push([key, value]);       }     }   }    this.remove = function (key) {     var index = hash(key, storageLimit);     if (storage[index].length === 1 && storage[index][0][0] === key) {       delete storage[index];     } else {       for (var i = 0; i < storage[index]; i++) {         if (storage[index][i][0] === key) {           delete storage[index][i];         }       }     }   }    this.lookup = function (key) {     var index = hash(key, storageLimit);     if (storage[index] === undefined) {       return undefined;     } else {       for (var i = 0; i < storage[index].length; i++) {         if (storage[index][i][0] === key) {           return storage[index][i][1];         }       }     }   } }

6. Tree(樹)

顧名思義，Tree的數(shù)據(jù)結(jié)構(gòu)和自然界中的樹極其相似，有根、樹枝、葉子，如上圖所示。Tree是一種多層數(shù)據(jù)結(jié)構(gòu)，與Array、Stack、Queue相比是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在進行插入和搜索操作時很高效。在描述一個Tree時經(jīng)常會用到下列概念：

1. Root(根)：代表樹的根節(jié)點，根節(jié)點沒有父節(jié)點

2. Parent Node(父節(jié)點)：一個節(jié)點的直接上級節(jié)點，只有一個

3. Child Node(子節(jié)點)：一個節(jié)點的直接下級節(jié)點，可能有多個

4. Siblings(兄弟節(jié)點)：具有相同父節(jié)點的節(jié)點

5. Leaf(葉節(jié)點)：沒有子節(jié)點的節(jié)點

6. Edge(邊)：兩個節(jié)點之間的連接線

7. Path(路徑)：從源節(jié)點到目標(biāo)節(jié)點的連續(xù)邊

8. Height of Node(節(jié)點的高度)：表示節(jié)點與葉節(jié)點之間的最長路徑上邊的個數(shù)

9. Height of Tree(樹的高度)：即根節(jié)點的高度

10. Depth of Node(節(jié)點的深度)：表示從根節(jié)點到該節(jié)點的邊的個數(shù)

11. Degree of Node(節(jié)點的度)：表示子節(jié)點的個數(shù)

我們以二叉查找樹為例，展示樹在Javascript中的實現(xiàn)。在二叉查找樹中，即每個節(jié)點最多只有兩個子節(jié)點，而左側(cè)子節(jié)點小于當(dāng)前節(jié)點，而右側(cè)子節(jié)點大于當(dāng)前節(jié)點，如圖所示：

一個二叉查找樹應(yīng)該具有以下常用方法：

1. add：向樹中插入一個節(jié)點

2. findMin：查找樹中最小的節(jié)點

3. findMax：查找樹中最大的節(jié)點

4. find：查找樹中的某個節(jié)點

5. isPresent：判斷某個節(jié)點在樹中是否存在

6. remove：移除樹中的某個節(jié)點

以下是二叉查找樹的Javascript實現(xiàn)：

class Node {   constructor(data, left = null, right = null) {     this.data = data;     this.left = left;     this.right = right;   } }  class BST {   constructor() {     this.root = null;   }    add(data) {     const node = this.root;     if (node === null) {       this.root = new Node(data);       return;     } else {       const searchTree = function (node) {         if (data < node.data) {           if (node.left === null) {             node.left = new Node(data);             return;           } else if (node.left !== null) {             return searchTree(node.left);           }         } else if (data > node.data) {           if (node.right === null) {             node.right = new Node(data);             return;           } else if (node.right !== null) {             return searchTree(node.right);           }         } else {           return null;         }       };       return searchTree(node);     }   }    findMin() {     let current = this.root;     while (current.left !== null) {       current = current.left;     }     return current.data;   }    findMax() {     let current = this.root;     while (current.right !== null) {       current = current.right;     }     return current.data;   }    find(data) {     let current = this.root;     while (current.data !== data) {       if (data < current.data) {         current = current.left       } else {         current = current.right;       }       if (current === null) {         return null;       }     }     return current;   }    isPresent(data) {     let current = this.root;     while (current) {       if (data === current.data) {         return true;       }       if (data < current.data) {         current = current.left;       } else {         current = current.right;       }     }     return false;   }    remove(data) {     const removeNode = function (node, data) {       if (node == null) {         return null;       }       if (data == node.data) {         // node沒有子節(jié)點         if (node.left == null && node.right == null) {           return null;         }         // node沒有左側(cè)子節(jié)點         if (node.left == null) {           return node.right;         }         // node沒有右側(cè)子節(jié)點         if (node.right == null) {           return node.left;         }         // node有兩個子節(jié)點         var tempNode = node.right;         while (tempNode.left !== null) {           tempNode = tempNode.left;         }         node.data = tempNode.data;         node.right = removeNode(node.right, tempNode.data);         return node;       } else if (data < node.data) {         node.left = removeNode(node.left, data);         return node;       } else {         node.right = removeNode(node.right, data);         return node;       }     }     this.root = removeNode(this.root, data);   } }

測試一下：

const bst = new BST();  bst.add(4); bst.add(2); bst.add(6); bst.add(1); bst.add(3); bst.add(5); bst.add(7); bst.remove(4); console.log(bst.findMin()); console.log(bst.findMax()); bst.remove(7); console.log(bst.findMax()); console.log(bst.isPresent(4));

打印結(jié)果：

1 7 6 false

7. Trie(字典樹，讀音同try)

Trie也可以叫做Prefix  Tree(前綴樹)，也是一種搜索樹。Trie分步驟存儲數(shù)據(jù)，樹中的每個節(jié)點代表一個步驟，trie常用于存儲單詞以便快速查找，比如實現(xiàn)單詞的自動完成功能。  Trie中的每個節(jié)點都包含一個單詞的字母，跟著樹的分支可以可以拼寫出一個完整的單詞，每個節(jié)點還包含一個布爾值表示該節(jié)點是否是單詞的最后一個字母。

Trie一般有以下方法：

• add：向字典樹中增加一個單詞

• isWord：判斷字典樹中是否包含某個單詞

• print：返回字典樹中的所有單詞 

/**  * Trie的節(jié)點  */ function Node() {   this.keys = new Map();   this.end = false;   this.setEnd = function () {     this.end = true;   };   this.isEnd = function () {     return this.end;   } }  function Trie() {   this.root = new Node();    this.add = function (input, node = this.root) {     if (input.length === 0) {       node.setEnd();       return;     } else if (!node.keys.has(input[0])) {       node.keys.set(input[0], new Node());       return this.add(input.substr(1), node.keys.get(input[0]));     } else {       return this.add(input.substr(1), node.keys.get(input[0]));     }   }    this.isWord = function (word) {     let node = this.root;     while (word.length > 1) {       if (!node.keys.has(word[0])) {         return false;       } else {         node = node.keys.get(word[0]);         word = word.substr(1);       }     }     return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;   }    this.print = function () {     let words = new Array();     let search = function (node = this.root, string) {       if (node.keys.size != 0) {         for (let letter of node.keys.keys()) {           search(node.keys.get(letter), string.concat(letter));         }         if (node.isEnd()) {           words.push(string);         }       } else {         string.length > 0 ? words.push(string) : undefined;         return;       }     };     search(this.root, new String());     return words.length > 0 ? words : null;   } }

8. Graph(圖)

Graph是節(jié)點(或頂點)以及它們之間的連接(或邊)的集合。Graph也可以稱為Network(網(wǎng)絡(luò))。根據(jù)節(jié)點之間的連接是否有方向又可以分為Directed  Graph(有向圖)和Undrected Graph(無向圖)。Graph在實際生活中有很多用途，比如：導(dǎo)航軟件計算最佳路徑，社交軟件進行好友推薦等等。

Graph通常有兩種表達方式：

Adjaceny List(鄰接列表)：

鄰接列表可以表示為左側(cè)是節(jié)點的列表，右側(cè)列出它所連接的所有其他節(jié)點。

和 Adjacency Matrix(鄰接矩陣)：

鄰接矩陣用矩陣來表示節(jié)點之間的連接關(guān)系，每行或者每列表示一個節(jié)點，行和列的交叉處的數(shù)字表示節(jié)點之間的關(guān)系：0表示沒用連接，1表示有連接，大于1表示不同的權(quán)重。

訪問Graph中的節(jié)點需要使用遍歷算法，遍歷算法又分為廣度優(yōu)先和深度優(yōu)先，主要用于確定目標(biāo)節(jié)點和根節(jié)點之間的距離，

在Javascript中，Graph可以用一個矩陣(二維數(shù)組)表示，廣度優(yōu)先搜索算法可以實現(xiàn)如下：

function bfs(graph, root) {   var nodesLen = {};    for (var i = 0; i < graph.length; i++) {     nodesLen[i] = Infinity;   }    nodesLen[root] = 0;    var queue = [root];   var current;    while (queue.length != 0) {     current = queue.shift();      var curConnected = graph[current];     var neighborIdx = [];     var idx = curConnected.indexOf(1);     while (idx != -1) {       neighborIdx.push(idx);       idx = curConnected.indexOf(1, idx + 1);     }      for (var j = 0; j < neighborIdx.length; j++) {       if (nodesLen[neighborIdx[j]] == Infinity) {         nodesLen[neighborIdx[j]] = nodesLen[current] + 1;         queue.push(neighborIdx[j]);       }     }   }    return nodesLen; }

測試一下：

var graph = [   [0, 1, 1, 1, 0],   [0, 0, 1, 0, 0],   [1, 1, 0, 0, 0],   [0, 0, 0, 1, 0],   [0, 1, 0, 0, 0] ];  console.log(bfs(graph, 1));

打?。?/p>

{   0: 2,   1: 0,   2: 1,   3: 3,   4: Infinity }

感謝各位的閱讀，以上就是“Javascript常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Javascript常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！