前端常用数据结构
- 什么是数据结构
- 常用的数据结构
- JavaScript 如何实现
- 这些数据结构实际场景
数据结构
所谓数据结构，是在计算机中组织、管理和存储数据的一种方式。
🙋：你知道哪些数据结构？
数据结构整体可以分为两大类：线性数据结构 和 非线性数据结构
-
线性数据结构：数据会排列成线性的序列
- 数组（Array）：一种固定大小的数据结构，里面存储相同类型的元素集合。通过索引来进行访问。
- 链表（Linked List）：由一个一个的节点组成，每个节点会包含数据还有下一个节点的指针（内存地址）
- 栈（Stack）：只有一个出入口，先进后出、后进先出
- 队列（Queue）：有两个口，因此先进先出，后进后出
-
非线性数据结构：顾名思义，就是元素不以线性的顺序排列
- 树（Tree）：体现了一个层次，DOM 树、组件树
- 图（Graph）：由多个节点以及连接节点的边组成。
- 哈希表（Hash Table）
前端常用的数据结构有：数组、栈、队列、链表以及树
数组
回顾一下数组创建的方法：
// 字面量创建
const arr = [];
// Array构造函数
const arr2 = new Array(3); // 如果参数只有一个值，那么表示的是长度
const arr3 = new Array(1, 2, 3); // 如果参数是多个值，那么表示的是数组的元素
// Array.of方法：ES6 新引入的方法
// 解决 Array 构造函数参数只有一个的时候的怪异行为
const arr4 = Array.of(3); // [3]
const arr5 = Array.of(1, 2, 3); // [1, 2, 3]
// Array.from方法：从一个类组数对象或者可迭代对象创建一个新的数组
const arr6 = Array.from("abc"); // ['a', 'b', 'c']
// 扩展运算符
const a = [1, 2, 3];
const b = [4, 5, 6];
const arr7 = [...a, ...b];
严格意义来讲，JS 里面所提供的数组并非数据结构里面的数组：
int[] arr = new int[3];
arr[0] = 100; // 合法
arr[1] = 200; // 合法
arr[2] = 300; // 合法
arr[3] = 400; // 报错：数组越界
在 JS 中压根儿就没有数组越界这个概念
const arr = [];
console.log(arr[10]); // undefined
arr[10] = 100;
console.log(arr[10]); // 100
究其原因，是因为 JS 底部，数组实际上就是对象。
类似于：
const arr = {
0: 100,
1: 200,
2: 300,
};
console.log(arr[0]);
栈
- FILO（first in last out）：先进后出
- LIFO（last in first out）：后进先出
class Stack {
constructor(...args) {
this.stack = [...args];
}
// 返回栈中元素的数量
size() {
return this.stack.length;
}
// 检查栈是否为空
isEmpty() {
return this.size() === 0;
}
// 添加一个或者多个元素到栈顶
push(...items) {
return this.stack.push(...items);
}
// 移除栈顶元素，返回被移除的元素
pop() {
return this.stack.pop();
}
// 返回栈顶元素，但是不删除
peek() {
return this.isEmpty() ? undefined : this.stack[this.size() - 1];
}
}
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4, 5, 6);
console.log(stack.size()); // 6
// 访问栈顶的元素
console.log(stack.peek