欢迎光临
我的个人博客网站

第五章 队列与双端队列


自我理解

说明

队列是遵循先进先出(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;   } }  

leetcode对应训练

赞(0) 打赏
未经允许不得转载:张拓的天空 » 第五章 队列与双端队列
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏