前端 用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] = val
        this.#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()) // true

queue.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 就是 index
      current = current.getNext();
    }

    return current;
  }

  // 根据val值，找第一个节点的索引值
  indexOf(val) {
    let current = this.head;
    // 如果没找到返回 -1
    let result = -1;

    for (let i = 0; i < this.count; i++) {
      if (current.value === val) {
        result = i;
      }
      // 不断的往下一个链表找
      current = current.getNext();
    }

    return result;
  }
  // 删除指定val值的节点
  removeVal(val) {
    // 找到对应值的index
    let 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 + 1
    this.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()); // 1

console.log(set.has(1)); // true

set.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来保存key
    this.#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})) // true

console.log(map1.get({a:1})) // {a:1}

console.log(map1.size()) // 3