第二章、队列和双端队列

队列

队列遵循先进先出原则。

class Queue {
  constructor() {
    // 已添加过的总数量，包括已移除的
    this.count = 0;
    // 当前队列最前端的项
    this.lowestCount = 0;
    this.items = {};
  }

  // 添加元素
  enqueue(item) {
    this.items[this.count] = item;
    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];
  }

  // 队列大小
  size() {
    // 队列总大小减去当前第一项的索引即为队列的当前大小
    return this.count - this.lowestCount;
  }

  // 检查是否为空
  isEmpty() {
    return this.size() === 0;
  }

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

  // 返回队列内容
  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(item) {
    if (this.isEmpty()) {
      // 当前队列为空情况
      this.addBack(item);
    } else if (this.lowestCount > 0) {
      // 当前队列有被移除过元素的情况，即第一个元素下标不是0
      this.lowestCount--;
      this.items[this.lowestCount] = item;
    } else {
      // 当前队列第一个下标为0的情况
      // 队列整体后移
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = item;
    }
  }

  // 后端添加元素
  addBack(item) {
    this.items[this.count] = item;
    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];
  }

  // 队列大小
  size() {
    // 队列总大小减去当前第一项的索引即为队列的当前大小
    return this.count - this.lowestCount;
  }

  // 检查是否为空
  isEmpty() {
    return this.size() === 0;
  }

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

  // 返回队列内容
  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;
  }
}

使用队列和双端队列解决问题

循环队列--击鼓传花游戏

这是一个队列的修改版本，循环队列，实现是将读取完的元素放到队列的末尾，形成队列的循环读取。

function loopQueue(itemList, num) {
  const queue = new Queue();
  const outItemList = []
  // 将给定的参数全部储存进队列
  for(let i =0;i<itemList.length;i++){
    queue.enqueue(itemList[i])
  }
  // 当队列中元素多余两个的时候进行循环，即进行传花游戏
  while(queue.size() > 1){
    for(let i=0;i<num; i++){
      // 循环指定的次数，每次都将队列最前端的项放到队列末尾
      queue.enqueue(queue.dequeue())
    }
    // 指定传递次数结束之后，将队列第一个元素抛出，即淘汰手上有花的人
    outItemList.push(queue.dequeue())
  }
  return {
    // 每次经过给定次数循环后被淘汰的元素组成的数组
    outItem: outItemList,
    // 队列中最后会只剩一个元素，即传花游戏的冠军
    winner: queue.dequeue()
  }
}

const names = ["a","b","c","d","e","f","g","h","i"]
const result = loopQueue(names, 8)
console.log(result)
//  {
//    outItem: (8) ["i", "a", "c", "f", "d", "e", "b", "g"]
//    winner: "h"
//  }

回文检查器

使用双端队列检查某一个字符串是否为回文

function palindromeCheck(str) {
  // 只检测字符串
  if (Object.prototype.toString.call(str) !== "[object String]") {
    return false;
  }
  const deque = new Deque();
  // 将字符串转为数组，并且不区分大小写，统一转为小写
  const strList = str.toLocaleLowerCase().split("");
  let isEqual = true;
  let firstChar, lastChar;
  for (let i = 0; i < strList.length; i++) {
    deque.addBack(strList[i]);
  }
  while (deque.size() > 1 && isEqual) {
    firstChar = deque.removeFront();
    lastChar = deque.removeBack(); 
    // 如果某个字符串是回文，那么转为双端队列之后，当前队列取出来的第一项跟最后一项应该相同
    if (firstChar !== lastChar) {
      isEqual = false;
    }
  }
  return isEqual
}
console.log(palindromeCheck("asD dsa")) // true


// 案例只是展示双端队列思想，JS中可以直接判断字符串是不是回文
function palindromeCheck(str) {
  return str.toLocaleLowerCase() === str.toLocaleLowerCase().split("").reverse().join("")
}
console.log(palindromeCheck("asD dsa")) // true