1. 什么是队列
队列是遵循先进先出（FIFO）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
下图模拟了队列的基本操作。
2. 模拟一个队列
javascript本身没有队列，所以我们用js来模拟一个队列的实现。
一个常用的队列包含如下方法
enqueue(element(s))：向队列尾部添加一个（或多个）新的项，相当于push。
dequeue()：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素，相当于shift。
peek()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动。 isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
size()：返回队列包含的元素个数，与数组的 length 属性类似
同栈一样，对于队列而言任何表的实现都是合法的。
2.1 数组实现
数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
如下图我们声明里一个长度为10的数组。Front 和Rear，分别代表队列的两端。
我们发现一个问题，当Rear为10时队列就满了，下一次再人队就会没有存放位置了。然而，队列前端的部分元素已经出队了。简单的解决方法是，只要 Front 或 Rear 到达数组的尾端，它就又绕回到开头。这叫做循环数组（circular array）实现。
实现回绕所需要的附加代码是极小的（虽然它可能使得运行时间加倍）。如果 Front 或 Rear 增1使得超越了数组，那么其值就要重置为数组的第一个位置。如下图所示：
另外，数组的大部分方法的时间复杂度为O(n)，因为我们每次修改数组的index，都相当于把下一个位置的元素拷贝到当前位置，一直到最后一个index为止。
综上考虑，搜索使用数组实现队列的性能较差，这里不再实现(另外数组实现太简单了，直接用数组原生的API即可，感兴趣的可以尝试自己实现下)。
2.2 用对象实现
以下是用对象模拟数组实现一个队列。
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]
}
// 如果队列中不包含任何元素，返回 true，否则返回 false
isEmpty() {
return this.count - this.lowestCount === 0
}
// 返回队列包含的元素个数，与数组的 length 属性类似
size() {
return this.count - this.lowestCount
}
clear() {
this.items = {}
this.count = 0
this.lowestCount = 0
}
}
2.3 链表实现
在上一篇栈的文章中讲了JavaScript对象是基于散列表+数组实现的，所以还是需要连续的内存空间，为了减少空间的占用，我们考虑使用链表实现(链表不需要连续的内存空间，链表部分详细讲解)。
interface INodeList {
value: number
next: INodeList | null
}
class MyQueue {
private head: INodeList | null = null
private tail: INodeList | null = null
private len: number = 0
add(x: number) {
const newNode: INodeList = {
value: x,
next: null,
}
if (this.head == null) {
this.head = newNode
}
const tailNode = this.tail;
if (tailNode) {
tailNode.next = newNode
}
this.tail = newNode
// 记录长度
this.len++
}
delete(): number | null {
const headNode = this.head
if (headNode == null) return null
if (this.len <= 0) return null
// 取值
const value = headNode.value
// 处理 head
this.head = headNode.next
// 记录长度
this.len--
return value
}
get length(): number {
return this.len;
}
}
由于队列是一个表，因此任何实现表的方法都能实现队列。下面是JAVA的队列源码实现。
JAVA queqe源码 fuseyism.com/classpath/d…
3. 双端队列
双端队列（deque，或称 double-ended queue）是一种允许我们同时从前端和后端添加和移除元素的特殊队列。
一般工程中都用双端队列，它相当于栈和队列的结合版，如下图所示：
双端队列在现实生活中也有例子。如在电影院、餐厅中排队，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，也可以直接离开队伍。
双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。
3.1 实现一个双端队列
我们在队列源码的基础上实现双端队列。
addFront() 在双端队列前端添加新的元素，相当于unshift
removeBack() 从双端队列后端移除第一个元素，相当于pop
peekBack() 返回双端队列后端的第一个元素
class Deque {
constructor() {
this.count = 0
this.lowestCount = 0
this.items = {}
}
// 该方法在双端队列前端添加新的元素
addFront(element) {
if (this.isEmpty()) {// 队列为空，调用addBack即可
this.addBack(element)
} else if (this.lowestCount > 0) { // 队列首位下标大于0，直接在队首插入
this.lowestCount--
this.items[this.lowestCount] = element
} else { // 队列首位下标小于0，我们将队列每位元素下标加1，再在队首插入元素
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1]
}
this.count++
this.items[0] = element
}
}
// 该方法在双端队列后端添加新的元素，同enqueue
addBack(element) {}
// 该方法会从双端队列前端移除第一个元素，同dequeue
removeFront() {}
// 该方法会从双端队列后端移除第一个元素
removeBack() {
if (this.isEmpty()) {
return undefined
}
this.count--
const result = this.items[this.count]
delete this.items[this.count]
return result
}
// 该方法返回双端队列前端的第一个元素，同peek
peekFront() {}
// 该方法返回双端队列后端的第一个元素
peekBack() {
if (this.isEmpty()) {
return undefined
}
return this.items[this.count - 1]
}
isEmpty() {}
size() {}
clear() {}
}
4. 优先队列
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。而在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。
特点：
- 1.插入操作: O(1)
- 2.取出操作: O(logN) - 按照元素的优先级取出
- 3.底层具体实现的数据结构较为多样和复杂: heap、 bst、 treap
优先队列比较复杂，这里不再详述，附上JAVA 优先队列实现，感兴趣的可以研究下源码。
JAVA 优先队列实现 docs.oracle.com/javase/10/d…
5. 常见队列问题
5.1 循环队列——击鼓传花游戏
在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈、结束游戏。重复这个过程，直到只剩一个孩子（胜者）
这是一个循环队列问题，每次循环，我们都需要将弹出队列的元素再加到队列的开头，以实现循环队列。代码如下：
function hotPotato(elementsList, num) {
const queue = []
const elimitatedList = []
// 将元素都加入队列中
for(let i = 0; i < elementsList.length; i++) {
queue.unshift(elementsList[i])
}
while (queue.length > 1) {
for (let i = 0; i < num; i++) {
queue.unshift(queue.pop())
}
elimitatedList.push(queue.pop())
}
return {
eliminated: elimitatedList,
winner: queue.pop()
}
}
const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']
const result = hotPotato(names, 7)
result.eliminated.forEach(name => {
console.log(`${name}在击鼓传花游戏中被淘汰。`)
});
console.log(`胜利者： ${result.winner}`)
过程如下图：
5.2 回文检查器
回文是正反都能读通的单词、词组、数或一系列字符的序列，例如 madam或 racecar，下面的算法使用了一个双端队列来解决问题。
将字符串以数组形式存入双端队列中，然后队首，队尾同时出队，如果值不同，则不是回文。
function palindromeChecker(aString) {
if (aString == null || (aString !== null && aString.length === 0)) {
return false;
}
const deque = [];
const lowerString = aString.toLocaleLowerCase().split(' ').join('');
let isEqual = true;
let firstChar, lastChar;
for (let i = 0; i < lowerString.length; i++) {
deque.push(lowerString.charAt(i));
}
while (deque.length > 1 && isEqual) {
firstChar = deque.shift(); // 从队首出队
lastChar = deque.pop(); // 队尾出队
if (firstChar !== lastChar) {
isEqual = false;
}
}
return isEqual;
}
6. leetcode常见考题
6.1 简单
1. 最近的请求次数
难度：简单
2. 用队列实现栈
难度：简单
6.2 中等
1. 设计循环队列
难度：中等
题解：设计循环队列(数组实现)
2. 设计循环双端队列
难度：中等
题解：实现双端队列(对象实现)
6.3 困难
1. 滑动窗口最大值
难度：困难
以上题解请参考：leetcode刷题之路
持续更新ing...
