JS数据结构之“栈”、“队列”、“链表”
一、栈
JS中没有栈这种数据类型，创建栈其实是创建数组。push（内容）入栈；pop（）出栈；
const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop();二、队列
JS中没有队列这种数据类型，创建队列其实是创建数组。push（内容）入队；shift（）出队；
const queue = [];
queue.push(1);
queue.push(2);
const item1 = queue.shift();
const item2 = queue.shift();
三、链表
在JavaScript中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和一个或多个指向列表中其他节点的引用（链接）。链表与数组不同，它在内存中不是连续存储的，这使得链表在插入和删除操作时更加高效。
以下是链表的基本组成部分和操作：
节点（Node）
链表中的每个元素都被称为节点，每个节点通常包含两个部分：
- 数据域：存储节点的数据。
- 指针域（或链接域）：存储指向下一个节点的引用。
下面是一个简单的节点类实现：
class ListNode {
constructor(data) {
this.data = data; // 数据域
this.next = null; // 指针域，初始为null
}
}
JS中简单的链表写成下面这种形式就可以。
const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;
// 遍历链表
let p = a;
while (p) {
console.log(p.val);
p = p.next;
}
// 插入操作
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除
c.next = d;链表（LinkedList）
链表本身是一个包含多个节点的数据结构，通常会有以下操作：
- 初始化：创建一个空链表。
- 插入：在链表的特定位置插入一个新节点。
- 删除：从链表中删除一个节点。
- 查找：在链表中查找一个节点。
- 遍历：访问链表中的每个节点。
以下是一个简单的链表类实现：
class LinkedList {
constructor() {
this.head = null; // 初始化时，头节点为null
}
// 在链表末尾添加一个新节点
append(data) {
let newNode = new ListNode(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 在链表头部添加一个新节点
prepend(data) {
let newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
}
// 删除特定数据的节点
delete(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
// 查找特定数据的节点
find(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}
// 遍历链表并打印每个节点的数据
print() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
使用链表
下面是如何使用上面定义的链表类：
let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print(); // 输出: 0 1 2 3
list.delete(2);
list.print(); // 输出: 0 1 3
链表在JavaScript中的应用非常广泛，尤其是在需要频繁插入和删除操作的场景中，它比数组更加高效。然而，链表也有其缺点，比如它不支持随机访问，访问特定索引的元素需要从头开始遍历。
使用链表指针获取JSON节点值
const json = {
a: { b: { c: 1 } },
d: { e: 2 },
};
const path = ['a', 'b', 'c'];
let p = json;
path.forEach(k => {
p = p[k];
});
JS中的原型链
const obj = {};
const func = () => { };
const arr = [];
// 如果A沿着原型链能够找到B.prototype，那么A instanceof B为true
// 如果在A对象上没有找到x属性，那么会沿着原型链找x属性
Object.prototype.x = 'x';
Function.prototype.y = 'y';
四、集合
在JavaScript中，集合（Set）是一种内置的对象类型，用于存储唯一值（不重复的值）的集合。集合中的值可以是任何类型的数据，包括原始值或对象引用。
以下是关于JavaScript中集合的一些关键点：
创建集合
你可以使用new Set()构造函数来创建一个新的集合。
const mySet = new Set();
你也可以在创建时初始化集合，通过传递一个可迭代对象（如数组）。
const mySet = new Set([1, 2, 3, 4]);
添加元素
使用add()方法可以向集合中添加新元素。如果元素已存在，则不会重复添加。
mySet.add(5);
删除元素
使用delete()方法可以从集合中删除特定的元素，如果元素存在，则返回true，否则返回false。
mySet.delete(5); // 如果元素5存在，则删除并返回true
检查元素是否存在
使用has()方法可以检查集合中是否存在某个元素。
mySet.has(5); // 如果元素5存在，则返回true
获取集合的大小
使用size属性可以获取集合中元素的数量。
console.log(mySet.size); // 输出集合中的元素数量
清空集合
使用clear()方法可以清空集合中的所有元素。
mySet.clear();
遍历集合
集合是可迭代的，你可以使用for...of循环来遍历集合中的元素。
for (const item of mySet) {
console.log(item);
}
或者使用forEach()方法。
mySet.forEach((value) => {
console.log(value);
});
集合操作
集合支持多种数学集合操作，如并集、交集和差集。
- 并集：使用
...扩展运算符和new Set()可以创建两个集合的并集。
const setA = new Set([1, 2, 3]);
const setB = new Set([3, 4, 5]);
const union = new Set([...setA, ...setB]); // Set {1, 2, 3, 4, 5}
- 交集：使用
filter()方法可以创建两个集合的交集。
const intersection = new Set([...setA].filter((x) => setB.has(x))); // Set {3}
- 差集：同样使用
filter()方法可以创建两个集合的差集。
const difference = new Set([...setA].filter((x) => !setB.has(x))); // Set {1, 2}
集合在JavaScript中是一种非常有用的数据结构，特别是当你需要确保存储的数据唯一性时。它们提供了一种简单的方式来处理不重复的值的集合，并支持高效的数据操作。
let mySet = new Set();
// 1.添加
mySet.add(1);
mySet.add(5);
// 这个5不会被添加
mySet.add(5);
mySet.add('some text');
let o = { a: 1, b: 2 };
mySet.add(o);
// 但是这个{a: 1, b: 2 }对象会被添加 因为这个对象和o对象是两个不一样的内存
mySet.add({ a: 1, b: 2 });
// 2.has方法
const has = mySet.has(5);
// 3.delete方法
mySet.delete(5);
// 4.迭代Set 4种方法
for (let item of mySet) console.log(item);
for (let item of mySet.keys()) console.log(item);
for (let item of mySet.values()) console.log(item);
for (let [key,value] of mySet.entries()) console.log(key,value);
// 5.如何把Set和array互转
// 第一种方法 通过...运算
const myArr1 = [...mySet];
// 第二种方法 通过调用from方法
const myArr2 = Array.from(mySet);
// 6.如何把array转化为Set
const mySet2 = new Set([1, 2, 3, 4]);
// 求交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)));
// 求差集
const difference = new Set([...mySet].filter(x => !mySet2.has(x)));
// 去重
const arr = [1, 1, 2, 2];
const arr2 =[... new Set(arr)];
// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(3);
// 求交集
const set2 = new Set([2, 3]);
const set3 = new Set([...set].filter(item => set2.has(item)));
五、字典
const m = new Map();
//增
m.set('a', 'aa');
m.set('b', 'bb');
//删
m.delete('b');
// m.clear();
// 改
m.set('a', 'aaa');
JavaScript也提供了一个Map对象，它是一个更合适的字典实现，因为它保持键的插入顺序，并且允许任何类型的值作为键。
const myMap = new Map();
myMap.set('key1', 'value1');
myMap.set('key2', 'value2');
console.log(myMap.get('key1')); // 输出 'value1'
myMap.delete('key1');
console.log(myMap.has('key1')); // 输出 false
// 遍历Map
for (const [key, value] of myMap) {
console.log(key + ': ' + value);
}
另外，可以使用对象（Object）来模拟字典的行为。字典是一种数据结构，用于存储键值对，其中每个键都是唯一的，每个键都映射到一个值。
以下是关于在JavaScript中使用对象作为字典的一些关键点：
创建字典
你可以通过创建一个空对象来模拟一个字典。
const myDictionary = {};
添加键值对
你可以通过给对象属性赋值来添加键值对。
myDictionary.key1 = 'value1';
myDictionary['key2'] = 'value2';
访问值
你可以通过键来访问对应的值。
console.log(myDictionary.key1); // 输出 'value1'
console.log(myDictionary['key2']); // 输出 'value2'
修改值
你可以通过键来修改对应的值。
myDictionary.key1 = 'newValue1';
删除键值对
你可以使用delete操作符来删除键值对。
delete myDictionary.key1;
检查键是否存在
你可以使用in操作符来检查一个键是否存在于字典中。
console.log('key1' in myDictionary); // 输出 false，因为已经删除了
或者使用hasOwnProperty方法来检查对象自身属性中是否具有指定的属性。
console.log(myDictionary.hasOwnProperty('key2')); // 输出 true
遍历字典
你可以使用for...in循环来遍历字典中的所有键。
for (const key in myDictionary) {
if (myDictionary.hasOwnProperty(key)) {
console.log(key + ': ' + myDictionary[key]);
}
}
使用Object.keys()和Object.values()
Object.keys()方法返回一个包含对象所有自身可枚举属性名称的数组，而Object.values()方法返回一个包含对象自身所有可枚举属性值的数组。
const keys = Object.keys(myDictionary); // ['key2']
const values = Object.values(myDictionary); // ['value2']