1. Stack（栈）
Stack 的特点是后进先出（last in first out）。生存中常见的 Stack 的例子比方一摞书，你最初放上去的那本你之后会最先拿走；又比方浏览器的拜访历史，当点击返回按钮，最初拜访的网站最先从历史记录中弹出。
Stack 个别具备以下办法：
- push：将一个元素推入栈顶
- pop：移除栈顶元素，并返回被移除的元素
- peek：返回栈顶元素
- length：返回栈中元素的个数
Javascript 的 Array 天生具备了 Stack 的个性，但咱们也能够从头实现一个 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：获取队列中元素的个数
Javascript 中的 Array 曾经具备了 Queue 的一些个性，所以咱们能够借助 Array 实现一个 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（优先队列）
Queue 还有个降级版本，给每个元素赋予优先级，优先级高的元素入列时将排到低优先级元素之前。区别次要是 enqueue 办法的实现：
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();后果：
[[ 'spartacus', 1],
['crixus', 2],
['gannicus', 3],
['oenomaus', 4]
]3. Linked List（链表）
顾名思义，链表是一种链式数据结构，链上的每个节点蕴含两种信息：节点自身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构，存储的都是一个序列的数据，但也有很多区别，如下表：
一个单向链表通常具备以下办法：
- size：返回链表中节点的个数
- head：返回链表中的头部元素
- add：向链表尾部减少一个节点
- remove：删除某个节点
- indexOf：返回某个节点的 index
- elementAt：返回某个 index 处的节点
- addAt：在某个 index 处插入一个节点
- removeAt：删除某个 index 处的节点
单向链表的 Javascript 实现：
/**
* 链表中的节点
*/
function Node(element) {
// 节点中的数据
this.element = element;
// 指向下一个节点的指针
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（汇合）
汇合是数学中的一个基本概念，示意具备某种个性的对象汇总成的个体。在 ES6 中也引入了汇合类型 Set，Set 和 Array 有肯定水平的类似，不同的是 Set 中不容许呈现反复的元素而且是无序的。
一个典型的 Set 应该具备以下办法：
- values：返回汇合中的所有元素
- size：返回汇合中元素的个数
- has：判断汇合中是否存在某个元素
- add：向汇合中增加元素
- remove：从汇合中移除某个元素
- union：返回两个汇合的并集
- intersection：返回两个汇合的交加
- difference：返回两个汇合的差集
- subset：判断一个汇合是否为另一个汇合的子集
应用 Javascript 能够将 Set 进行如下实现，为了区别于 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）的数据结构，因为 Hash Table 依据 key 查问 value 的速度很快，所以它罕用于实现 Map、Dictinary、Object 等数据结构。如上图所示，Hash Table 外部应用一个 hash 函数将传入的键转换成一串数字，而这串数字将作为键值对理论的 key，通过这个 key 查问对应的 value 十分快，工夫复杂度将达到 O(1)。Hash 函数要求雷同输出对应的输入必须相等，而不同输出对应的输入必须不等，相当于对每对数据打上惟一的指纹。
一个 Hash Table 通常具备下列办法：
- add：减少一组键值对
- remove：删除一组键值对
- lookup：查找一个键对应的值
一个繁难版本的 Hash Table 的 Javascript 实现：
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 的数据结构和自然界中的树极其类似，有根、树枝、叶子，如上图所示。Tree 是一种多层数据结构，与 Array、Stack、Queue 相比是一种非线性的数据结构，在进行插入和搜寻操作时很高效。在形容一个 Tree 时常常会用到下列概念：
- Root（根）：代表树的根节点，根节点没有父节点
- Parent Node（父节点）：一个节点的间接下级节点，只有一个
- Child Node（子节点）：一个节点的间接上级节点，可能有多个
- Siblings（兄弟节点）：具备雷同父节点的节点
- Leaf（叶节点）：没有子节点的节点
- Edge（边）：两个节点之间的连接线
- Path（门路）：从源节点到指标节点的间断边
- Height of Node（节点的高度）：示意节点与叶节点之间的最长门路上边的个数
- Height of Tree（树的高度）：即根节点的高度
- Depth of Node（节点的深度）：示意从根节点到该节点的边的个数
- Degree of Node（节点的度）：示意子节点的个数
咱们以二叉查找树为例，展现树在 Javascript 中的实现。在二叉查找树中，即每个节点最多只有两个子节点，而左侧子节点小于以后节点，而右侧子节点大于以后节点，如图所示：
一个二叉查找树应该具备以下罕用办法：
- add：向树中插入一个节点
- findMin：查找树中最小的节点
- findMax：查找树中最大的节点
- find：查找树中的某个节点
- isPresent：判断某个节点在树中是否存在
- remove：移除树中的某个节点
以下是二叉查找树的 Javascript 实现：
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 没有子节点
if (node.left == null && node.right == null) {return null;}
// node 没有左侧子节点
if (node.left == null) {return node.right;}
// node 没有右侧子节点
if (node.right == null) {return node.left;}
// node 有两个子节点
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));打印后果：
1
7
6
false7. Trie（字典树，读音同 try）
Trie 也能够叫做 Prefix Tree（前缀树），也是一种搜寻树。Trie 分步骤存储数据，树中的每个节点代表一个步骤，trie 罕用于存储单词以便疾速查找，比方实现单词的主动实现性能。Trie 中的每个节点都蕴含一个单词的字母，跟着树的分支能够能够拼写出一个残缺的单词，每个节点还蕴含一个布尔值示意该节点是否是单词的最初一个字母。
Trie 个别有以下办法：
- add：向字典树中减少一个单词
- isWord：判断字典树中是否蕴含某个单词
- print：返回字典树中的所有单词
/**
* Trie 的节点
*/
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 是节点（或顶点）以及它们之间的连贯（或边）的汇合。Graph 也能够称为 Network（网络）。依据节点之间的连贯是否有方向又能够分为 Directed Graph（有向图）和 Undrected Graph（无向图）。Graph 在理论生存中有很多用处，比方：导航软件计算最佳门路，社交软件进行好友举荐等等。
Graph 通常有两种表达方式：
Adjaceny List（邻接列表）：
邻接列表能够示意为左侧是节点的列表，右侧列出它所连贯的所有其余节点。
和 Adjacency Matrix（邻接矩阵）：
邻接矩阵用矩阵来示意节点之间的连贯关系，每行或者每列示意一个节点，行和列的交叉处的数字示意节点之间的关系：0 示意没用连贯，1 示意有连贯，大于 1 示意不同的权重。
拜访 Graph 中的节点须要应用遍历算法，遍历算法又分为广度优先和深度优先，次要用于确定指标节点和根节点之间的间隔，
在 Javascript 中，Graph 能够用一个矩阵（二维数组）示意，广度优先搜索算法能够实现如下：
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));打印：
{
0: 2,
1: 0,
2: 1,
3: 3,
4: Infinity
}