JavaScript数据结构笔记-队列、栈、散列表

队列

队列（queue）是一种先进先出的、操作受限的线性表。必须从队尾插入新元素，队列中的元素只能从队首取出。下面是用数组实现的简单队列。

// 队列
class Queue {
  constructor() {
    this.queue = new Array();
    this.size = this.queue.length;
  }
// 向队列中添加一个元素
  enqueue = (item) => {
    this.queue.push(item)
    this.print();
  }
// 从队列中取出一个元素
  dequeue = () => {
    this.queue.shift();
    this.print();
  }
// 获取队列的大小
  size = () => {
    return this.size;
  }
// 清空队列
  clear = () => {
    this.queue = [];
    this.print();
  }
// 显示队列
  print = () => {
    console.log(`当前队列：${this.queue}`);
  }
}

function testQueue() {
  const myQueue = new Queue();
  myQueue.enqueue("队列1");
  myQueue.enqueue("队列2");
  myQueue.enqueue("队列3");
  myQueue.dequeue();
  myQueue.dequeue();
  myQueue.clear();
}

当前队列：队列1
当前队列：队列1,队列2
当前队列：队列1,队列2,队列3
当前队列：队列2,队列3
当前队列：队列3
当前队列：

栈

栈是只允许在同一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。下面是使用数组实现的简单栈。

class Stack {
  constructor() {
    this.stack = new Array();
    this.size = this.stack.length;
  }
// 入栈
  push = (item) => {
    this.stack.unshift(item);
    this.print();
  }
// 出栈
  pop = () => {
    this.stack.shift();
    this.print();
  }
// 查看栈元素个数
  size = () => {
    return this.size;
  }
// 清空栈
  clear = () => {
    this.stack = [];
    this.print();
  }

  print = () => {
    console.log(`当前栈：${this.stack}`);
  }
}

// 测试栈
function testStack() {
  let myStack = new Stack();
  myStack.push("栈1");
  myStack.push("栈2");
  myStack.push("栈3");
  myStack.pop();
  myStack.pop();
  myStack.clear();
}

当前栈：栈1
当前栈：栈2,栈1
当前栈：栈3,栈2,栈1
当前栈：栈2,栈1
当前栈：栈1
当前栈：

散列表

散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数在整个过程中起着非常关键的作用，它将数据一一映射到散列表中。散列表的设计需要遵循一下规则：

1. 得到的散列值是一个非负整数
2. 两个相同的键，通过散列函数计算出的散列值也相同
3. 两个不同的键，计算出的散列值不同

虽然我们在设计的时候要求满足以上三条要求，但是对于第三条来说，想要找到不同的 key 对应的散列值都不一样的散列函数是不可能的。即使现在非常著名的 MD5、SHA、CRC 哈希算法，也没办法避免这用哈希冲突。而且因为数组的存储空间有限，也会加大这种哈希冲突。

解决哈希冲突一般有两种方式，开放寻址法和链表法。

开放寻址法，当遇到哈希冲突的时候，在散列表中向下寻找一个空闲位置放入

链表法，在散列表每个位置存放一个链表，当出现哈希冲突的时候只需要在链表中添加一个元素即可。

下面是使用链表法实现的散列表

class HashTable {
  constructor() {
    this.hashTable = new Array(13);
  }
// 哈希函数
  hashCode = (key) => {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    return hash % 13;
  }
// 链表解决哈希冲突
  push = (key, value) => {
    let hash = this.hashCode(key);
    if (this.hashTable[hash] == undefined) {
      this.hashTable[hash] = new LinkedList();
    } 
    this.hashTable[hash].append({
      key: key,
      value: value
    });
    this.print();
  }
// 获取hash表内数据
  get = (key) => {
    let hash = this.hashCode(key);
    let link = this.hashTable[hash];
    if(link != undefined) {
      let currentNode = link.head;
      while(currentNode.val.key != key) {
        currentNode = currentNode.next;
      }
      return currentNode?.val.value;
    } else {
      return undefined;
    }
  }
// 删除hash表内数据
  remove = (key) => {
    let hash = this.hashCode(key);
    let link = this.hashTable[hash];
    if(link != undefined) {
      let currentNode = link.head;
      while(currentNode.next != null && currentNode.next.val.key != key) {
        currentNode = currentNode.next;
      }
      currentNode.next = currentNode.next.next;
    }
    this.print();
  }

  print = () => {
    let printString = '';
    for(let i=0; i<this.hashTable.length; i++) {
      let link = this.hashTable[i];
      if (link == undefined){
        printString = printString + '' + ',';
      } else {
        let currentNode = link.head.next;
        let tempString = '';
        while(currentNode != null) {
          tempString = tempString + '-->' + currentNode.val.key + '-' + currentNode.val.value;
          currentNode = currentNode.next;
        }
        printString = printString + tempString + ',';
      }
    }
    console.log(printString);
  }
}

function testHashTable() {
  let myHashTable = new HashTable();
  myHashTable.push('a7', '哈希1');
  myHashTable.push('b6', '哈希2');
  myHashTable.push('k3i', '哈希3');
  myHashTable.push('k21', '哈希4');
  myHashTable.push('oop1', '哈希5');

  console.log(myHashTable.get('aki'));
  console.log(myHashTable.get('oop1'));

  myHashTable.remove('k21');
  myHashTable.remove('a7');
}

-->head-->[object Object]
,,,,,,,,,-->a7-哈希1,,,,
-->head-->[object Object]-->[object Object]
,,,,,,,,,-->a7-哈希1-->b6-哈希2,,,,
-->head-->[object Object]
,,,-->k3i-哈希3,,,,,,-->a7-哈希1-->b6-哈希2,,,,
-->head-->[object Object]
,,,-->k3i-哈希3,,,,,,-->a7-哈希1-->b6-哈希2,,-->k21-哈希4,,
-->head-->[object Object]
,,,-->k3i-哈希3,,,-->oop1-哈希5,,,-->a7-哈希1-->b6-哈希2,,-->k21-哈希4,,
undefined
哈希5
,,,-->k3i-哈希3,,,-->oop1-哈希5,,,-->a7-哈希1-->b6-哈希2,,,,
,,,-->k3i-哈希3,,,-->oop1-哈希5,,,-->b6-哈希2,,,,