- A+
所属分类：Web前端
自我理解
说明
队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项.队列在尾部添加新元素,并从顶部移除元素.最新添加的元素必须排在队列的末尾.
使用
当我们在浏览器打开新标签时,就会创建一个任务队列.这是因为每个标签都是一个单线程处理所有任务,称为事件循环.浏览器要赋值多个任务,如渲染HTML,执行JavaScript代码,处理用户交互(用户输入,鼠标点击等),执行和处理异步请求.
更多事件循环
队列
简单图解
队列和栈不同,就像排队买票,先排上队的先开始买票,所以是一个先进先出(FIFO)的数据结构
一个队列的基本方法
- enqueue(element(s)) : 向队列尾部添加一个(或多个)新的项
- dequeue() :移除队列的第一项(即排在队列最前面的项)并返回被移除的元素
- peek() : 返回队列中的第一个元素---最先被添加上,也将最先被移除的元素.队列不做任何变动(不移除元素,只返回信息),该方法在其他语言中也可以叫作front
- isEmpty() : 如果队列中不包含任何元素,返回true,否则返回false
- clear() : 清除所有元素
- size() : 返回队列包含的元素个数, 与数组的length属性类似
export default class Queue<T> { // 队列数据集 private queueList: any; // 队列的个数 private beforeIndex: number; // 队列当前最后一个的位置 private lastIndex: number; constructor() { this.queueList = {}; this.lastIndex = 1; this.beforeIndex = 1; } //插入 enqueue(...items: Array<T>): void { let newIndex = this.lastIndex; for (let i = 0, len = items.length; i < len; i++) { this.queueList[newIndex++] = items[i]; } this.lastIndex = newIndex; } //移除 dequeue(): (T | undefined) { if (this.isEmpty()) { return undefined; } let result = this.queueList[this.beforeIndex]; delete this.queueList[this.beforeIndex]; this.beforeIndex++; return result; } //队列最前一个数 peek(): (T | undefined) { return this.queueList[this.beforeIndex]; } //队列中是否有数据 isEmpty(): boolean { return this.size() === 0; } //队列里的数据个数 size(): number { return this.lastIndex - this.beforeIndex; } //清理数据 clear(): void { this.beforeIndex = 0; this.lastIndex = 0; this.queueList = {}; } } 双端队列
简单图解
双端队列与队列的不同点在于,队列是先进先出,所以是一端出口,一端进口,而双端队列,就是两边都可以进也都可以出. 这就像你和你女朋友去外面玩,看到一个烤串店排了老长的队,但是又不知道有什么好吃的,所以你女朋友叫你去后面排队(后端插入数据),她去前面看看菜品(前端插入数据),然后你女票去前面看了,发现很多好吃的,但是这个时候她不太想吃这些!所以她又退了回来(移除前端数据),然后告诉你,我们以后再来吃吧!你们就一起走了(你退出队列,尾部移除)
一个双端队列的基本方法
- addFront(element(s)) : 在双端队列前端添加新的元素
- addBack() :该方法在双端队列后端添加新的元素
- removeFront() : 该方法会从双端队列前端移除第一个元素
- removeBack() : 该方法会从双端队列后端移除第一个元素
- peekFront() : 该方法会返回双端队列前端第一个元素
- peekBack() : 该方法会返回双端队列后端第一个元素
export default class Deque<T> { //数据源 private dequeList: any; //起始位置 private startIndex: number; //结束指针的后一个 private endIndex: number; constructor() { this.dequeList = {}; this.startIndex = 0; this.endIndex = 0; } // 前面添加的时候,startIndex位置有元素 addFront(...elements: Array<T>): void { //没有元素的情况下,我会将这个添加交给后置添加 if (this.isEmpty()) { this.addBack(...elements); return; } let index = this.startIndex; for (let i = elements.length - 1; i >= 0; i--) { // 因为startIndex有元素,所以先减后赋值 this.dequeList[--index] = elements[i]; } this.startIndex = index; } // 后面添加的时候,endIndex位置没有元素 addBack(...elements: Array<T>): void { let index = this.endIndex; elements.forEach(item => { //因为规定endIndex位置没有元素,所以先赋值再++ this.dequeList[index++] = item; }) this.endIndex = index; } // 前面移除一个元素 removeFront(): (T | undefined) { if (this.isEmpty()) { return undefined; } let result = this.dequeList[this.startIndex]; delete this.dequeList[this.startIndex]; this.startIndex++; return result; } //后面移除一个元素 removeBack(): (T | undefined) { if (this.isEmpty()) { return undefined; } //endIndex这个时候是没有值的 this.endIndex--; let result = this.dequeList[this.endIndex]; delete this.dequeList[this.endIndex]; return result; } peekFront(): T { return this.dequeList[this.startIndex]; } peekBack(): T { return this.dequeList[this.endIndex - 1]; } isEmpty() { return this.size() === 0; } size() { return this.endIndex - this.startIndex; } clear() { this.dequeList = {}; this.startIndex = 0; this.endIndex = 0; } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.dequeList[this.startIndex]}`; for (let i = this.startIndex + 1; i < this.endIndex - 1; i++) { objString = `${objString},${this.dequeList[i]}`; } return objString; } } 书中代码
队列
export default class Queue<T> { private count: number; private lowestCount: number; private items: any; constructor() { this.count = 0; this.lowestCount = 0; this.items = {}; } enqueue(element: T) { this.items[this.count] = element; this.count++; } dequeue() { if (this.isEmpty()) { return undefined; } const result = this.items[this.lowestCount]; delete this.items[this.lowestCount]; this.lowestCount++; return result; } peek() { if (this.isEmpty()) { return undefined; } return this.items[this.lowestCount]; } isEmpty() { return this.size() === 0; } clear() { this.items = {}; this.count = 0; this.lowestCount = 0; } size() { return this.count - this.lowestCount; } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.items[this.lowestCount]}`; for (let i = this.lowestCount + 1; i < this.count; i++) { objString = `${objString},${this.items[i]}`; } return objString; } } 双端队列
export default class Deque<T> { private count: number; private lowestCount: number; private items: any; constructor() { this.count = 0; this.lowestCount = 0; this.items = {}; } addFront(element: T) { if (this.isEmpty()) { this.addBack(element); } else if (this.lowestCount > 0) { this.lowestCount--; this.items[this.lowestCount] = element; } else { for (let i = this.count; i > 0; i--) { this.items[i] = this.items[i - 1]; } this.count++; this.items[0] = element; } } addBack(element: T) { this.items[this.count] = element; this.count++; } removeFront() { if (this.isEmpty()) { return undefined; } const result = this.items[this.lowestCount]; delete this.items[this.lowestCount]; this.lowestCount++; return result; } removeBack() { if (this.isEmpty()) { return undefined; } this.count--; const result = this.items[this.count]; delete this.items[this.count]; return result; } peekFront() { if (this.isEmpty()) { return undefined; } return this.items[this.lowestCount]; } peekBack() { if (this.isEmpty()) { return undefined; } return this.items[this.count - 1]; } isEmpty() { return this.size() === 0; } clear() { this.items = {}; this.count = 0; this.lowestCount = 0; } size() { return this.count - this.lowestCount; } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.items[this.lowestCount]}`; for (let i = this.lowestCount + 1; i < this.count; i++) { objString = `${objString},${this.items[i]}`; } return objString; } } 
