本部分介绍文章预计阅读需要四分钟，全文948个字。
队列（queue），也是常见的数据结构之一。在生活中，各个商场中等待的队伍，羽毛球筒中的羽毛球，计算机打印文档的序列，都是队列的生动实例，和栈（stack）不同的是，它的数据元素遵循FIFO，即先进先出，先来先服务的原则。
下面，我们尝试使用javascript实现一个队列。
class Queue {
constructor() {
this.items = {}; // 队列中的元素集合
this.count = 0; // 队列中元素的个数
this.lowestCount = 0; // 指定队列中最前排的元素位置
}
}
然后实现队列中常用的方法
- enqueue(elements) 向队列中添加一个或者多个元素
- dequeue() 删除队列的第一个元素
- peek() 返回队列的第一个元素
- isEmpty() 队列是否为空
- size() 队列的大小
- clear() 清空队列
- toString() 将队列中的元素转换成字符串输出
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.count- this.lowestCount === 0;
}
size() {
return this.count - this.lowestCount;
}
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
toString() {
if(this.isEmpty()) {
return '';
}
const result = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.size() - 1; i++) {
result += `,${this.items[i]}`;
}
return result;
}
队列和栈十分类似，不同在于dequeue和peek，是由于他们删除元素的特性不同，一个先进先出，一个后进先出；
目前，我们实现了从后边添加元素的队列，下面，我们来实现双端队列（deque），也就是，前端和后端都可以添加元素的队列；
双端队列在生活中比如电影院的排队，餐厅的排队也很常见，后边的人可以先走，前面的人也可以再返回问下这部电影是不是要3D眼镜之类；
在计算机中，双端队列应用于存储撤销操作，也就是Ctrl-Z，用户可以马上撤销最后进行的操作，而存储了一定的操作之后，前边进行的操作也会被移除出去；
可以说，deque是结合了栈以及队列的应用；
它的构造函数和队列相同，如下代码所示：
class Deque {
constructor() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
}
双端队列使用的方法有：
- addFront(element) 在队列前端添加元素
- addBack(element) 在队列后端添加元素，同Queue中的enqueue
- removeFront() 移除队列前端的元素，同Queue中的dequeue
- removeBack() 移除队列后端的元素，同Stack中的pop
- peekFront() 返回队列前端的第一个元素，同Queue中的peek
- peekBack() 返回队列后端的第一个元素，同Stack中的peek
对应的clear, size, isEmpty, toString等也不再赘述；
下边我们主要实现addFront这个方法
addFront(element) {
// 如果为空，可以直接使用addBack方法
if(this.isEmpty()) {
addBack(element);
} else if(this.lowestCount > 0){
// 如果最小坐标大于0，那么把最小坐标往前移动，直接赋值给前一个
this.lowestCount--;
this.items[this.lowestCount] = element;
} else {
// 如果最小坐标已经是0了，那么把所有元素后移，0放置添加的元素，count加一
for(let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.items[0] = element;
this.lowestCount = 0;
this.count++;
}
}
现在，我们创建了这两种队列的数据结构之后，可以用来解决一些实际的问题。
比如，循环队列，这个在现实中有一个游戏可以代表它，就是击鼓传花游戏，人们围坐成为一个圈，在音乐响起的时候，传递花朵，音乐停止，花朵到谁手中，谁就淘汰，最终留下的一个人胜出。
下面的示例，是模仿击鼓传花的代码：
// elementList 玩游戏的人的列表， num 在第几秒音乐停止
function hotPotato(elementList, num) {
const queue = new Qeque();
const eliminatedList = []; // 淘汰的人的列表
// 先把所有玩游戏的人放入队列
for (let i = 0; i < elementList.length; i++) {
queue.enqueue(elementList[i]);
}
// 游戏开始，当人数大于1就一直游戏
while(queue.size() > 1) {
// 每次到结束音乐的时间之后，把轮到队列前端的人移除
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
eliminatedList.push(queue.dequeue());
}
// 返回淘汰的列表，和最后的赢家
return { eliminated: eliminatedList, winner: queue.dequeue() };
}
算法问题中经常见到检测回文字符串，而双端队列可以说是最为方便的一种解决它的数据结构，实现检测回文字符串的代码如下：
function palindromeChecker(aString) {
// 首先判断传入的字符串是否合法
if(aString === null || aString === undefined ||
(aString !== null && aString.length === 0)) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(' ').join(''); // 先转换成小写，如果句子有空格，可以split去除再join
let isEqual = true;
let firstChar, lastChar;
// 把字符存入双端队列
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString.charAt(i));
}
// 从两端移除字符，判断他们是否相等
while(deque.size() > 1 && isEqual) {
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
isEqual = false;
}
}
return isEqual;
}
最后补充一个和队列相关的知识，当我们打开浏览器，就会创建一个任务队列，每个标签都是单线程的处理所有任务，这就叫做事件循环，包括渲染HTML，执行javascript代码，处理用户交互（鼠标点击，输入）、执行异步请求等。
到此为止，队列相关的内容总结完毕，觉得有用的友友可以点一个赞，一起学习~
