JavaScript如何实现队列结构

# JavaScript如何实现队列结构

## 引言

队列（Queue）是计算机科学中最基础的数据结构之一，它遵循**先进先出（FIFO）**原则。在JavaScript中，虽然数组可以模拟队列操作，但理解如何从零实现队列对掌握数据结构本质至关重要。本文将深入探讨队列的实现方式、应用场景以及性能优化策略。

## 一、队列的基本概念

### 1.1 什么是队列
队列是一种线性数据结构，其操作限制在两端进行：
- **入队（Enqueue）**：在队尾添加元素
- **出队（Dequeue）**：从队首移除元素

### 1.2 队列的特性
- 有序性：元素保持插入顺序
- 操作受限：只能从特定端点访问
- 时间复杂度：
  - 理想情况下入队/出队操作应为O(1)
  - 搜索/随机访问为O(n)

### 1.3 队列的常见类型
| 类型 | 特点 | 应用场景 |
|------|------|----------|
| 普通队列 | 严格FIFO | 任务调度 |
| 双端队列 | 两端可操作 | 撤销操作历史 |
| 优先队列 | 按优先级出队 | 急诊分诊系统 |
| 循环队列 | 空间复用 | 缓冲区实现 |

## 二、基于数组的队列实现

### 2.1 基础实现方案
```javascript
class ArrayQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return "Underflow";
    return this.items.shift();
  }

  peek() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

2.2 性能问题分析

• shift()方法的缺陷：
  • 每次出队需要移动所有剩余元素
  • 时间复杂度实际为O(n)
• 内存浪费：
  • 出队后数组前端空间无法复用

2.3 优化方案：指针追踪法

class OptimizedArrayQueue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }

  enqueue(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }

  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }
  // 其他方法保持不变...
}

三、基于链表的队列实现

3.1 节点定义

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

3.2 完整链表队列实现

class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  dequeue() {
    if (!this.head) return null;
    const removedNode = this.head;
    if (this.head === this.tail) {
      this.tail = null;
    }
    this.head = this.head.next;
    this.length--;
    return removedNode.value;
  }
  
  peek() {
    return this.head?.value;
  }
  
  isEmpty() {
    return this.length === 0;
  }
}

3.3 性能对比

四、循环队列实现

4.1 解决什么问题

• 固定大小的队列
• 避免数据迁移造成的性能损耗
• 高效利用存储空间

4.2 具体实现

class CircularQueue {
  constructor(k) {
    this.size = k;
    this.queue = new Array(k);
    this.head = -1;
    this.tail = -1;
  }

  enQueue(value) {
    if (this.isFull()) return false;
    if (this.isEmpty()) this.head = 0;
    this.tail = (this.tail + 1) % this.size;
    this.queue[this.tail] = value;
    return true;
  }

  deQueue() {
    if (this.isEmpty()) return false;
    if (this.head === this.tail) {
      this.head = -1;
      this.tail = -1;
    } else {
      this.head = (this.head + 1) % this.size;
    }
    return true;
  }

  Front() {
    return this.isEmpty() ? -1 : this.queue[this.head];
  }

  Rear() {
    return this.isEmpty() ? -1 : this.queue[this.tail];
  }

  isEmpty() {
    return this.head === -1;
  }

  isFull() {
    return (this.tail + 1) % this.size === this.head;
  }
}

五、队列的实际应用

5.1 浏览器事件循环

graph LR
    A[宏任务队列] --> B[DOM事件]
    A --> C[网络请求]
    A --> D[setTimeout]
    E[微任务队列] --> F[Promise.then]
    E --> G[MutationObserver]

5.2 广度优先搜索(BFS)

function BFS(root) {
  const queue = [root];
  const result = [];
  
  while (queue.length) {
    const node = queue.shift();
    result.push(node.value);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

5.3 消息队列系统

class MessageQueue {
  constructor() {
    this.subscribers = new Map();
  }

  subscribe(topic, callback) {
    if (!this.subscribers.has(topic)) {
      this.subscribers.set(topic, []);
    }
    this.subscribers.get(topic).push(callback);
  }

  publish(topic, message) {
    const callbacks = this.subscribers.get(topic) || [];
    callbacks.forEach(cb => {
      setTimeout(() => cb(message), 0);
    });
  }
}

六、性能优化进阶

6.1 批量处理模式

class BatchQueue {
  constructor(processor, batchSize = 10) {
    this.queue = [];
    this.processing = false;
    this.processor = processor;
    this.batchSize = batchSize;
  }

  add(item) {
    this.queue.push(item);
    if (!this.processing) {
      this.process();
    }
  }

  async process() {
    this.processing = true;
    while (this.queue.length) {
      const batch = this.queue.splice(0, this.batchSize);
      await this.processor(batch);
    }
    this.processing = false;
  }
}

6.2 优先级队列实现

class PriorityQueue {
  constructor(comparator = (a, b) => a > b) {
    this.heap = [];
    this.comparator = comparator;
  }

  enqueue(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  dequeue() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return max;
  }

  // 省略堆的上浮和下沉操作...
}

七、现代JavaScript中的队列

7.1 使用Generators实现

function* queueGenerator() {
  const queue = [];
  while (true) {
    const action = yield;
    if (action.type === 'ENQUEUE') {
      queue.push(action.value);
    } else if (action.type === 'DEQUEUE') {
      yield queue.shift();
    }
  }
}

const q = queueGenerator();
q.next();
q.next({ type: 'ENQUEUE', value: 1 });
q.next({ type: 'ENQUEUE', value: 2 });
console.log(q.next({ type: 'DEQUEUE' }).value); // 1

7.2 Web Worker任务队列

// main.js
const workerQueue = new Array();
let workerBusy = false;

function processWithWorker(data) {
  return new Promise((resolve) => {
    workerQueue.push({ data, resolve });
    if (!workerBusy) processQueue();
  });
}

function processQueue() {
  if (!workerQueue.length) return;
  workerBusy = true;
  const { data, resolve } = workerQueue.shift();
  const worker = new Worker('worker.js');
  worker.postMessage(data);
  worker.onmessage = (e) => {
    resolve(e.data);
    workerBusy = false;
    processQueue();
  };
}

结语

队列作为基础数据结构，其实现方式随着应用场景不断演进。从简单的数组实现到复杂的优先级队列，理解其核心原理能帮助开发者： 1. 合理选择数据结构 2. 优化关键路径性能 3. 设计更健壮的系统架构

在JavaScript生态中，队列概念广泛应用于事件处理、状态管理、异步流程控制等领域，是每个开发者必须掌握的基础知识。 “`