使用JavaScript實作堆疊、佇列、鏈表、集合等常見資料結構，可能會有點用？
水
堆疊(Stack)
實際上JavaScript的Array本身就具有堆疊和佇列的特性，所以我們可以借助Array來實作它們，
class Stack {
constructor() {
this.items = [];
}
get length() {
return this.items.length;
}
// 獲取堆疊頂元素
get peek() {
return this.items[this.items.length - 1];
}
push(element) {
this.items.push(element);
}
pop() {
this.items.pop();
}
}
佇列(Queue)
class Queue {
constructor() {
this.items = [];
}
get isEmpty() {
return this.items.length === 0;
}
get length() {
return this.items.length;
}
// 入隊
enqueue(element) {
this.items.push(element);
}
// 出隊
dequeue() {
return this.items.shift();
}
}
優先佇列
佇列的升級版本，給每個元素一個優先級，入隊時會先排序，這里PriorityQueue繼承自Queue，所以只需要重寫enqueue方法，
class PriorityQueue extends Queue {
/**
* 入隊
* @param {*} element 元素
* @param {*} priority 優先級
*/
enqueue(element, priority) {
const queueElement = { element, priority };
if (this.isEmpty) {
super.enqueue(queueElement);
} else {
const preIndex = this.items.findIndex(items => queueElement.priority < items.priority);
if (preIndex > -1) {
this.items.splice(preIndex, 0, queueElement);
} else {
super.enqueue(queueElement);
}
}
}
}
回圈佇列
回圈佇列可以想象為一個首尾相連的圓環，相較于普通佇列，它更節省空間，
雖然同樣繼承自Queue，但基本上所有方法都重寫了，
class LoopQueue extends Queue {
constructor(maxSize) {
super();
this.maxSize = maxSize;
this.head = -1; //頭指標
this.tail = -1; //尾指標
}
get isFull(){
return (this.tail + 1) % this.maxSize === this.head;
}
get isEmpty(){
return this.tail === -1 && this.head === -1;
}
enqueue(element) {
if (this.isFull) {
return false;
}
if (this.isEmpty) {
this.head = 0;
}
this.tail = (this.tail + 1) % this.maxSize;
this.items[this.tail] = element;
return true;
}
dequeue(){
if (!this.isEmpty) {
if (this.tail === this.head) {
this.tail = -1;
this.head = -1;
} else {
this.head = (this.head + 1) % this.maxSize;
}
return true;
}
return false;
}
}
鏈表(Linked List)
// 節點
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
// 鏈表
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
// 追加
append(element) {
const node = new Node(element);
let current = null;
if (this.head === null) {
this.head = node;
} else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.length++;
}
/**
* 插入
* @param {*} element 元素
* @param {*} position 位置
*/
insert(element, position) {
if (position >= 0 && position <= this.length) {
const node = new Node(element);
let current = this.head;
let previous = null;
if (position === 0) {
this.head = node;
this.head.next = current;
} else {
for (let index = 0; index < position; index++) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
this.length++;
return true;
}
return false;
}
/**
* 洗掉
* @param {*} position 位置
*/
removeAt(position) {
if (position >= 0 && position < this.length) {
let current = this.head;
let previous = null;
if (position === 0) {
this.head = current.next;
} else {
for (let index = 0; index < position; index++) {
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.length--;
return current.element;
}
return null;
}
// 查找元素所在位置
indexOf(element) {
let current = this.head;
let index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
// 根據元素洗掉
remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
toString() {
let current = this.head;
let string = '';
while (current) {
string += `${current.element} -- `;
current = current.next;
}
string += '*';
return string;
}
}
集合(Set)
ES6中引入了集合型別，可以參考一下，
class Set {
constructor() {
this.items = {};
}
get size() {
return Object.keys(this.items).length;
}
get values() {
return Object.keys(this.items);
}
// 判斷元素是否存在
has(value) {
return this.items.hasOwnProperty(value);
}
add(value) {
if (!this.has(value)) {
this.items[value] = value;
return true;
}
return false;
}
remove(value) {
if (this.has(value)) {
delete this.items[value]
return true;
}
return false;
}
// 并集
union(otherSet) {
const unionSet = new MySet();
this.values.forEach((value) => unionSet.add(this.value));
otherSet.values.forEach((value) => unionSet.add(otherSet.value));
return unionSet;
}
// 交集
intersection(otherSet) {
const intersectionSet = new MySet();
this.values.forEach((value, index) => {
if (otherSet.has(value)) {
intersectionSet.add(value);
}
});
return intersectionSet;
}
// 差集
difference(otherSet) {
const differenceSet = new MySet();
this.values.forEach((value) => {
if (!otherSet.has(value)) {
differenceSet.add(value);
}
});
return differenceSet;
}
// 子集
subset(otherSet) {
return this.values.every((value) => otherSet.has(value));
}
}
字典(Dictionary)
在JavaScript中，Object物件實際上就是字典，都是以{ key: value }的形式存盤資料的，
class Dictionary {
constructor() {
this.items = {};
}
get keys() {
return Object.keys(this.items);
}
get values() {
const r = [];
Object.keys(this.items).forEach((value) => {
r.push(this.items[value]);
});
return r;
}
set(key, value) {
this.items[key] = value;
}
get(key) {
return this.items[key];
}
remove(key) {
delete this.items[key];
}
}
哈希表(Hash Table)
哈希表也是以鍵值對的形式存盤資料的，但是因為每個資料都會根據key生成唯一的哈希值，所以查詢速度非常快，
這里散列函式就是用來生成哈希值的，隨便寫的，常用的構造散列函式的方法在網上能查到很多，
class HashTable {
constructor() {
this.table = [];
}
// 散列函式
getHashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 64 * 0xffffff;
}
put(key, value) {
const position = this.getHashCode(key);
this.table[position] = value;
}
get(key) {
return this.table[this.getHashCode(key)];
}
remove(key) {
this.table[this.getHashCode(key)] = undefined;
}
}
樹(tree)
正常的二叉樹沒有必要實作，這里實作一下二叉搜索樹，
class Node {
constructor(data) {
this.data = https://www.cnblogs.com/xueyubao/p/data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(data) {
const newNode = new Node(data);
const insertNode = (node, newNode) => {
if (newNode.data < node.data) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
}
if (!this.root) {
this.root = newNode;
} else {
insertNode(this.root, newNode);
}
}
// 中序遍歷
inOrderTraverse(callback) {
const inOrderTraverseNode = (node, callback) => {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.data);
inOrderTraverseNode(node.right, callback);
}
}
inOrderTraverseNode(this.root, callback);
}
// 先序遍歷
preOrderTraverse(callback) {
const preOrderTraverseNode = (node, callback) => {
if (node !== null) {
callback(node.data);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
preOrderTraverseNode(this.root, callback);
}
// 后序遍歷
postOrderTraverse(callback) {
const postOrderTraverseNode = (node, callback) => {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.data);
}
}
postOrderTraverseNode(this.root, callback);
}
min() {
let current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.data;
}
max() {
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.data;
}
search(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;
}
remove(data) {
const removeNode = (node, data) => {
if (node === null) {
return false;
}
if (node.data === data) {
if (node.left === null && node.right === null) {
return null;
}
if (node.left === null) {
return node.right;
}
if (node.right === null) {
return node.left;
}
let tempNode = node.right;
while(tempNode.left !== null) {
tempNode = tempNode.left;
}
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
}
if (node.data > data) {
node.left = removeNode(node.left, data);
return node;
}
if(node.data < data) {
node.right = removeNode(node.right, data);
return node;
}
}
this.root = removeNode(this.root, data);
}
}
圖(Graph)
這里實作的無向圖，
class Graph {
constructor() {
this.vertices = []; // 存頂點
this.adjList = {}; // 存邊
}
// 頂點
addVertex(v) {
this.vertices.push(v);
this.adjList[v] = [];
}
// 邊
addEdge(v, w) {
this.adjList[v].push(w);
this.adjList[w].push(v);
}
// 轉化成鄰接表的形式的字串
toString() {
let str = '\n';
for (let i = 0; i < this.vertices.length; i++) {
const v = this.vertices[i];
str += v + ' => ';
const e = this.adjList[v];
for (let j = 0; j < e.length; j++) {
str += ' ' + e[j] + ' ';
}
str += '\n';
}
return str;
}
}
參考文章
-
在 JavaScript 中學習資料結構與演算法
-
常見資料結構和Javascript實作總結
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98388.html
標籤：其他