JavaScript隊列和雙端隊列

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

在生活中也有隊列的應用，比如我們在售票處排隊等票，隊頭的人先拿到票，就走了，而新來的人，就必須排在隊偉文明排隊。

隊列

建立隊列

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;//追蹤隊列的第一個元素
    this.items = {};
  }      

向隊列添加元素

enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }      

細節就是要注意到隊列隻能在尾部添加元素

檢查隊列是否為空并擷取它的長度

size() {
    return this.count - this.lowestCount;
  };
isEmpty() {
    return this.size() === 0;
  };      

從隊列移除元素

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];
  }      

清空隊列

clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }      

建立toString方法

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;
  }      

好的，我們的隊列到此就建立完畢了。但是，有些小夥伴就有疑問了，還是排隊情景，假如我已經離開售票廳了，但是我還想再問些簡單問題，直接到前台詢問，這就是隊首添加元素了，還有隊尾的人突然有事離開了，這也是删除元素操作呀，那這個用隊列怎麼實作。

恩 ，我們的前輩就提出了雙端隊列，允許使用者在隊首進行添加和删除元素的操作，隊尾也是一樣。

雙端隊列

建立雙端隊列

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

添加操作

隊首添加元素

addFront(element) {
    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) {
    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];
  }      

隊列的實踐

模拟擊鼓傳花遊戲

情景：孩子們圍城一圈，把花傳遞給身邊的人，某一時刻停止，花在誰手上，誰就推出。重複這個操作，剩下的最後一個人就是勝利者。

代碼實作：

function hotPotato(elementsList, num) {
  const queue = new Queue();
  const elimitatedList = [];


  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[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()
  };
}      

回文檢查器

檢查一個詞組揮着字元串是否為回文。

代碼實作：​

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 firstChar;
  let lastChar;


  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }


  while (deque.size() > 1) {
    firstChar = deque.removeFront();
    lastChar = deque.removeBack();
    if (firstChar !== lastChar) {
      return false;
    }
  }


  return true;
};      

本文完〜