前端面试题-说说你了解的js数据结构?(2024.1.29)

1、数组 (Array)

数组是一组有序的值的集合，可以通过索引访问。JavaScript 数组可以包含不同的数据类型，并且长度是动态的。

let myArray = [1, 'hello', true, [2, 3]];

2、对象 (Object)

对象是无序的键值对的集合。每个键都是字符串或符号，值可以是任何数据类型。

let myObject = {key1: 'value1',key2: 42,key3: ['a', 'b', 'c']
};

3、栈 (Stack)

栈是一种后进先出（LIFO）的数据结构，只允许在顶部进行插入和删除操作。常见的应用包括函数调用堆栈。（想象一下你在叠盘子，你总是把新的盘子放在最上面，那么拿出盘子时，你会从最上面开始取。后面叠的盘子先被取出，这就是后进先出。只能从最上面取盘子。不能在中间或底部插入或删除盘子。这就是栈的特点，只能在顶部进行插入和删除。）

这种栈的操作方式确保了函数调用的顺序是后进先出，也就是最后调用的函数最先执行完毕。这就是栈在函数调用中的应用，它通过维护一个栈帧（包含函数的信息）来管理函数的调用顺序。

class Stack {constructor() {this.items = [];}// 入栈push(element) {this.items.push(element);}// 出栈pop() {if (this.isEmpty()) {return "Underflow";}return this.items.pop();}// 查看栈顶元素peek() {if (this.isEmpty()) {return "Stack is empty";}return this.items[this.items.length - 1];}// 判断栈是否为空isEmpty() {return this.items.length === 0;}// 返回栈的大小size() {return this.items.length;}
}// 使用栈
let myStack = new Stack();// 入栈
myStack.push(10);
myStack.push(20);
myStack.push(30);// 出栈
console.log(myStack.pop()); // 输出 30// 查看栈顶元素
console.log(myStack.peek()); // 输出 20// 判断栈是否为空
console.log(myStack.isEmpty()); // 输出 false// 返回栈的大小
console.log(myStack.size()); // 输出 2

4、队列 (Queue)

队列是一种先进先出（FIFO）的数据结构，允许在一端插入元素，在另一端删除元素。常见的应用包括任务队列。（队列（Queue）就像是排队买票或者排队等候服务的一群人，先来的人先服务，后来的人后服务。）常见的应用： 在计算机科学中，队列经常被用于任务队列，例如异步操作的处理、消息队列等。任务按照先进先服务的原则执行，确保按照顺序处理各项任务

5、链表 (Linked List)

链表是由节点组成的序列，每个节点包含一个值和一个指向下一个节点的指针。链表允许在中间插入或删除元素。

想象你有一串糖果链，每颗糖果都是一个节点，而链子就像是连接这些糖果的绳子。

1. 添加糖果： 如果你想往糖果链上加一颗新的糖果，你可以把新糖果挂在链子的最前面，然后让它的绳子指向原来的第一颗糖果。

2. 移除糖果： 如果你想拿掉一颗糖果，只需要调整前一颗糖果的绳子，让它直接指向被拿掉的糖果之后的糖果。这样就好像把那颗糖果从链子上拿掉了。

3. 检查糖果： 从链子的开始位置，你可以一颗一颗地往后走，每次都按照绳子的指示找到下一颗糖果。这样你就可以逐个查看整条糖果链上的每颗糖果。

每颗糖果就是链表中的一个节点，节点可以存储一些数据。而绳子就像箭头一样，指向下一颗糖果。这种结构让你可以在链表中轻松地添加、移除和检查节点

// 定义链表节点类
class CandyNode {constructor(data, next = null) {this.data = data; // 糖果的种类this.next = next; // 指向下一个糖果节点的指针，默认为 null 表示末尾}
}// 定义糖果链表类
class CandyLinkedList {constructor() {this.head = null; // 链表的头部节点}// 添加糖果到链表头部addCandy(data) {const newCandy = new CandyNode(data, this.head);this.head = newCandy;}// 移除指定种类的糖果removeCandy(targetData) {if (!this.head) {return;}if (this.head.data === targetData) {this.head = this.head.next;return;}let current = this.head;while (current.next) {if (current.next.data === targetData) {current.next = current.next.next;return;}current = current.next;}console.error(`No candy of type '${targetData}' found.`);}// 打印糖果链表printCandyList() {let current = this.head;while (current) {console.log(`Candy Type: ${current.data}`);current = current.next;}}
}// 使用糖果链表
const candyList = new CandyLinkedList();
candyList.addCandy('Chocolate');
candyList.addCandy('Caramel');
candyList.addCandy('Gummy');
candyList.printCandyList();// 移除一颗糖果
candyList.removeCandy('Caramel');
console.log('\nAfter removing Caramel:\n');
candyList.printCandyList();

CandyNode 类表示链表中的糖果节点，每个节点有一个值 data 和一个指向下一个节点的指针 next。CandyLinkedList 类表示糖果链表，提供了添加和移除糖果的方法，以及打印链表的方法。

你可以通过 addCandy 方法在链表头部添加糖果，通过 removeCandy 方法移除指定种类的糖果，通过 printCandyList 方法打印整个糖果链表

6、集合 (Set)

集合是一种无序且唯一的数据结构，它不允许重复的元素。常见的应用包括查找和去重。

// 创建一个集合类
class Set {constructor() {this.elements = new Map();}// 添加元素add(element) {if (!this.has(element)) {this.elements.set(element, true);}}// 删除元素delete(element) {this.elements.delete(element);}// 检查元素是否存在has(element) {return this.elements.has(element);}// 获取集合大小size() {return this.elements.size;}// 获取集合中的所有元素getElements() {return Array.from(this.elements.keys());}// 集合运算 - 交集intersection(otherSet) {const newSet = new Set();this.getElements().forEach(element => {if (otherSet.has(element)) {newSet.add(element);}});return newSet;}// 集合运算 - 并集union(otherSet) {const newSet = new Set();this.getElements().forEach(element => {newSet.add(element);});otherSet.getElements().forEach(element => {newSet.add(element);});return newSet;}// 集合运算 - 差集difference(otherSet) {const newSet = new Set();this.getElements().forEach(element => {if (!otherSet.has(element)) {newSet.add(element);}});return newSet;}
}// 使用集合
const fruitSet = new Set();
fruitSet.add('Apple');
fruitSet.add('Banana');
fruitSet.add('Orange');console.log(fruitSet.getElements()); // 输出: ['Apple', 'Banana', 'Orange']fruitSet.delete('Banana');
console.log(fruitSet.getElements()); // 输出: ['Apple', 'Orange']console.log(fruitSet.has('Apple')); // 输出: true
console.log(fruitSet.has('Grape')); // 输出: falseconsole.log(fruitSet.size()); // 输出: 2const newFruitSet = new Set();
newFruitSet.add('Orange');
newFruitSet.add('Grape');const intersectionSet = fruitSet.intersection(newFruitSet);
console.log(intersectionSet.getElements()); // 输出: ['Orange']const unionSet = fruitSet.union(newFruitSet);
console.log(unionSet.getElements()); // 输出: ['Apple', 'Orange', 'Grape']const differenceSet = fruitSet.difference(newFruitSet);
console.log(differenceSet.getElements()); // 输出: ['Apple']

应用

1. 去重： 用集合来去除数组中的重复元素，得到一个唯一元素的列表。
2. 成员关系判断： 可以用集合来检查某个元素是否属于一个特定的集合。
3. 集合运算： 在处理多个集合时，可以利用集合运算来获得交集、并集、差集等结果。

7、映射 (Map)

映射是键值对的集合，其中每个键唯一对应一个值。与对象相似，但映射的键可以是任何数据类型。

// 创建一个映射
const userMap = new Map();// 添加键值对
userMap.set('username', 'john_doe');
userMap.set('age', 25);
userMap.set('isSubscribed', true);// 获取值
console.log(userMap.get('username')); // 输出: 'john_doe'// 检查键是否存在
console.log(userMap.has('email')); // 输出: false// 删除键值对
userMap.delete('age');// 获取映射大小
console.log(userMap.size); // 输出: 2// 遍历映射
userMap.forEach((value, key) => {console.log(`${key}: ${value}`);
});
// 输出:
// username: john_doe
// isSubscribed: true

8、树 (Tree)

树是一种层级结构，由节点组成，每个节点有一个父节点和零个或多个子节点。二叉树是一种特殊的树，每个节点最多有两个子节点。树是一种层级结构，由节点组成，每个节点都有一个父节点（除了根节点）和零个或多个子节点。节点之间的关系形成了层级关系，通常表示为从上到下的方向。树的最上层节点称为根节点，没有子节点的节点称为叶子节点。

常见术语：

1. 根节点 (Root): 树的顶层节点，没有父节点。
2. 叶子节点 (Leaf): 没有子节点的节点。
3. 父节点 (Parent): 有子节点的节点。
4. 子节点 (Child): 位于某个节点下面的节点。
5. 兄弟节点 (Sibling): 具有相同父节点的节点。
6. 深度 (Depth): 从根节点到某个节点的层级数。
7. 高度 (Height): 从某个节点到它的最远叶子节点的层级数。
8. 子树 (Subtree): 树中的任意节点及其所有后代节点组成的树

二叉树 (Binary Tree): 二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的结构使得在树的任何一层，每个节点都最多有两个子节点。

二叉搜索树 (Binary Search Tree): 二叉搜索树是一种二叉树，其中每个节点的左子树的所有节点的值都小于该节点的值，而右子树的所有节点的值都大于该节点的值。这种性质使得二叉搜索树具有高效的查找、插入和删除操作。

平衡树 (Balanced Tree): 为了避免树在特定操作下退化成链表，通常会使用平衡树，其中树的左右子树的高度差被控制在一个小范围内。

9、图 (Graph)

图是一组节点和边的集合，节点之间通过边连接。图可以是有向的或无向的，可以有权重或无权重。

// 邻接表表示无向图
class Graph {constructor() {this.vertices = new Map(); // 用 Map 存储顶点和相邻顶点的关系}addVertex(vertex) {this.vertices.set(vertex, []); // 初始化一个顶点的邻接表为空数组}addEdge(vertex1, vertex2) {this.vertices.get(vertex1).push(vertex2);this.vertices.get(vertex2).push(vertex1);}printGraph() {this.vertices.forEach((adjacentVertices, vertex) => {console.log(`${vertex} -> ${adjacentVertices.join(', ')}`);});}
}// 使用图
const socialNetwork = new Graph();
socialNetwork.addVertex('Alice');
socialNetwork.addVertex('Bob');
socialNetwork.addVertex('Charlie');
socialNetwork.addEdge('Alice', 'Bob');
socialNetwork.addEdge('Bob', 'Charlie');
socialNetwork.printGraph();
// 输出:
// Alice -> Bob
// Bob -> Alice, Charlie
// Charlie -> Bob

常见的说一下就行，后面两个我也是了解