本文详细介绍JavaScript中队列数据结构的实现，涵盖基础队列、优先队列及循环队列。通过数组模拟入队出队操作，解析优先队列的优先级排序逻辑，并利用击鼓传花游戏演示循环队列的应用，帮助开发者掌握核心算法与代码实现。
队列基础概念与实现
队列是一种遵循先进先出（FIFO）原则的有序集合。它允许在尾部添加新元素，并从顶部移除元素。
理解队列的概念
队列在生活中的常见场景即为排队，其名称直观易懂，便于理解。
队列与栈类似，但区别在于队列遵循先入先出的规则。
队列的前端称为队头，后端称为队尾。元素从队头移除（出队），从队尾添加（入队）。
队列的创建方法
与栈的实现类似，此处不再赘述。我们需要实现以下核心功能，类比生活中排队上厕所的场景：
- 向队列中添加元素（加入排队队伍）
- 移除队头元素（队伍最前端的人出队进入）
- 查看队头元素（查看队伍最前端的人）
- 判断队列是否为空（检查队伍中是否有人）
- 移除所有元素（清空队列，如场景结束）
- 查看队列元素个数（统计排队人数）
基于数组实现完整的队列类，数组头部对应队列头部。
function Queue() {
var items = [];
this.enqueue = function (ele) {
items.push(ele);
};//入队
this.dequeue = function () {
return items.shift();
};//出队
this.front = function () {
return items[0];
};//查看队头元素
this.isEmpty = function () {
return items.length === 0;
};//判断队列是否为空
this.size = function () {
return items.length;
};//队列大小
this.clear = function () {
items = [];
};//清空队列
this.print = function () {
console.log(items.toString());
};//打印队列
}
var queue = new Queue(); //声明队列的实例
队列的使用示例
利用上述队列类简单模拟排队过程。
var queue = new Queue();
console.log("队列是否为空： " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("当前队列：");
queue.print();
console.log("出队的人： " + queue.dequeue());
console.log("当前队列：");
queue.print();
控制台打印结果如下：
优先队列的应用
优先队列
在排队场景中，若持有VIP会员卡的人插队至最前，随后SVIP会员又插至VIP之前，这体现了优先级的概念。
尽管比喻可能不严谨，但生活中确实存在优先级队列，高优先级元素可置于低优先级元素之前。
循环队列
若优先值小的元素置于队头，称为最小优先队列；反之，优先值大的元素置于队头，称为最大优先队列。两者仅判断逻辑不同，实现方式一致。优先队列与普通队列的区别在于入队时需判断优先级并对元素进行处理，即将元素封装为包含优先级的对象。由于所有对象具有相同属性，应使用工厂模式构建。通过修改队列类，可实现最小优先队列。
function PriorityQueue() {
var items = [];
function QueEle(ele, priority){ //封装我们的元素为一个对象
this.ele = ele; //元素
this.priority = priority; //优先级
}
this.enqueue = function (ele, priority) {
var queObj = new QueEle(ele, priority); //创建队列元素对象
if(this.isEmpty()){ //如果队列是空的，直接插入
this.push(queObj);
}else{
var bAdded = false;
for(var i = 0, len = items.length; i < len; i++){
if(priority < items[i].priority){
items.splice(i, 0, queObj); // 循环队列，如果优先级小于这个位置元素的优先级，插入
bAdded = true;
break;
}
}
if(!bAdded){
items.push(queObj); // 如果循环一圈都没有找到能插队的位置，直接插入队列尾部
}
}
};
this.dequeue = function () {
return items.shift();
};
this.front = function () {
return items[0];
};
this.isEmpty = function () {
return items.length === 0;
};
this.size = function () {
return items.length;
};
this.clear = function () {
items = [];
};
this.print = function () {
//这个地方稍微修改一下下
var temp = [];
for(var i = 0, len = items.length; i < len; i++){
temp.push(items[i].ele);
}
console.log(temp.toString());
};
}
代码中已有详细注释，以下模拟使用优先队列进行排队上WC的场景。
var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原队列:");
pQueue.print();
pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新队列:");
pQueue.print();
控制台打印结果：
循环队列与击鼓传花
循环队列
击鼓传花是循环队列的典型应用。高中晚自习停电时，大家手持物品传递，鼓停时持物者需唱歌。可将循环队列视为队列的一种应用形式，以下模拟实现击鼓传花游戏。
function hotPotato(pepoleList, frequency){ //参数：表示人的数组，传花的频率
var queue = new Queue();
for(var i = 0, len = pepoleList.length; i < len; i++){
queue.enqueue(pepoleList[i]); //初始化，进入队列
}
var eliminated;//被淘汰的同学
while(queue.size() > 1){ //只要队列至少还有两个人，就一直循环
for(var i = 0; i < frequency; i++){//出队入队，模拟循环效果
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();//清算
console.log(eliminated + '被淘汰');
}
return queue.dequeue();//返回队列中的最后一人
}
var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全场最佳:' + gameWinner);
控制台输出结果：
以上为JavaScript下的队列实现，并简要探讨了两种特殊队列：优先队列与循环队列。
本文内容希望对您的学习有所帮助，欢迎支持本站。