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']