当前位置 博文首页 > 司夏的博客：JavaScript 数据结构与算法（队列）
队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。在现实中，最常见的队列的例子就是排队。
创建队列
创建自己的类来表示一个队列。首先需要一个用于存储队列中元素的数据结构。可以使用数组，但是，为了写出一个在获取元素时更高效的数据结构，将使用一个对象来存储元素。
// 声明类
class Queue {
constructor() {
this.count = 0; // count 属性来帮助我们控制队列的大小
this.lowestCount = 0; // 追踪第一个元素
this.items = {};
}
}
向队列添加元素
enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
enqueue(element) {
this.items[this.count] = element; // 要把 count 变量作为 items对象中的键，对应的元素作为它的值
this.count++;
}
从队列移除元素
dequeue()：移除队列的第一项（即排在队列最前面的项）并返回被移除的元素。
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount]; // {1}
delete this.items[this.lowestCount]; // {2}
this.lowestCount++; // {3}
return result; // {4}
}
查看队列头元素
peek()：返回队列中第一个元素。队列不做任何变动(不移除元素，只返回元素信息)
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
检查队列是否为空并获取它的长度
isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
isEmpty() {
return this.count - this.lowestCount === 0;
// 只需要计算 count 和 lowestCount 之间的差值即可
}
size()：返回队列包含的元素个数，与数组的 length 属性类似。
size() {
return this.count - this.lowestCount;
}
清空队列
clear()：要清空队列中的所有元素
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
创建 toString 方法
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;
}
完整的 Queue 类
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]
};
isEmpty() {
return this.size() === 0;
};
size() {
return this.count - this.lowestCount;
};
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;
}
}
首先实例化创建的 Queue 类
const queue = new Queue();
console.log(queue.isEmpty()); // 输出 true
添加一些元素（可以向队列添加任何类型的元素）
queue.enqueue('John');
queue.enqueue('Jack');
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John, Jack, Camila
console.log(queue.size()); // 输出 3
console.log(queue.isEmpty()); // 输出 false
queue.dequeue(); // 移除 John
queue.dequeue(); // 移除 Jack
console.log(queue.toString()); // Camila
双端队列（deque，或称 double-ended queue）是一种允许我们同时从前端和后端添加和移除元素的特殊队列。双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。，双端队列的一个常见应用是存储一系列的撤销操作。
创建 Deque 类
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
};
//方法
}
双端队列是一种特殊的队列，所以构造函数中的部分代码和队列相同，包括相同的内部属性和以下方法：isEmpty、clear、size 和 toString。由于双端队列允许在两端添加和移除元素，还会有下面几个方法。
向双端队列的前端添加元素
addFront(element)：该方法在双端队列前端添加新的元素。
要将一个元素添加到双端队列的前端，存在三种场景。
addFront(element) {
// 第一种场景是这个双端队列是空的（行{1}）执行 addBack 方法，元素会被添加到双端队列的后端.
if (this.isEmpty()) { // {1}
this.addBack(element);
} else if (this.lowestCount > 0) { // {2}
//第二种场景是一个元素已经被从双端队列的前端移除（行{2}），也就是说 lowestCount 属性会大于等于 1。
//这种情况下，我们只需要将 lowestCount 属性减 1 并将新元素的值放在这个键的位置上即可。
this.lowestCount--;
this.items[this.
