Js队列和双端队列
队列遵循的是先进先出（FIFO）原则的一组有序的项，并从顶部移除元素，但是最新添加的元素必须排在队列的末尾。在生活中也有队列的应用，比如我们在售票处排队等票，队头的人先拿到票，就走了，而新来的人，就必须排在队伟文明排队。
队列
创建队列
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;//追踪队列的第一个元素
this.items = {};
}向队列添加元素
enqueue(element) {
this.items[this.count] = element;
this.count++;
}细节就是要注意到队列只能在尾部添加元素
检查队列是否为空并获取它的长度
size() {
return this.count - this.lowestCount;
};
isEmpty() {
return this.size() === 0;
};从队列移除元素
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];
}清空队列
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;
}好的，我们的队列到此就创建完毕了。但是，有些小伙伴就有疑问了，还是排队情景，假如我已经离开售票厅了，但是我还想再问些简单问题，直接到前台询问，这就是队首添加元素了，还有队尾的人突然有事离开了，这也是删除元素操作呀，那这个用队列怎么实现。恩 ，我们的前辈就提出了双端队列，允许用户在队首进行添加和删除元素的操作，队尾也是一样。
双端队列
创建双端队列
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}添加操作
队首添加元素
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[0] = element;
}
}队尾添加元素
addBack(element) {
this.items[this.count] = element;
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];
}队列的实践
模拟击鼓传花游戏
情景：孩子们围城一圈，把花传递给身边的人，某一时刻停止，花在谁手上，谁就推出。重复这个操作，剩下的最后一个人就是胜利者。
代码实现：
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()
};
}回文检查器
检查一个词组挥着字符串是否为回文。
代码实现：
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 firstChar;
let lastChar;
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString.charAt(i));
}
while (deque.size() > 1) {
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
return false;
}
}
return true;
};本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！
