面试题：说说你了解的js数据结构
JavaScript中的数据结构是编程的基础，它们帮助我们以高效的方式存储和操作数据。
下面将详细介绍
这些数据结构的来源、概念和应用场景。
数组 Array
来源： 数组是一种线性数据结构，起源于计算机科学的早期，用于存储一系列的元素。
概念： 数组是具有相同数据类型的一组有序元素的集合，可以通过索引快速访问每个元素。
应用场景： 数组适用于需要快速访问元素的场景，如列表、矩阵等。
数组是最基本的数据结构，它使用一块连续的内存空间保存数据，保存的数据的个数在分配内存的时候是确定的
let users = [{ id: 1, name: "Alice", age: 25 },{ id: 2, name: "Bob", age: 30 },{ id: 3, name: "Charlie", age: 22 }
];// 访问第一个用户
console.log(users[0]); // { id: 1, name: "Alice", age: 25 }
栈 Stack
来源： 栈的概念来源于计算机科学中的抽象数据类型，用于模拟现实世界中堆叠物品的行为。
概念： 栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行添加（push）和移除（pop）操作。
应用场景： 栈适用于需要后进先出操作的场景，如浏览器的前进和后退功能、函数调用栈等。
在栈里，新元素都接近栈顶，旧元素都接近栈底 每次加入新的元素和拿走元素都在顶部操作
场景： 实现一个简单的撤销功能。
class Stack {constructor() {this.items = [];}push(item) {this.items.push(item);}pop() {return this.items.pop();}
}let undoStack = new Stack();
undoStack.push("第一步操作");
undoStack.push("第二步操作");// 撤销操作
console.log(undoStack.pop()); // "第二步操作"队列
来源： 队列的概念同样起源于计算机科学，用于模拟现实世界中的排队行为。
概念： 队列是一种先进先出（FIFO）的数据结构，只允许在队尾添加元素，在队首移除元素。
应用场景： 队列适用于需要先进先出操作的场景，如任务调度、缓冲处理等。
场景： 实现一个简单的任务队列。
class Queue {constructor() {this.items = [];}enqueue(item) {this.items.push(item);}dequeue() {return this.items.shift();}
}let taskQueue = new Queue();
taskQueue.enqueue("任务1");
taskQueue.enqueue("任务2");// 执行任务
console.log(taskQueue.dequeue()); // "任务1"
链表
来源： 链表的概念起源于计算机科学，用于解决数组在插入和删除操作时效率低下的问题。
概念： 链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
应用场景： 链表适用于频繁插入和删除操作的场景，如实现哈希表、LRU缓存等。
场景： 实现一个简单的链表结构。
class ListNode {constructor(value) {this.value = value;this.next = null;}
}class LinkedList {constructor() {this.head = null;}append(value) {let newNode = new ListNode(value);if (!this.head) {this.head = newNode;return;}let current = this.head;while (current.next) {current = current.next;}current.next = newNode;}
}let list = new LinkedList();
list.append(1);
list.append(2);// 输出链表
console.log(list); // ListNode { value: 1, next: ListNode { value: 2, next: null } }
字典
来源： 字典的概念起源于现实世界中的字典，用于存储键值对。
概念： 字典是一种存储键值对的数据结构，允许通过键快速访问对应的值。
应用场景： 字典适用于需要通过键快速查找值的场景，如实现映射、缓存等。
场景： 存储和检索键值对。
let dictionary = new Map();
dictionary.set("name", "Alice");
dictionary.set("age", 25);// 获取值
console.log(dictionary.get("name")); // "Alice"
散列表
来源： 散列表（哈希表）的概念起源于计算机科学，用于实现快速的键值对存储和检索。
概念： 散列表是一种通过哈希函数将键映射到数组索引的数据结构，以实现快速的查找和插入。
应用场景： 散列表适用于需要快速键值对操作的场景，如数据库索引、缓存等。
场景： 实现一个简单的缓存机制。
class HashTable {constructor(size) {this.buckets = new Array(size);this.size = size;}hash(key) {let hash = 0;for (let i = 0; i < key.length; i++) {hash = (hash + key.charCodeAt(i)) % this.size;}return hash;}set(key, value) {let index = this.hash(key);if (!this.buckets[index]) {this.buckets[index] = [];}this.buckets[index].push([key, value]);}get(key) {let index = this.hash(key);let bucket = this.buckets[index];if (bucket) {for (let i = 0; i < bucket.length; i++) {if (bucket[i][0] === key) {return bucket[i][1];}}}return undefined;}
}let hashTable = new HashTable(10);
hashTable.set("name", "Alice");
hashTable.set("age", 25);// 获取值
console.log(hashTable.get("name")); // "Alice"
树
来源： 树的概念起源于计算机科学中的抽象数据类型，用于模拟具有层级关系的数据。
概念： 树是一种非线性数据结构，由节点组成，每个节点可以有多个子节点，但只有一个父节点（根节点除外）。
应用场景： 树适用于表示具有层级关系的数据，如文件系统、组织结构图等。
场景： 实现一个简单的文件系统。
class TreeNode {constructor(value) {this.value = value;this.children = [];}
}let root = new TreeNode("root");
let child1 = new TreeNode("child1");
let child2 = new TreeNode("child2");root.children.push(child1);
root.children.push(child2);// 输出树结构
console.log(root); // TreeNode { value: "root", children: [TreeNode, TreeNode] }
图
来源： 图的概念起源于数学，用于表示对象之间的关系。
概念： 图是一种由节点（顶点）和连接节点的边组成的非线性数据结构，可以是有向图或无向图。
应用场景： 图适用于表示复杂的关系网络，如社交网络、地图导航等。
场景： 实现一个简单的社交网络。
class Graph {constructor() {this.adjacencyList = new Map();}addVertex(vertex) {if (!this.adjacencyList.has(vertex)) {this.adjacencyList.set(vertex, []);}}addEdge(source, destination) {if (this.adjacencyList.has(source) && this.adjacencyList.has(destination)) {this.adjacencyList.get(source).push(destination);this.adjacencyList.get(destination).push(source);}}
}let graph = new Graph();
graph.addVertex("Alice");
graph.addVertex("Bob");
graph.addEdge("Alice", "Bob");// 输出图结构
console.log(graph.adjacencyList); // Map(2) {"Alice" => ["Bob"], "Bob" => ["Alice"]}
堆
来源： 堆的概念起源于计算机科学，用于实现优先队列。
概念： 堆是一种特殊的完全二叉树，满足堆属性：每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。
应用场景： 堆适用于需要快速访问最大或最小元素的场景，如优先队列、堆排序等。
以上数据结构在JavaScript中都有实现，它们在不同的场景下发挥着各自的作用，帮助开发者高效地解决问题。理解这些数据结构的概念和应用场景对于编写高效、可维护的代码至关重要。
场景： 实现一个优先队列。
class MaxHeap {constructor() {this.heap = [];}insert(value) {this.heap.push(value);this.bubbleUp();}bubbleUp() {let index = this.heap.length - 1;const element = this.heap[index];while (index > 0) {let parentIndex = Math.floor((index - 1) / 2);let parent = this.heap[parentIndex];if (element <= parent) break;this.heap[index] = parent;this.heap[parentIndex] = element;index = parentIndex;}}extractMax() {const max = this.heap[0];const end = this.heap.pop();if (this.heap.length > 0) {this.heap[0] = end;this.bubbleDown();}return max;}bubbleDown() {let index = 0;const length = this.heap.length;const element = this.heap[0];while (true) {let leftChildIndex = 2 * index + 1;let rightChildIndex = 2 * index + 2;let leftChild, rightChild;let swap = null;if (leftChildIndex < length) {leftChild = this.heap[leftChildIndex];if (leftChild > element) {swap = leftChildIndex;}}if (rightChildIndex < length) {rightChild = this.heap[rightChildIndex];if ((swap === null && rightChild > element) ||(swap !== null && rightChild > leftChild)) {swap = rightChildIndex;}}if (swap === null) break;this.heap[index] = this.heap[swap];this.heap[swap] = element;index = swap;}}
}let maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);// 获取最大值
console.log(maxHeap.extractMax()); // 20
这些数据结构在实际开发中非常有用，能够帮助我们更高效地解决问题。
