1. 队列特征
   1. 先进先出
   2. 头部类似栈底
   3. 尾部类似栈顶
   4. 需要使用双指针来分别指向队列的头部和尾部
2. 双端队列：结合了栈和队列的特点
   1. 双端都可以进行添加和删除操作
   2. 同时具备先进先出和后进先出的特点

队列

1. 先进先出，在末尾添加元素，在头部移除元素
2. 利用js对象实现队列结构的好处
   1. 保证了队列结构的特点
   2. 可以通过键名的形式获取队列元素，降低了查询队列元素的时间复杂度

/**
 * 1.enqueue 向队列末尾添加元素
 * 2.dequeue 删除队列头元素并返回
 * 3.peek 获取队列头元素并返回
 * 4.isEmpty 判断队列是否为空
 * 5.size 判断队列元素数量
 * 6.clear 清空队列
 * 7.toString 输出字符串
 */
class Queue {
  constructor() {
    // 控制队列尾部添加删除操作
    this.count = 0;
    // 控制队列头部添加删除操作
    this.lowestCount = 0;
    this.items = {};
  }
  enqueue(element) {
    //   在末尾添加element
    this.items[this.count] = element;
    //   将末尾索引值扩大 1 -->  2 ：想不清楚就举举例子，一个例子就可以证明count需要增大
    this.count++;
  }
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    //   获取头部元素
    const res = this.items[this.lowestCount];
    //   删除头部元素
    delete this.items[this.lowestCount];
    //   头部索引需要后移一位 0 --> 1
    this.lowestCount++;
    //   返回删除的元素
    return res;
  }
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    //   返回头部元素
    return this.items[this.lowestCount];
  }
  isEmpty() {
    // 判断count 和 lowestCount是否相等
    return this.count === this.lowestCount;
  }
  size() {
    // count 和 lowestCount的差即为元素数量
    return this.count - this.lowestCount;
  }
  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  toString() {
    let str = '';
    for (let i = this.lowestCount; i < this.count; i++) {
      str += `${this.items[this.lowestCount]}`;
    }
    return str;
  }
}
const q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
console.log(q);
q.dequeue();
q.dequeue();
console.log('empty', q.isEmpty());
console.log('size', q.size());
console.log('string', q.toString());
q.clear();
console.log('clear--', q);

双端队列

1. 双端都可以进行添加和删除操作
2. 同时具备先进先出和后进先出的特点

/**
 * 具备队列的方法
 * 额外的function
 * 1.addFront 在队列头部添加元素
 * 2.addBack 在队列尾部添加元素 - 同enqueue
 * 3.removeFront 在队列头部删除元素并返回 - 同queue中dequeue
 * 4.removeBack 在队列尾部删除元素并返回 - 同stack中pop
 * 5.peekFront 返回队列头部元素 - 同peek
 * 6.peekBack 返回队列尾部元素
 */
class Deque {
  constructor() {
    // 控制尾部元素添加和删除
    this.count = 0;
    // 控制头部元素添加和删除
    this.lowestCount = 0;
    this.items = {};
  }
  // 需要保证lowestCount大于等于0
  addFront(element) {
    if (this.isEmpty()) {
      this.addBack(element);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      // lowestCount = 0
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = element;
    }
  }
  // 保证后端count为大于等于0
  addBack(element) {
    this.items[this.count] = element;
    // 控制尾部的变量需要加1
    this.count++;
  }
  removeFront() {
    const res = this.items[this.lowestCount];
    console.log(res);
    delete this.items[this.lowestCount];
    // 控制头部元素的变量需要加1
    this.lowestCount++;
    return res;
  }
  removeBack() {
    //   因为addFront的时候给count加了1，所以这里需要减1
    this.count--;
    const res = this.items[this.count];
    delete this.items[this.count];
    // 控制尾部元素的变量需要减1
    return res;
  }
  peekFront() {
    return this.items[this.lowestCount];
  }
  peekBack() {
    return this.items[this.count];
  }
  isEmpty() {
    return this.count === this.lowestCount;
  }
  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  size() {
    return this.count - this.lowestCount;
  }
}
const d = new Deque();
d.addFront(1);
d.addFront(2);
d.addFront(3);
d.addBack(4);
d.addBack(5);
d.addBack(6);
console.log(d);
d.removeFront();
console.log(d);
d.removeBack();
console.log(d);
console.log('empty', d.isEmpty());
console.log('size', d.size());

循环队列解决击鼓传花问题

1. 将未收到花的元素移除的同时重新添加到队列末尾
2. 将收到花的元素移除
   1. 通过条件判断队列长度是否为1来不断遍历
   2. 最终队列中只剩下一个元素即为胜利者

// 模拟实现击鼓传花
/**
 * 1.将传入的数据保存到队列当中
 * 2.通过遍历传入的击鼓次数，遍历队列
 *  - 在遍历的过程中，未达到最后一次击鼓：将开头的元素移除并保存到末尾
 *  - 在最后一次击鼓，将头元素移除
 * 3.最终队列中只剩下一个元素，返回该元素
 */
function hotPotato(arr, num) {
  const q = new Queue();
  // 保存被移除的元素
  const newArr = [];
  // 1.将arr中的元素保存到队列中
  for (let i = 0; i < arr.length; i++) {
    q.enqueue(arr[i]);
  }
  // 2.游戏开始
  while (q.size() > 1) {
    for (let i = 0; i < num; i++) {
      //   把成功躲避花的元素重新添加到队列中;
      q.enqueue(q.dequeue());
    }
    //   第num次，未成功躲避花的元素被移除
    newArr.push(q.dequeue());
  }
  return {
    newArr,
    result: q.dequeue(),
  };
}
let nameList = ['波仔', '点点', '右右', '洋洋'];
console.log(hotPotato(nameList, 5));

利用双端队列判断回文

1. 将字符串按照字符插入队列中
2. 依照双端队列两端都可以进行删除操作的特点同时比较双端删除的字符是否相等
   1. first === last
   2. first !== last

// 利用双端队列解决回文问题
/**
 * 思路：通过双端队列两端都可以进行删除操作的特点，遍历比较双端删除返回的元素是否相等
 *  - 如果全部相等，则是回文
 *  - 有一处不相等：不是回文
 * 1.先判断string是否合法，不合法直接返回false
 * 2.将string按字符添加到双端队列中
 * 3.遍历判断是否相等
 */
function palindrome(string) {
  if (string === undefined || string === null || string.trim() === '') {
    return false;
  }
  const d = new Deque();
  let firstChar;
  let lastChar;
  let isPalindrome = true;
  let arr = string.toLowerCase().split('');
  for (let i = 0; i < arr.length; i++) {
    d.addBack(arr[i]);
  }
  while (d.size() > 1 && isPalindrome) {
    firstChar = d.removeFront();
    lastChar = d.removeBack();
    if (firstChar !== lastChar) {
      isPalindrome = false;
    }
  }
  return isPalindrome;
}
let str = 'step on no pets';
console.log(palindrome(str));