数据结构（搁置）

• JS中的数组是多种数据结构的封装，它存在快慢两种模式，快时数组开辟默认的内存空间，保存的每一项都是指针，所以能够保存不同类型的数据，同时有能实现数组的任意位高速读取的优势。但是当插入或删除时导致的空间不足，会导致需要开辟新的内存空间并整体复制当前值。慢的模式没有了解。
• 数据结构实际上是数据在内存中的储存方法和读取方法。比如：栈和队列的存储都是一样的，使用一个连续的内存空间。他们的区别在于队列多使用了3个内存空间来保存位置变量，他们能够实现的功能也不一样。
• 数据结构只是一种理论上的内存使用方式，在不同的语言中其实现方式是不同。数据结构更在乎的是在内存使用的不同方式（应该是结合了长期使用总结的功能需求上总结出来的）
• 数据结构是为了方便程序访问数据和提高程序性能而使用，就像算法一样，优秀的数据结构能够以指数级提高程序速度
• 实际在具体的编程实践中，数据结构的优化变得相当弱，更应该把精力关注在代码结构的优化及代码语义化上。（暂时这么认为中？数据结构或许在TypeScript中得到了优化）

栈

栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则

• 可用于判断是否对称，例如判断括号是否对称
• 用JS的数组实现栈不会有多余的开销，因为它们都一样，当空间不足时需要重新开辟空间并复制原有数据

var isValid = function (s) {
  let map = {
    '(': -1,
    ')': 1,
    '[': -2,
    ']': 2,
    '{': -3,
    '}': 3
  }
  let stack = []
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] < 0) {
      stack.push(s[i])
    } else {
      let last = stack.pop()
      if (map[last] + map[s[i]] != 0) return false
    }
  }
  if (stack.length > 0) return false
  return true
};

队列

队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。

• 循环队列，更高效率的队列实现
• 相对于JS数组，应该是一种更高效率的实现方式。JS中数组在快模式时，头部的出数据会导致数组的拷贝，所以以下队列的方式效率会更高。（可能）

class SqQueue {
  constructor(length) {
    this.queue = new Array(length)
    this.first = 0
    this.last = 0
    this.size = 0
    this.base = length
  }
  enQueue(item) {
    this.queue[this.last] = item
    this.size++
    this.last = (this.last + 1) % this.queue.length
    if (this.first === this.last) {
      this.__resize(this.size + this.base)
    }
  }
  deQueue() {
    if (this.first === this.last) {
      return undefined
    }
    let r = this.queue[this.first]
    this.queue[this.first] = null
    this.first = (this.first + 1) % this.queue.length
    this.size--
    if (this.size <= this.queue.length - 2 * this.base) {
      this.__resize(this.queue.length - this.base)
    }
    return r
  }
  getHeader() {
    if (this.first === this.last) {
      return undefined
    }
    return this.queue[this.first]
  }
  getLength() {
    return this.size
  }
  __resize(length) {
    let q = new Array(length)
    for (let i = 0; i < this.size; i++) {
      q[i] = this.queue[(i + this.first) % this.queue.length]
    }
    this.queue = q
    this.first = 0
    this.last = this.size
  }
}

链表

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。（使用对象树实现）

• 链表在删除和插入上的表现优于数组，因为数组需要移动改变位之后的所有数据的位置（其实还受查询插入位影响，数组查询快于链表，插入时数组需要整体移动，JS中数组做了优化，实际综合效率哪个更高不确定）
• 查询效率低于数组，总要从第一个依次向下查询
• 能够确定的是链表相对于栈和队列，它在头部添加和删除的表现上最为优秀。
• 链表和树的内存本质是一样的，只是数据组织结构不同

class Node {
  constructor(v, next) {
    this.value = v
    this.next = next
  }
}
class LinkList {
  constructor() {
    this.size = 0
    this.dummyNode = new Node(null, null)
  }
  __find(header, index, currentIndex) {
    if (index === currentIndex) return header
    return this.__find(header.next, index, currentIndex + 1)
  }
  __addNode(v, index) { // 在某个位置添加，实际是改变这个位置上一项next的指向，及这个新增项next指向这个位置上一项next原本的指向
    if (index < 0 || index > this.size) throw Error('Index error')
    let prev = this.__find(this.dummyNode, index, 0)
    prev.next = new Node(v, prev.next)
    this.size++
    return prev.next
  }
  insertNode(v, index) {
    return this.__addNode(v, index)
  }
  addToFirst(v) {
    return this.__addNode(v, 0)
  }
  addToLast(v) {
    return this.__addNode(v, this.size)
  }
  __checkIndex(index){
    if (index < 0 || index > this.size-1) throw Error('Index error')
  }
  __removeNode(index) { // 获取删除项的前一项，修改它的next为删除项的next，设置删除项的next为null（删除关联让内存释放空间）
    this.__checkIndex(index)
    let prev = this.__find(this.dummyNode, index, 0)
    let node = prev.next
    prev.next = node.next
    node.next = null
    this.size--
    return node
  }
  removeFirstNode() {
    return this.__removeNode(0)
  }
  removeLastNode() {
    return this.__removeNode(this.size-1)
  }
  getNode(index) {
    this.__checkIndex(index)
    return this.__find(this.dummyNode, index, 0).next.value
  }
  getSize() {
    return this.size
  }
}

树

二叉树

二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当一颗树的叶数量数量为满时，该树可以称之为满二叉树。

• 树本身存在层级结构，能够方便的自上而下或自下而上获取数据

二分搜索树

二分搜索树也是二叉树，拥有二叉树的特性。但是区别在于二分搜索树每个节点的值都比他的左子树的值大，比右子树的值小。

• 这种存储方式很适合于数据搜索。用于整理一堆数据，方便后面查询比较。
• 容易获取最大值和最小值
• 也方便获取排序好的数据，本身结构就带有顺序特点
• 搜索效率其实和添加顺序还是有关的，如果倒序添加数据，这个二叉树就会变成链表
• 二分搜索树只是数据结构，用于排序的话数组的sort会快得多

// 创建二叉树

class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}
class BST {
  constructor() {
    this.root = null
    this.size = 0
  }
  _addChild(node, v) {
    if (!node) {
      this.size++
      return new Node(v)
    }
    if (node.value > v) {
      node.left = this._addChild(node.left, v)
    } else if (node.value < v) {
      node.right = this._addChild(node.right, v)
    }
    return node
  }
  addNode(v) {
    this.root = this._addChild(this.root, v)
  }
  getSize() {
    return this.size
  }
}

// 三种深度遍历方法，分别是先序遍历、中序遍历、后序遍历 

  // 先序遍历可用于打印树的结构（似乎并不能很好体现）
  _pre(node) {
    if (node) {
      console.log(node.value)
      this._pre(node.left)
      this._pre(node.right)
    }
  }
  preTraversal() {
    this._pre(this.root)
  }

  // 中序遍历得到排好序的值
  _mid(node) {
    if (node) {
      this._mid(node.left)
      console.log(node.value)
      this._mid(node.right)
    }
  }
  midTraversal() {
    this._mid(this.root)
  }
  
  // 后序遍历可用于先操作子节点再操作父节点的场景（vue钩子mounted先执行子节点的后执行父节点的，保证所有子节点挂载完才挂载父节点）
  _back(node) {
    if (node) {
      this._back(node.left)
      this._back(node.right)
      console.log(node.value)
    }
  }
  backTraversal() {
    this._back(this.root)
  }

// 广度遍历
// 利用之前讲过的队列结构来完成

  breadthTraversal() {
    if (!this.root) return null
    let size = Math.pow(2,Math.ceil(Math.log(this.size + 1)/Math.log(2))-1) // 二叉树的总长度决定了插入队列时占的最大位置（依据等比数列公式获取），使用最大位置能加快插入读取速度，但也更消耗内存。还有待优化
    let q = new SqQueue(size)
    q.enQueue(this.root)
    while (q.getLength()) {
      let n = q.deQueue()
      console.log(n.value)
      if (n.left) q.enQueue(n.left)
      if (n.right) q.enQueue(n.right)
    }
  }

// 获取最大值和最小值
  _getNode(node,key) {
    if (!node[key]) return node.value
    return this._getNode(node[key],key)
  }
  getMin() {
    return this._getNode(this.root,'left')
  }
  getMax() {
    return this._getNode(this.root,'right')
  }

// 向下取整向上取整

  floor(v) {
    let node = this._floor(this.root, v)
    return node ? node.value : null
  }
  _floor(node, v) {
    if (!node) return null
    if (node.value > v) {
      return this._floor(node.left, v)
    }
    if(node.value < v) {
      let right = this._floor(node.right, v) 
      if (right) return right
    }
    return node
  }
  top(v){
    let node = this._top(this.root, v)
    return node ? node.value : null
  }
  _top(node,v){
    if (!node) return null
    if (node.value < v) {
      return this._top(node.right, v)
    }
    if(node.value > v) {
      let left = this._top(node.left, v) 
      if (left) return left
    }
    return node
  }

// 返回第K项

  select(k) {
    let node = this._select(this.root, k)
    return node ? node.value : null
  }
  _select(node, k) {
    if (!node) return null
    let size = node.left ? node.left.size  : 0
    if (size > k) return this._select(node.left, k)
    if (size < k) return this._select(node.right, k - size - 1)
    return node
  }