队列和双端队列
队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
队列数据结构
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0; // 用于追踪第一元素
this.items = {};
}
// 向队尾添加一个新的项
enqueue(item) {
this.items[this.count] = item;
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 '';
}
let objString = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString}, ${this.items[i]}`;
}
return objString;
}
}
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）是一种允许同时从前端和后端添加和移除元素的特殊队列。在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
// 在队列前添加新元素
addFront(item) {
if (this.isEmpty()) {
this.addBack(item);
} else if (this.lowestCount > 0) {
this.lowestCount--;
this.items[this.lowestCount] = item;
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.lowestCount = 0;
this.items[0] = item;
}
}
// 在队尾添加新元素
addBack(item) {
this.items[this.count] = item;
this.count++;
}
// 从前面移除元素
removeFront() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
// 从后面移除元素
removeBack() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
// 获取队列前端元素
peekFront() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
// 获取队尾元素
peekBack() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
// 查看是否为空
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 '';
}
let objString = `${this.items[this.lowestCount]}`;
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString}, ${this.items[i]}`;
}
return objString;
}
}
const deque = new Deque();
console.log(deque.isEmpty()); // 输出 true
deque.addBack('John');
deque.addBack('Jack');
console.log(deque.toString()); // John, Jack
deque.addBack('Camila');
console.log(deque.toString()); // John, Jack, Camila
console.log(deque.size()); // 输出 3
console.log(deque.isEmpty()); // 输出 false
deque.removeFront(); // 移除 John
console.log(deque.toString()); // Jack, Camila
deque.removeBack(); // Camila 决定离开
console.log(deque.toString()); // Jack
deque.addFront('John'); // John 回来询问一些信息
console.log(deque.toString()); // John, Jack
队列应用
function hotPotato(elementsList, num) {
const queue = new Queue();
const elimitatedList = [];
for (let i = 0; i < elementsList.length; i++) {
queue.enqueue(elementsList[i]);
}
while(queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
elimitatedList.push(queue.dequeue());
}
return {
eliminated: elimitatedList,
winner: queue.dequeue(),
};
}
const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotPotato(names, 7);
result.eliminated.forEach(name => {
console.log(`${name}在击鼓传花游戏中被淘汰。 `);
});
console.log(`胜利者： ${result.winner}`);
回文是正反都能读通的单词、词组、数或一系列字符的序列，例如 madam 或 racecar。
function palindromeChecker(aString) {
if (aString === undefined || aString === null ||
(aString !== null && aString.length === 0)) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().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 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。
