前端 用js封装部分数据结构

Stack

栈，先进后出，后进先出。用数组来进行模拟，通过push存入，通过pop取出。

class Stack {// 带#表示这是一个私有变量，不能在外部对其进行直接修改#items = []push(val) {this.#items.push(val);}pop() {return this.#items.pop();}getLength() {return this.#items.length;}clear() {this.#items = [];}peek() {return this.#items.at(-1) || this.#items[this.#items.length - 1];}isEmpty() {return this.#items.length === 0;}
}const stack1 = new Stack();
stack1.push(1);
stack1.push(2);
console.log(stack1);
stack1.push(4);
console.log(stack1);
console.log(stack1.pop());// 用辗转相除法，将一个十进制转化为任意进制的数 2到十六进制（一般为）function tansformTenToNumber(targetNumber,base) {let num = targetNumber;const stack = new Stack();let result = '';const stringMap='0123456789ABCDEF';while(num > 0) {stack.push(stringMap[num % base]);num = Math.floor(num / base);}while(stack.getLength() !== 0) {result = result + stack.pop()}return result
}console.log(tansformTenToNumber(50,2)) // 110010
console.log(tansformTenToNumber(1501,16)) // 5DD

队列

为什么用对象来封装队列而不用数组呢，因为当数组shift的时候，会造成一定的性能问题。
当你将数组第一个移动，实际上，整个数组所有的子元素都会跟着移动。

class Queue {
// 带#表示这是一个私有变量，不能在外部对其进行直接修改#items = {};#min = 0;#max = 0;push(val) {this.#items[this.#max] = valthis.#max++}shift() {// 如果已经为空，就没有东西可以取if(this.isEmpty()) {return undefined}// 取出数字最小的，先进先出麻let result = this.#items[this.#min]this.#min++return result}clear() {this.#items = {}this.#max = 0;this.#min = 0;}size() {return this.#max - this.#min}isEmpty() {return this.size() === 0}
}const queue = new Queue()queue.push('deng')
queue.push('xi')
queue.push('yang')
queue.push('xi')console.log(queue.size()) // 4
console.log(queue.isEmpty()) // false
console.log(queue.shift()) // deng
console.log(queue.shift()) // xi
console.log(queue.shift()) // yang
console.log(queue.shift()) // xi
console.log(queue.shift()) // undefined
console.log(queue.isEmpty()) // truequeue.push('deng')
queue.push('xi')console.log(queue.shift()) //deng
console.log(queue.clear())
console.log(queue.isEmpty()) // true
queue.push('yang')
queue.push('xi')
console.log(queue.size()) // 2// 击鼓传花
// 参与者按照一定顺序，一次被选中，当鼓声停止时，被选中的人淘汰，
// 直到场上剩下最后一人为止。// 接受两个参数，第一个参数，参与人的数组， 
// 第二个参数，鼓声每次敲击多少下,敲击多少次后，必须淘汰拿花的人
function passingFlower(list, num) {const queue = new Queue()// 先将list 全部放入队列中for(let i =0,len=list.length;i < len; i++) {queue.push(list[i])}// 当只剩一个人的时候停止循环while(queue.size() > 1) {for(let j=0, len=num; j < len; j++) {// 每一次循环，都要将队列最前面的人放到最后面去let result = queue.shift()queue.push(result)}// 当循环结束，淘汰掉一个人，直接从队列最前面拿掉，不放入队列最后queue.shift()}// 将最后一人作为获胜者返回return queue.shift()
}const winner = passingFlower(['d','e','n','g','x','i'], 7)console.log(winner) // n

链表

为了解决队列里面，移动一个，后面的所有元素都会跟着移动的问题，出现了新的数据结构，链表。链表是不定长度的数据，但与数组相比，不利于数据的搜索。

// 链表中的单个节点
class LinkElement {constructor(value) {this.value = value;this.next = null;}setNext(next) {this.next = next;}getNext() {return this.next;}
}
// 链表
class LinkList {constructor() {this.count = 0;this.head = null;}// 追加链表到里面，放置到最后一个push(val) {let link = new LinkElement(val);if (this.head === null) {// 让头指向第一个节点this.head = link;} else {let current = this.head;// 如果不为空，就要一直找到链表的最后一个，然后让最后一个的next指向新的节点while (current.getNext() !== null) {current = current.getNext();}current.setNext(link);}// 计算加一this.count++;}// 删除制定位置removeAt(index) {// 如果是空的，就直接返回if (index < 0 || index >= this.count) {return undefined;}let current = this.head;if (index === 0) {// 如果是0，就让head指向第二个节点this.head = current.getNext();} else {// 找到 index的上一个link节点let previous = this.findAt(index - 1);// current 就是 index 就是要删除的节点current = previous.getNext();// 让 index - 1 的节点的next指向 index + 1 的节点，这样就把 index 的节点删除了previous.setNext(current.getNext());}// 计算减一this.count--;// 将删除的节点返回return current;}// 找到指定位置的节点findAt(index) {if (index < 0 || index >= this.count) {return undefined;}let current = this.head;for (let i = 0; i < index; i++) {// 当循环到最后，current 是 index - 1，再getNext 就是 indexcurrent = current.getNext();}return current;}// 根据val值，找第一个节点的索引值indexOf(val) {let current = this.head;// 如果没找到返回 -1let result = -1;for (let i = 0; i < this.count; i++) {if (current.value === val) {result = i;}// 不断的往下一个链表找current = current.getNext();}return result;}// 删除指定val值的节点removeVal(val) {// 找到对应值的indexlet currentIndex = this.indexOf(val);if (currentIndex === -1) {return undefined;} else {// 如果有就利用removeAt删除return this.removeAt(currentIndex);}}// 链表的插入，在指定位置插入元素,第一个参数是你要插入元素的值，第二参数是你要插入链表的位置insert(val, index) {const link = new LinkElement(val);// 判断index 是否合理if (index < 0 || index > this.count) {return false;}// 如果是0，就让head指向新的节点if (index === 0) {let current = this.head;// 让新的节点的next指向第一个节点link.setNext(current);// 然后让指针指向新的第一个节点this.head = link;} else {// 找到index - 1 的节点let previous = this.findAt(index - 1);// 让新的节点的next指向 index 的节点link.setNext(previous.getNext());// 让 index - 1 的节点的next指向新的节点previous.setNext(link);}// 将count + 1this.count++;}size() {return this.count;}isEmpty() {return this.size() === 0;}getHead() {return this.head;}
}const linkList = new LinkList();linkList.push(1);
linkList.push(2);
linkList.push(3);
linkList.push(4);
linkList.insert(0, 0);
console.log(linkList.indexOf(1));linkList.removeAt(1);
console.log(linkList);linkList.removeVal(2);
console.log(linkList);

Set

set用对象来封装，key和value保存一致。这样就能确保Set里面的内容不会被重复保存。如果要想确保万无一失，可以用symboal模拟set，这样可以在set里面保存任意内容。

class MySet {#object = {};delete(value) {// 删除之前先判断该值是否存在if (this.has(value)) {delete this.#object[value];return true;}return false;}add(value) {// 添加之前也得先判断是否已经存在了，不能重复添加if (!this.has(value)) {this.#object[value] = value;return true;}return false;}has(value) {return this.#object.hasOwnProperty(value);}clear() {this.#object = {};}size() {return Object.values(this.#object).length;}values() {return Object.values(this.#object);}
}const set = new MySet();
set.add(1);
set.add(2);console.log(set.values()); // [1, 2]set.delete(2);console.log(set.values()); // [1]
console.log(set.size()); // 1console.log(set.has(1)); // trueset.clear();
console.log(set.values()); // []

set 用来数组去重

const arr1 = [1,2,3,4,4,5]
const arr2 = [3,4,5,6]const result = Array.from(new Set(arr1))
console.log(result) // [ 1, 2, 3, 4, 5 ]

set用来取两个数组的并集

const arr1 = [1,2,3,4,4,5]
const arr2 = [3,4,5,6]// 并集 将两个数组重复的内容，全部去重
const union = Array.from(new Set([...arr1, ...arr2]))

set用来取两个数组的交集

const arr1 = [1,2,3,4,4,5]
const arr2 = [3,4,5,6]
const set2 = new Set(arr2)
// 交集 将两个数组重复的内容，全部保留
const intersection = arr1.filter(item => set2.has(item))

set用来取两个数组的差集

const arr1 = [1,2,3,4,4,5]
const set1 = new Set(arr1)
const arr2 = [3,4,5,6]
const set2 = new Set(arr2)
// 差集 取出arr1对arr2的差集 // 1 2
const intersection = arr1.filter(item => !set2.has(item))
// 差集 取出arr2对arr1的差集 // 6
const intersection2 = arr2.filter(item => !set1.has(item))

字典

class NewMap {#obj = {};keyToString(key) {let KeyStr = "";switch (key) {case null:KeyStr = "null";break;case undefined:KeyStr = "undefined";default:KeyStr = JSON.stringify(key);break;}return KeyStr}// 社区比较受欢迎的计算hashcode方式之一hashCode(key) {let mapKey = this.keyToString(key) || '';let hash = 5381;for(let i=0,len=mapKey.length; i<len; i++) {hash = (hash * 33) + mapKey.charCodeAt(i);}return hash % 1013}set(key, value) {// 通过hashcode来保存keythis.#obj[this.hashCode(key)] = {key,value,};}remove(key) {if(this.#obj[this.hashCode(key)]) {delete this.#obj[this.hashCode(key)]return true}return false}has(key) {return this.get(key) !== undefined}get(key) {if(this.#obj[this.hashCode(key)]) {return this.#obj[this.hashCode(key)].value}}keyValues() {return Object.entries(this.#obj)}size() {return this.keyValues().length}
}const map1 = new NewMap()map1.set(null,null)
map1.set(undefined,undefined)
map1.set({a:1},{a:1})
console.log(map1.keyValues())
console.log(map1.has({a:1})) // trueconsole.log(map1.get({a:1})) // {a:1}console.log(map1.size()) // 3