【JS】数据结构之队列

基本概念

• 队列：它是一种运算受限的线性表，FIFO（先进先出）
• 特性：它只运行表的前端进行删除操作，在表的后端进行添加操作
• 面对无法同时处理多个请求的场景，我们通常就会使用队列，先进先出，一个一个的解决问题，保证有序。

JavaScript：是单线程语言，浏览器只会分配一个主线程给JS，用来执行任务，但是一次只能执行一个任务

• 单线程：所有任务需要排队，前一个任务结束以后，才能执行下一个任务
• 避免复杂性：比如一个线程在一个DOM上添加了内容，另一个线程又删除了这个DOM节点。
• H5、web worker标准：它是允许JS创建多个线程，但是子线程完全受主线程控制的，而且子线程是不可以操作DOM的。

如果前一个任务耗时很长，发起一个请求，网络很慢，后面的那个任务是不是要一直等着？并不是

• IO（输入输出）的时候，主线程不会去管IO，而是挂起处于等待中的任务，先运行排在后面的任务，等IO设备返回了结果，再回过头，把挂起的等待中任务继续执行下去。
• 于是就有来：同步任务 和 异步任务

同步任务：
- 在`主线程`上排队执行的任务，只有前一个任务执行完毕以后，才能够去执行下一个任务。
异步任务：
- 不进入`主线程`，而是进入`任务队列`，只有`任务队列`通知`主线程`后，某个异步任务可以执行了，这个任务才会进入`主线程`执行。
1
2
3
4

• 代码执行过程：

1. 所有的同步任务都在主线程执行，形成一个执行栈，同步任务执行完后立即出栈，让出主线程。
2. 主线程外，还存在一个`任务队列（Task Queue）`，只要有了异步代码，就在`任务队列`放置一个事件
3. 一旦`执行栈`所有的同步任务执行完毕以后，主线程就会去读取`任务队列`， 看任务队列有哪些对应的异步任务，结束等待状态，进入`执行栈`，开始执行。
1
2
3

• 主线程执行完毕以后，从事件队列中去读取任务队列的过程，我们称之为事件循环（Event Loop）
• 任务队列：存在两个队列，一个是宏任务队列，一个是微任务队列
• 主线程执行顺序可以理解为：同步任务=>微任务=>宏任务

宏任务：I/O，定时器，事件绑定、ajax...
微任务：Promise.then、catch、finally，process.nextTick... 
1
2

代码实现

• 使用JavaScript实现一个队列

class Queue {
	constructor() {
		this.items = [];
	}
	// 入列
	enqueue(ele){
		this.items.push(ele);
	}
	// 出列
	dequeue() {
		return this.items.shift();
	}
	// 查看队列前端元素
	front(){
		return this.items[0];
	}
	// 查看队列后端元素
	rear(){
		return this.items[this.items.length - 1];
	}
	// 查看队列是否为空
	isEmpty(){
		return this.items.length === 0;
	}
	// 查看队列中元素个数
	size(){
		return this.items.length;
	}
	// 清空队列
	clear(){
		this.items = []
	}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue('a');
// 出列
queue.dequeue();
queue.dequeue();
console.log(queue);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

• 运行结果：