队列与的使用(queue)

1.队列的实现(queue),使用对象

// @ts-check

export default class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

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

2.双端队列的实现(dueue),使用对象

// @ts-check

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

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

3.使用队列(queue)实现击鼓传花游戏

import Queue from "./queue";

/*******************************************************************************************************
 * 击鼓传花游戏:
 * 循环传递花,某时刻停止,花在谁手里谁就淘汰,最终只剩一个人为赢家
 */

function hotPatato(elementList, num) {
  const queue = new Queue();
  const elimitatedList = [];
  let circleCount = 0;

  // 将数组的每个元素加入队列中
  for (let i = 0; i < elementList.length; i++) {
    queue.enqueue(elementList[i]);
  }
  console.log(queue);
  /*******************************************************************************************************
   * 队列为:
    Queue {
        count: 5,       
        lowestCount: 0, 
        items: {        
          '0': 'John',  
          '1': 'Jack',  
          '2': 'Camila',
          '3': 'Ingrid',
          '4': 'Carl'
        }
      }
  */
  while (queue.size() > 1) {
    // 循环次数
    circleCount++;

    // 击鼓传花,队列的头部去掉,加入队列的尾部
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }

    // 达到次数,剔除传到花的人
    const elimitatedPerson = queue.dequeue();
    elimitatedList.push(elimitatedPerson);

    console.log(
      `${circleCount}次循环传花,结果为:`,
      queue.toString(),
      `,淘汰:`,
      elimitatedPerson
    );
  }

  /*******************************************************************************************************
    * 
    第1次循环传花,结果为: Jack,Camila,Ingrid,Carl ,  淘汰: John
    第2次循环传花,结果为: Camila,Ingrid,Carl ,  淘汰: Jack
    第3次循环传花,结果为: Camila,Ingrid ,  淘汰: Carl
    第4次循环传花,结果为: Ingrid ,  淘汰: Camila
    */

  const result = {
    circleCount,
    elimitated: elimitatedList,
    winner: queue.dequeue(),
  };
  console.log(result);
  return result;
}

hotPatato(["John", "Jack", "Camila", "Ingrid", "Carl"], 20);

/*******************************************************************************************************
 * 结果为:
 *  {
 *    circleCount: 4,
 *    elimitated: [ 'John', 'Jack', 'Carl', 'Camila' ],
 *    winner: 'Ingrid'
 *  }
 */

4.使用双端队列(deque)实现是否是回文字符检查

/*******************************************************************************************************
 * 使用双端队列,检查是否是回文字符:例如,madam或者racecar
 */

import Deque from "./deque";

function palindromeChecker(astring) {
  if (typeof astring !== "string" || !astring || !astring.length) {
    return false;
  }

  /***** 去除首尾字符串,转化为小写,分割为单个字母的数组 ***********************/

  const strArr = astring
    .toLowerCase()
    .replace(/^\s+|\s+$/g, "")
    .split("");
  let isEqual = true;
  let firstChar, lastChar;
  const deque = new Deque();

  /***** 依次加入双端队列中 ***********************/
  strArr.forEach((str) => {
    deque.addBack(str);
  });

  while (deque.size() > 1 && isEqual) {
    /*******************************************************************************************************
     * 分别拿出双端队列头和尾,进行比较,如果相等,继续比较下去,不等则直接退出
     */
    // 拿出队列头
    firstChar = deque.removeFront();
    lastChar = deque.removeBack();
    if (firstChar !== lastChar) {
      isEqual = false;
    }
  }

  console.log(`"${astring}"`, `${isEqual ? "是" : "不是"}回文字符`);
  return isEqual;
}

palindromeChecker("abcd");
palindromeChecker("madam");
palindromeChecker(" r-aceca-r");
palindromeChecker("i love u evol i");
palindromeChecker("i love evol i");

/*******************************************************************************************************
  结果为:
  "abcd" 不是回文字符
  "madam" 是回文字符
  " r-aceca-r" 是回文字符
  "i love u evol i" 是回文字符
  "i love evol i" 是回文字符
  */
Contributors: masecho