JavaScript 实现队列、优先队列与循环队列详解

结果或目标

理解并掌握 JavaScript 中三种常见队列的实现方式：基础 FIFO 队列、基于权重的优先队列，以及用于逻辑循环处理的循环队列。你将学会如何封装类、处理元素入队与出队的逻辑，并通过具体案例观察其运行效果。

准备条件

1. 开发环境：任何支持 JavaScript 的环境（如 Node.js、浏览器控制台或 VS Code）。
2. 基础知识：了解 JavaScript 的基本语法、函数定义、数组操作（如 push, shift）以及对象概念。

真实操作顺序

第1步：构建基础队列

目的：实现一个标准的 FIFO 结构，确保元素按进入的顺序被取出。

核心逻辑：

• 入队 (enqueue)：将新元素添加到数组末尾。
• 出队 (dequeue)：移除并返回数组开头的第一个元素。
• 辅助方法：包含查看队头(front)、判断是否为空(isEmpty)、获取大小(size)和清空(clear)等功能。

代码实现：利用内部变量 items 存储数据，保护封装性。

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();
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();

运行上述代码，控制台将依次显示队列状态的变化。最初队列为空，加入三个元素后按序打印，出队一个元素后再次打印验证顺序。这直观展示了 的基础排队概念，即最早进入的元素最先被服务。

第2步：构建优先队列

目的：根据元素的优先级权重重新排序，高优先级（通常数值小）的元素排在前面。

核心逻辑：

• 数据结构改造：不再仅存储值，而是存储包含 element 和 priority 的对象。
• 自定义入队：插入时遍历现有队列，找到第一个优先级低于新元素的索引位置进行插入（splice），若未找到则追加至末尾。

代码实现：

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()) {
      // 如果队列为空，直接插入
      items.push(queObj);
    } else {
      var bAdded = false;
      for (var i = 0; i < items.length; 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; i < items.length; i++) {
      temp.push(items[i].ele);
    }
    console.log(temp.toString());
  };
}

// 测试优先队列
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); // 优先级 2
pQueue.enqueue('SVIP', 1); // 优先级 1 (最高)
console.log("新队列:");
pQueue.print();

在这个示例中，SVIP (优先级1) 和 VIP (优先级2) 成功插队到了普通成员 (优先级3) 之前，验证了 的执行结果。

第3步：模拟循环队列（击鼓传花）

目的：演示如何将基础队列用于解决约瑟夫环类型的逻辑问题，即循环执行操作。

核心逻辑：

• 循环机制：不真正修改底层存储结构，而是通过反复调用 enqueue 和 dequeue 来模拟指针的移动。
• 淘汰规则：每经过指定次数（frequency）的传递，当前队首元素被移出（淘汰），直到只剩一名队员。

代码实现：

// pepoleList: 参与者的数组, frequency: 每轮传递的次数
function hotPotato(pepoleList, frequency) {
  var queue = new Queue();
  // 1. 初始化：所有人入队
  for (var i = 0; i < pepoleList.length; i++) {
    queue.enqueue(pepoleList[i]);
  }
  
  var eliminated;
  // 2. 循环淘汰：当人数大于1时继续
  while (queue.size() > 1) {
    // 模拟传花：将队首移到队尾
    for (var i = 0; i < frequency; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 击鼓停止：队首出队（被淘汰）
    eliminated = queue.dequeue();
    console.log(eliminated + '被淘汰');
  }
  
  // 3. 返回获胜者
  return queue.dequeue();
}

var people = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(people, 12);
console.log('全场最佳:' + gameWinner);

该算法通过不断的“首尾相接”操作实现了逻辑上的循环队列，最终筛选出唯一幸存者。这一过程的输出结果如 所示，清晰展示了每一轮的淘汰顺序。

完成判断

当你成功运行了上述三段代码，并在控制台中观察到： 1. 基础队列严格按输入顺序输出。 2. 优先队列中低数字（高优先级）元素始终位于前端。 3. 击鼓传花算法能准确剔除指定位置的元素并返回最后一人。 即视为掌握目标达成。

简要总结

以上就是 JavaScript 下的队列实现。我们不仅理解了基础的先进先出原理，还通过优先队列学会了如何根据权重调整执行顺序，并利用基础队列的特性巧妙解决了循环逻辑中的淘汰问题。这些数据结构是许多复杂算法（如 BFS 广度优先搜索、任务调度系统）的基石。更多关于 JavaScript 数据结构优化的资料请关注本站其它相关文章！