---恢复内容开始---
1、常用数据结构
- 栈：一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
- 队列：与上相反，一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。
- 链表：存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的；每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针/链接）组成。
- 集合：由一组无序且唯一（即不能重复）的项组成；这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。
- 字典：以 [键，值] 对为数据形态的数据结构，其中键名用来查询特定元素，类似于 Javascript 中的
Object。 - 散列：根据关键码值（Key value）直接进行访问的数据结构；它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度；这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- 树：由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。
- 图：图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。
2、栈
1)栈是一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，
称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
通俗来讲，一摞叠起来的书或盘子都可以看做一个栈，我们想要拿出最底下的书或盘子，一定要现将上面的移走才可以。
2)在 Javascript 中我们可以使用数组的原生方法实现一个栈/队列的功能，鉴于学习目的，我们使用类来实现一个栈
class Stack { constructor() { this.items = [] } // 入栈 push(element) { this.items.push(element) } // 出栈 pop() { return this.items.pop() } // 末位 get peek() { return this.items[this.items.length - 1] } // 是否为空栈 get isEmpty() { return !this.items.length } // 尺寸 get size() { return this.items.length } // 清空栈 clear() { this.items = [] } // 打印栈数据 print() { console.log(this.items.toString()) } }
3、队列
与栈相反，队列是一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；
队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。
使用push和shift我们可以快速实现队列
class Queue { constructor(items) { this.items = items || [] } enqueue(element){ this.items.push(element) } dequeue(){ return this.items.shift() } front(){ return this.items[0] } clear(){ this.items = [] } get size(){ return this.items.length } get isEmpty(){ return !this.items.length } print() { console.log(this.items.toString()) } }
3）优先队列
现实中的例子是医院的(急诊科)候诊室。医生会优先处理病情比较严重的患者。通常，护士会鉴别分类，根据患者病情的严重程度放号。
一个优先队列的例子如下
class PriorityQueue { constructor() { this.items = [] } priorityPush(value, priority) { let thisItem = { value, priority } if (this.isEmpty()) { this.items.push(thisItem) } else { let preIndex = this.items.findIndex((item) => item.priority < thisItem.priority) if (preIndex > -1) { this.items.splice(preIndex, 0, thisItem) } else { this.items.push(thisItem) } } } isEmpty() { return this.items == [] } priorityShift() { return this.items.shift() } clear() { return this.items = [] } print() { return console.log(this.items) } }
4)循环队列
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，
并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
这种循环队列可以以单链表、队列的方式来在实际编程应用中来实现。
class LoopQueue extends Queue { constructor(items) { super(items) } getIndex(index) { const length = this.items.length return index > length ? (index % length) : index } find(index) { return !this.isEmpty ? this.items[this.getIndex(index)] : null } }
4、链表
1)
要存储多个元素，数组（或列表）可能是最常用的数据结构。
每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。
然而，这种数据结构有一个缺点：在大多数语言中，数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素；
尽管 JavaScript 中的Array类方法可以帮我们做这些事，但背后的处理机制同样如此。
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点
和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了链表的结构:
数组的另一个细节是可以直接访问任
何位置的任何元素，而要想访问链表中间的一个元素，需要从起点(表头)开始迭代列表直到找到所需的元素。
2)普通链表的实现：
//节点类 class Node { constructor(element) { this.element = element this.next = null } } //链表类 class LinkedList { constructor() { this.head = null//头指针,也是第一个链表元素的引用 this.length = 0 } //追加 push(element) { let newEle = new Node(element) if (this.head == null) { this.head = newEle } else { let current = this.head while (current.next) { current = current.next } current.next = newEle } this.length++ return newEle } //任意位置追加 pushAnywhere(element, index) { let newEle = new Node(element) if (index < 0) return false if (this.head == null) { this.head = newEle this.length++ return newEle } if (index >= this.length) index = this.length if (index == 0) { newEle.next = this.head this.head = newEle this.length++ return newEle } let i = 0 let preEle = null let current = this.head while (i++ < index) { preEle = current current = current.next } preEle.next = newEle newEle.next = current this.length++ return newEle } //任意位置删除 deleteAnywhere(index) { if (index < 0 || index >= this.length || this.length == 0) return false if (index == 0) { this.head = this.head.next this.length-- return true } let i = 1 let preEle = this.head let targetEle = preEle.next let nxtEle = targetEle.next while (i++ < index) { preEle = targetEle targetEle = nxtEle nxtEle = nxtEle.next } preEle.next = nxtEle this.length-- return true } isEmpty() { return this, length == 0 } query(index) { if(index<0||index>=this.length) return false let current = this.head let i = 0 while (i++ < index) { current=current.next } return console.log(current) } clear(){ this.length=0 this.head=null return true } print(){ let current=this.head for(let i=0;i<this.length;i++){ console.log(current) current=current.next } } }
3）双向链表：
链表有多种不同的类型，这一节介绍双向链表。双向链表和普通链表的区别在于，
在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，
链接是双向的:一个链向下一个元素， 另一个链向前一个元素，如下图所示:·
双向链表提供了两种迭代列表的方法:从头到尾，或者反过来。
我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中，
如果迭代列表时错过了要找的元素，就需要回到列表 起点，重新开始迭代。这是双向链表的一个优点。
双向列表的实现如下：
//双向节点类 class BothNode { constructor(element) { this.element = element this.next = null this.pre = null } } //双向链表类 class BothLinkedList { constructor() { this.head = null//头指针,也是第一个链表元素的引用 this.tail = null//尾指针，也是最后一个链表元素的引用 this.length = 0 } //末尾追加 push(element) { let newEle = new BothNode(element) if (this.length == 0) { this.head = newEle this.tail = newEle } else { let current = this.tail newEle.pre = current current.next = newEle this.tail = newEle } this.length++ return newEle } //任意位置追加 pushAnywhere(element, index) { let newEle = new Node(element) if (index < 0) return false if (this.length == 0) { this.head = newEle this.tail = newEle return newEle } if (index >= this.length) index = this.length if (index == 0) { newEle.next = this.head this.head = newEle this.length++ return newEle } let i = 0 let preEle = null let current = this.head while (i++ < index) { preEle = current current = current.next } newEle.pre = preEle newEle.next = current preEle.next = newEle current.pre = newEle this.length++ return newEle } //任意位置删除 deleteAnywhere(index) { if (index < 0 || index >= this.length || this.length == 0) return false if (index == 0) { this.head = this.head.next this.head.pre = null this.length-- return true } let i = 1 let preEle = this.head let targetEle = preEle.next let nxtEle = targetEle.next while (i++ < index) { preEle = targetEle targetEle = nxtEle nxtEle = nxtEle.next } preEle.next = nxtEle nxtEle.pre = preEle this.length-- return true } isEmpty() { return this.length == 0 } query(index) { if (index < 0 || index >= this.length) return false let current = this.head let i = 0 while (i++ < index) { current = current.next } return console.log(current) } clear() { this.length = 0 this.head = null return true } print() { let current = this.head for (let i = 0; i < this.length; i++) { console.log(current) current = current.next } } }
链表相比数组最重要的优点，那就是无需移动链表中的元素，就能轻松地添加和移除元素。
因此，当你需要添加和移除很多元素 时，最好的选择就是链表，而非数组。
5）循环链表
链表最后的元素的next指回表头元素
一个循环链表的 实例如下
//节点类 class CircleNode { constructor(element) { this.element = element this.next = null } } //链表类 class CircleLinkedList { constructor() { this.head = null//头指针,也是第一个链表元素的引用 this.length = 0 } //追加 push(element) { let newEle = new Node(element) if (this.head == null) { this.head = newEle this.head.next = this.head } else { let current = this.head while (current.next) { current = current.next } newEle.next = this.header current.next = newEle } this.length++ return newEle } //任意位置追加 pushAnywhere(element, index) { let newEle = new Node(element) if (index < 0) return false if (this.head == null) { this.head = newEle this.head.next = this.head this.length++ return newEle } if (index >= this.length) index = this.length if (index == 0) { newEle.next = this.head this.head = newEle this.length++ return newEle } let i = 0 let preEle = null let current = this.head while (i++ < index) { preEle = current current = current.next } preEle.next = newEle newEle.next = current if (newEle.next == null) { newEle.next = this.header } this.length++ return newEle } //任意位置删除 deleteAnywhere(index) { if (index < 0 || index >= this.length || this.length == 0) return false if (index == 0) { this.head = this.head.next this.length-- return true } let i = 1 let preEle = this.head let targetEle = preEle.next let nxtEle = targetEle.next while (i++ < index) { preEle = targetEle targetEle = nxtEle nxtEle = nxtEle.next } if(index==this.length-1){ nxtEle=this.head } preEle.next = nxtEle this.length-- return true } isEmpty() { return this, length == 0 } query(index) { if (index < 0 || index >= this.length) return false let current = this.head let i = 0 while (i++ < index) { current = current.next } return console.log(current) } clear() { this.length = 0 this.head = null return true } print() { let current = this.head for (let i = 0; i < this.length; i++) { console.log(current) current = current.next } } }