队列和双端队列

1. 队列数据结构

• 队列是遵循先进先出原则的一组有序项。
• 在尾部添加新元素，并在顶部移除元素。
• 最新添加的元素必须排在队列末尾。

1.1 创建队列

类声明：

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

这里使用对象存储元素，也可以使用其它结构。其中 count 用来控制队列的大小，lowestCount 用来指向第一个顶部元素。

队列的一些方法：

• enqueue(elements)：向队列尾部添加元素。
• dequeue()：移除并返回队列的第一个元素。
• peek()：返回队列顶部（第一个）元素。
• isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
• size()：返回队列包含的元素个数。

1.1.1 向队列添加元素

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

1.1.2 从队列移除元素

class Queue {
  dequeue() {
    if(this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }
}

1.1.3 查看队列头元素

class Queue {
  peek() {
    if(this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }
}

1.1.4 检查队列是否为空并获取长度

class Queue {
  isEmpty() {
    return this.count - this.lowestCount === 0
  }

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

1.1.5 清空队列

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

1.1.6 创建 toString() 方法

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

2. 双端队列

• 双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。
• 双端队列同时遵守先进先出和后进先出原则，可以说是队列和栈相结合的一种数据结构。

2.1 创建 Deque 类

Deque 类：

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

双端队列结构与普通队列相同，只不过操作有区别。

双端队列的方法：

• addFront(element)：在双端队列前端添加新元素。
• addBack(element)：在双端队列后端添加新元素，与普通队列 enqueue() 方法相同。
• removeFront()：从双端队列前端移除第一个元素，与普通队列 dequeue() 方法相同。
• removeBack()：从双端队列后端移除第一个元素，与栈的 pop() 方法一样。
• peekFront()：返回双端队列前端的第一个元素。
• peekBack()：返回双端队列后端的第一个元素。

2.1.1 向双端队列的前端添加元素

向双端队列前端添加元素存在三种情况（使用数组保存数据，对象可省略移动元素的步骤）：

1. 队列为空，直接调用 addBack() 方法添加即可。
2. 队列不为空，且 lowestCount 大于 0，表明前端有元素出队，可以直接添加到前端。
3. 队列不为空，且 lowestCount 等于 0，表明前端没有元素出队，需要将每个元素向后移，再添加到前端。

class Deque {
  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[this.lowestCount] = element;
    }
  }
}

2.1.2 向双端队列的后端添加元素

class Deque {
  addBack(element) {
    this.items[this.count++] = element;
  }
}

2.1.3 前端移除元素

class Deuqe {
  removeFront() {
    if(this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }
}

2.1.4 后端移除元素

class Deque {
  removeBack() {
    if(this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }
}

3. 使用队列和双端队列来解决实际问题

3.1 循环队列-击鼓传花

击鼓传花：给定一个序列，从第一位开始向后一位传花，最后一位传给第一位，每传 num 次，将该处元素从序列中移除，直至剩下最后一个元素，返回移除的元素序列和剩下的元素。

可以用队列模拟传花的过程：

function hotPotato(elementList, num) {
  const queue = new Queue();
  const res = [];

  // 入队
  for(let i = 0; i < elementList.length; i++) {
    queue.enqueue(elementList[i]);
  }

  // 模拟击鼓传花
  while(queue.size() > 1) {
    for(let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
    res.push(queue.dequeue());
  }

  return {
    eliminated: res,
    winner: queue.dequeue()
  }
}

3.2 回文检查

可以使用双端队列验证一个字符串是否是回文串：

class Deque {
  palindromeChecker(str) {
    if(!str) return false;
    const deque = new Deque();
    // 去掉空格
    const lowerString = str.toLocaleLowerCase().split(' ').join('');
    let res = true;

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

    while(deque.size() > 1 && res) {
      if(deque.removeFront() !== deque.removeBack()) {
        res = false;
      }
    }

    return res;
  }
}

3.3 JavaScript 任务队列

• 浏览器新开一个标签，就会创建一个任务队列。
• 每个标签都是单线程处理所有的任务，称为事件循环。