摘要：做前端的同學(xué)不少都是自學(xué)成才或者半路出家，計(jì)算機(jī)基礎(chǔ)的知識(shí)比較薄弱，尤其是數(shù)據(jù)結(jié)構(gòu)和算法這塊，所以今天整理了一下常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)和對(duì)應(yīng)的的實(shí)現(xiàn)，希望能幫助大家完善這方面的知識(shí)體系。

做前端的同學(xué)不少都是自學(xué)成才或者半路出家，計(jì)算機(jī)基礎(chǔ)的知識(shí)比較薄弱，尤其是數(shù)據(jù)結(jié)構(gòu)和算法這塊，所以今天整理了一下常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)和對(duì)應(yīng)的Javascript的實(shí)現(xiàn)，希望能幫助大家完善這方面的知識(shí)體系。

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

Stack一般具備以下方法：

push：將一個(gè)元素推入棧頂

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

peek：返回棧頂元素

length：返回棧中元素的個(gè)數(shù)

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

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;
  }
}

Queue和Stack有一些類(lèi)似，不同的是Stack是先進(jìn)后出，而Queue是先進(jìn)先出。Queue在生活中的例子比如排隊(duì)上公交，排在第一個(gè)的總是最先上車(chē)；又比如打印機(jī)的打印隊(duì)列，排在前面的最先打印。

Queue一般具有以下常見(jiàn)方法：

enqueue：入列，向隊(duì)列尾部增加一個(gè)元素

dequeue：出列，移除隊(duì)列頭部的一個(gè)元素并返回被移除的元素

front：獲取隊(duì)列的第一個(gè)元素

isEmpty：判斷隊(duì)列是否為空

size：獲取隊(duì)列中元素的個(gè)數(shù)

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

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;
  }
}

Queue還有個(gè)升級(jí)版本，給每個(gè)元素賦予優(yōu)先級(jí)，優(yōu)先級(jí)高的元素入列時(shí)將排到低優(yōu)先級(jí)元素之前。區(qū)別主要是enqueue方法的實(shí)現(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);
      }
    }
  }
}

測(cè)試一下：

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 ]
]

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

一個(gè)單向鏈表通常具有以下方法：

size：返回鏈表中節(jié)點(diǎn)的個(gè)數(shù)

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

add：向鏈表尾部增加一個(gè)節(jié)點(diǎn)

remove：刪除某個(gè)節(jié)點(diǎn)

indexOf：返回某個(gè)節(jié)點(diǎn)的index

elementAt：返回某個(gè)index處的節(jié)點(diǎn)

addAt：在某個(gè)index處插入一個(gè)節(jié)點(diǎn)

removeAt：刪除某個(gè)index處的節(jié)點(diǎn)

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

/**
 * 鏈表中的節(jié)點(diǎn) 
 */
function Node(element) {
  // 節(jié)點(diǎn)中的數(shù)據(jù)
  this.element = element;
  // 指向下一個(gè)節(jié)點(diǎn)的指針
  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;
  }
}

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

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

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

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

has：判斷集合中是否存在某個(gè)元素

add：向集合中添加元素

remove：從集合中移除某個(gè)元素

union：返回兩個(gè)集合的并集

intersection：返回兩個(gè)集合的交集

difference：返回兩個(gè)集合的差集

subset：判斷一個(gè)集合是否為另一個(gè)集合的子集

使用Javascript可以將Set進(jìn)行如下實(shí)現(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);
    });
  }
}

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

一個(gè)Hash Table通常具有下列方法：

add：增加一組鍵值對(duì)

remove：刪除一組鍵值對(duì)

lookup：查找一個(gè)鍵對(duì)應(yīng)的值

一個(gè)簡(jiǎn)易版本的Hash Table的Javascript實(shí)現(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];
        }
      }
    }
  }
}

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

Root（根）：代表樹(shù)的根節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)

Parent Node（父節(jié)點(diǎn)）：一個(gè)節(jié)點(diǎn)的直接上級(jí)節(jié)點(diǎn)，只有一個(gè)

Child Node（子節(jié)點(diǎn)）：一個(gè)節(jié)點(diǎn)的直接下級(jí)節(jié)點(diǎn)，可能有多個(gè)

Siblings（兄弟節(jié)點(diǎn)）：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)

Leaf（葉節(jié)點(diǎn)）：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)

Edge（邊）：兩個(gè)節(jié)點(diǎn)之間的連接線

Path（路徑）：從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的連續(xù)邊

Height of Node（節(jié)點(diǎn)的高度）：表示節(jié)點(diǎn)與葉節(jié)點(diǎn)之間的最長(zhǎng)路徑上邊的個(gè)數(shù)

Height of Tree（樹(shù)的高度）：即根節(jié)點(diǎn)的高度

Depth of Node（節(jié)點(diǎn)的深度）：表示從根節(jié)點(diǎn)到該節(jié)點(diǎn)的邊的個(gè)數(shù)

Degree of Node（節(jié)點(diǎn)的度）：表示子節(jié)點(diǎn)的個(gè)數(shù)

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

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

add：向樹(shù)中插入一個(gè)節(jié)點(diǎn)

findMin：查找樹(shù)中最小的節(jié)點(diǎn)

findMax：查找樹(shù)中最大的節(jié)點(diǎn)

find：查找樹(shù)中的某個(gè)節(jié)點(diǎn)

isPresent：判斷某個(gè)節(jié)點(diǎn)在樹(shù)中是否存在

remove：移除樹(shù)中的某個(gè)節(jié)點(diǎn)

以下是二叉查找樹(shù)的Javascript實(shí)現(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沒(méi)有子節(jié)點(diǎn)
        if (node.left == null && node.right == null) {
          return null;
        }
        // node沒(méi)有左側(cè)子節(jié)點(diǎn)
        if (node.left == null) {
          return node.right;
        }
        // node沒(méi)有右側(cè)子節(jié)點(diǎn)
        if (node.right == null) {
          return node.left;
        }
        // node有兩個(gè)子節(jié)點(diǎn)
        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);
  }
}

測(cè)試一下：

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

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

Trie一般有以下方法：

add：向字典樹(shù)中增加一個(gè)單詞

isWord：判斷字典樹(shù)中是否包含某個(gè)單詞

print：返回字典樹(shù)中的所有單詞

/**
 * Trie的節(jié)點(diǎn)
 */
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;
  }
}

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

Graph通常有兩種表達(dá)方式：

Adjaceny List（鄰接列表）：

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

和 Adjacency Matrix（鄰接矩陣）：

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

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

在Javascript中，Graph可以用一個(gè)矩陣（二維數(shù)組）表示，廣度優(yōu)先搜索算法可以實(shí)現(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;
}

測(cè)試一下：

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));

打印：

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

最后，推薦大家使用Fundebug，一款很好用的BUG監(jiān)控工具~

本文旨在向廣大前端同學(xué)普及常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，本人對(duì)這一領(lǐng)域也只是初窺門(mén)徑，說(shuō)的有差池的地方歡迎指出。也希望大家能打牢基礎(chǔ)，在這條路上走的更高更遠(yuǎn)！