第五章 佇列與雙端佇列

自我理解

說明

佇列是遵循先進先出(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對應訓練

標籤：JavaScript

上一篇：第四章 堆疊

下一篇：第六章 鏈表