常用的数据结构：队列、栈、链表、树等…
- 队列
- 先进先出，push shift
- 举例: 事件环
- 栈
- 后进先出，push pop
- 举例： 方法调用栈、路由切换、浏览器对而历史记录(两个栈)、判断标签是否闭合
1. 栈型结构举例
1.1 方法调用栈
function a(){
function b(){
function c(){
}
c();
}
b();
}
a();
- 错误的说法：每次执行都会创建一个作用域。
- 错误的原因：声明时就定义了作用域，而不是执行时创建的。
- 运行时产生的是执行上下文。这里所谓的栈，就是执行上下文栈。
- 上面这段代码，执行上下文栈是：[a, b, c]，因为先执行的是a，a执行了再执行b，最后是c，所以是a, b, c。但是执行完后，销毁的顺序先是c，等c销毁完了是b，最后是a
- 上面所说的执行上下问栈，是一层层的关系，并不是包含关系，并不是说c的执行上下文在b的里面，而是说整个执行栈中，c的执行上下文在b的上面
1.2 浏览器的历史记录
- 有两个栈，假设栈A和栈B
- 当我进入www.baidu.com时，那么就会在栈A中push，栈A就成了[www.baidu.com]
- 这时我再进去www.taobao.com时，那么就会在栈A中再push，栈A就成了[www.baidu.com, www.taobao.com]
- 然后这时候我按浏览器后退键，那么栈A就会pop，栈A就成了[www.baidu.com],这时候栈B就会push进栈A出来的网站，也就是栈B变成了[www.taobao.com]
- 如果这时候按前进，B就会pop，将pop出的给栈A，也就是A会push进去。再按后退，A就会pop出去，B会push进A出来的网站。
- 经过上面一系列操作后，这时候栈A是[www.baidu.com]，栈B是[www.taobao.com]。如果这时候在浏览器输入www.jd.com，那么栈B就会被清空，栈A就会push进www.jd.com，也就是A变成了[www.baidu.com, www.jd.com]，栈B就成了[]
- 这时候你前进后退就跟之前一样了
1.3 判断标签是否闭合
- 比如有
- 当我遇到开始标签的时候，就往栈中push，如上面就是[div, span]
- 当我遇到结束标签的时候，就从栈中pop，比如上面先遇到，那么栈就成了[div]，又遇到，就栈就成了[]
- 最后如果栈是空的，那么说明这段html中所有标签都是闭合的，否则就是有问题的，当然单标签除外。
2. 手写一个链表结构
-
数组的shift是比较浪费性能的，每次弹出一个后续内容都会前进，所以这时候就需要链表（通过指针连接起来）
-
链表查找、删除的性能平均复杂度是O(n)，跟数组遍历复杂度一样的，都是O(n)。但是链表可以优化头尾操作，比较合适。
-
我们可以使用链表来实现 栈 或 队列
-
链表的实现：
class Node{
constructor(element, next){
this.element = element; // 节点元素
this.next = next; // 指向下一个的指针
}
}
// 链表类
class LinkedList{
constructor(){
this.head = null; // 链表的头
this.size = 0; // 链表的大小
}
// 增加
add(index, element){
if (arguments.length === 1) {
element = index; // 如果参数只有一个，那么相当于向链表最后一个添加。这时候，第一个参数其实就是元素值
index= this.size;
}
if (index < 0 || index > this.size) throw new Error('链表索引异常');
if (index === 0) {
let oldHead = this.head;
this.head = new Node(element, oldHead) // element是当前节点，oldHead老的节点就成为下一个节点了
} else {
let preNode = this.getNode(index - 1);
preNode.next = new Node(element, preNode.next); // 上一个的next指向新增的元素，新增的元素的next指向原先上一个的next
}
this.size++; // 每次添加完，长度应该加1
// console.log(index, element)
}
// 删除
remove(index){
if (index < 0 || index >= this.size) throw new Error('链表索引异常');
let oldNode = null;
if (index === 0) {
oldNode = this.head;
this.head = oldNode && oldNode.next;
} else {
let prevNode = this.getNode(index - 1);
oldNode = prevNode.next;
prevNode.next = prevNode.next.next;
}
this.size--;
return oldNode && oldNode.element; // 返回删除的元素
}
// 查找,获取某个节点
getNode(index){
let current = this.head; // 从头开始找
for(let i = 0; i < index; i++) {
current = current.next;
}
return current;
}
// 获取链表的长度，节点的总个数
length(){
return this.size;
}
}
module.exports = LinkedList;
3.将列表封装成队列
const LinkedList = require('./6.链表结构');
// 将链表进行封装，封装成队列
class Queue{ // 队列主要是添加和删除
constructor(){
this.ll = new LinkedList();
}
offer(element){ // 入队列
this.ll.add(element);
return this;
}
poll(){ // 出队列,也就是从头部删除
this.ll.remove(0);
return this;
}
getQueue(){
let queue = [];
for(let i = 0; i < this.ll.length(); i++) {
let current = this.ll.getNode(i).element;
queue.push(current)
}
return queue;
}
}
module.exports = Queue;