JavaScript 數據結構與演算法2(隊列和雙端隊列)

學習數據結構的 git 程式碼地址: //gitee.com/zhangning187/js-data-structure-study

1、隊列和雙端隊列

　　隊列和棧非常類似，但是使用了與 後進先出 不同的原則。雙端隊列是一種將棧的原則和隊列的原則混合在一起的數據結構。

1.1 隊列數據結構

　　隊列是遵循先進先出（FIFO）原則的一組有序的項。隊列在尾部添加新元素，並從頂部移除元素。最新添加的元素必須排在隊列的末尾。

　　最常見的例子就是排隊。排隊打飯，排隊買票等，電腦裡面有排隊列印等。

1.1.1 創建隊列類

class Queue {
  constructor() {
    // 記錄隊列的長度，大小
    this.count = 0;
    // 記錄隊列的第一個元素
    this.lowestCount = 0;
    // 這裡也可以使用數組，但是為了獲取元素時更高效，使用對象存儲元素，
    // 和 Stack 非常類似，只是添加和移除元素的原則不同
    this.items = {};
  }
}

1.1.2 向隊列添加元素

  // 向隊列尾部添加項
  // 這裡的實現方法和 Stack 棧中的方式相同。將 count 作為items中的鍵對應元素作為它的值
  enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }

1.1.3 從隊列移除元素

  // 移除第一項，並返回被移除的元素
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    // 刪除最先進去的元素
    delete this.items[this.lowestCount];
    // 最先添加的元素位置，也要向後移動
    this.lowestCount++;
    return result;
  }

只有 enqueue 方法和 dequeue 方法可以添加和移除元素，這樣就確保了 Queue 類遵循先進先出原則。

1.1.4 查看隊列頭元素

  // 返回隊列中第一個元素，最先被添加，也將是最先被移除的元素，隊列不做任何變動，只是取值
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

1.1.5 檢查隊列是否為空和獲取隊列長度

  // 是否為空隊列
  isEmpty() {
    return this.count === 0;
  }

  // 隊列元素個數
  size() {
    return this.count - this.lowestCount;
  }

1.1.6 清空隊列和toString方法

  // 清空隊列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let queueString = this.items[this.lowestCount];
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      queueString += `,${this.items[i]}`;
    }
    return queueString;
  }

1.2 雙端隊列數據結構

　　雙端隊列（deque，或 double-ended queue）是一種允許我們同時從前端或後端添加或移除元素的特殊隊列。

　　雙端隊列生活中的例子，電影院、餐廳排隊等。一個人剛買了票還想問一些問題，可以直接在隊伍的最前面詢問資訊，另外，在隊伍尾部的人不想排隊了可以直接離開隊伍。

　　雙端隊列的一個常見應用是存儲一系列的撤銷操作。每當用戶在軟體中進行一個操作，該操作會被存在一個雙端隊列中（就像一個棧裡面）。雙端隊列同時遵守了先進先出和後進先出的原則，可以說它是把隊列和棧相結合的一種數據結構。

1.2.1 創建 Deque 類

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
}

　　雙端隊列是一個特殊的隊列，構造函數和部分方法和隊列相同，isEmpty、clear、size、toString

1.2.2 實現雙端隊列的方法

// 前端添加元素
  addFront(element) {
    if (this.isEmpty()) {// 空隊列
      this.addBack(element);
    } else {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    }
  }

  // 後端添加元素
  addBack(element) {
    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];
  }

1.3 使用隊列和雙端隊列解決問題

　　使用隊列模擬擊鼓傳花遊戲，使用雙端隊列檢查一個短語是否為迴文。

1.3.1 循環隊列--擊鼓傳花遊戲

　　隊列可以修改為很多的不同隊列，其中可以修改為一種循環隊列。循環隊列的一個例子就是擊鼓傳花遊戲--多人圍成一個圈，把花儘快地傳遞給旁邊的人。某一刻傳花停止，花在誰手裡誰就退出，直到最後一個人為勝者。

// 擊鼓傳花
import {Queue} from './Queue.js';

// list: 人數 num: 傳遞次數
function hotPotato(list, num) {
  const queue = new Queue();
  // 淘汰的列表
  const elimitatedList = [];

  for (let i = 0; i < list.length; i++) {
    // 依次添加到隊列中
    queue.enqueue(list[i]);
  }
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      // 隊列開頭移除一項添加到隊尾，
      // 模擬擊鼓傳花（如果你把花傳給旁邊的人，你的淘汰威脅就立即解除了）
      queue.enqueue(queue.dequeue());
    }
    // 淘汰的放在數組中
    // 一旦達到傳遞次數，拿著花的那個人就被淘汰了
    elimitatedList.push(queue.dequeue());
  }
  return {
    eliminated: elimitatedList,
    winner: queue.dequeue()
  };
}

const names = ['zn1', 'zn2', 'zn3', 'zn4', 'zn5'];
const result = hotPotato(names, 7);
console.log(result);// zn1 為 winner

1.3.2 迴文檢查器

　　迴文是正反都能讀通的單詞、片語、數或一系列字元的序列。abba，abcd

　　有不同的演算法可以檢查字元串是否為迴文。最簡單的方式是將字元串反向排列並檢查它和原字元串是否相同。如果兩者相同那麼它就是一個迴文。也可以使用棧來完成，但是利用數據結構來解決這個問題最簡單的方法是使用雙端隊列。

// 迴文檢查
function palindromeChecker(aString) {
  // 檢查字元串是否合法
  if (aString === undefined || aString === null || (aString !== null && aString.length === 0)) {
    return false;
  }
  const deque = new Deque();
  // 大小寫字母都轉化為小寫，同時移除所有空格。
  const lowerString = aString.toLocaleLowerCase().split(' ').join('');
  let isEqual = true;
  // 字元插入到雙端隊列中
  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }
  while (deque.size() > 1 && isEqual) {
    // 最前面一個是否等於最後面一個
    isEqual = deque.removeFront() === deque.removeBack();
  }
  return isEqual;
}

console.log(1111, palindromeChecker('123321'));

1.3.3 任務隊列

　　當我們在瀏覽器中打開新標籤時，就會創建一個任務隊列。因為每個標籤都是單執行緒處理所有的任務，稱為事件循環。瀏覽器要負責多個任務，渲染HTML、執行 JavaScript 程式碼、處理用戶交互（用戶輸入、滑鼠點擊等）、執行和處理非同步請求。

 

-----------磨刀不誤砍柴工、加油！！！

Tags:

VirMach 便宜 VPS