时间戳

首页 > 技术文章 > 第五章 队列与双端队列

第五章 队列与双端队列

wangzhaoyv 2020-11-15 13:09 原文

自我测试

本篇文章的测试用例及调试方法见前言

说明

队列是遵循先进先出(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对应训练

推荐阅读