JavaScript如何实现一个队列

# JavaScript如何实现一个队列

## 队列基础概念

队列（Queue）是一种遵循**先进先出（FIFO）**原则的线性数据结构。与栈不同，队列允许在一端（队尾）添加元素，在另一端（队首）移除元素。这种特性使队列成为处理顺序任务的理想选择。

### 队列的核心操作
1. **enqueue(element)** - 向队尾添加元素
2. **dequeue()** - 移除队首元素
3. **peek()** - 查看队首元素（不移除）
4. **isEmpty()** - 检查队列是否为空
5. **size()** - 获取队列长度

## 数组实现队列

JavaScript数组天然支持队列操作，但存在性能问题：

```javascript
class ArrayQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element); // O(1)
  }

  dequeue() {
    return this.items.shift(); // O(n) - 性能瓶颈！
  }

  peek() {
    return this.items[0];
  }

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

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

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

性能问题分析

• shift()操作需要移动所有剩余元素，时间复杂度为O(n)
• 当处理大量数据时（如10,000+元素），性能显著下降

对象实现高性能队列

通过维护头尾指针的优化实现：

class ObjectQueue {
  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;
  }

  peek() {
    return this.items[this.frontIndex];
  }

  isEmpty() {
    return this.rearIndex - this.frontIndex === 0;
  }

  size() {
    return this.rearIndex - this.frontIndex;
  }

  clear() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }
}

性能优势

• 所有操作的时间复杂度均为O(1)
• 适合高频操作的生产环境

链表实现队列

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

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 value = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    return value;
  }

  // ...其他方法实现类似
}

循环队列实现

解决普通队列的”假溢出”问题：

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;
      return true;
    }
    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;
  }
}

优先队列实现

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    
    if (!added) {
      this.items.push(queueElement);
    }
  }

  // 其他方法与普通队列相同
}

实际应用场景

1. 异步任务处理

const taskQueue = new ObjectQueue();

function addTask(task) {
  taskQueue.enqueue(task);
}

function processTasks() {
  while (!taskQueue.isEmpty()) {
    const task = taskQueue.dequeue();
    try {
      task.execute();
    } catch (error) {
      console.error('Task failed:', error);
    }
  }
}

2. 广度优先搜索(BFS)

function bfs(graph, startNode) {
  const visited = new Set();
  const queue = new LinkedListQueue();
  queue.enqueue(startNode);

  while (!queue.isEmpty()) {
    const currentNode = queue.dequeue();
    if (!visited.has(currentNode)) {
      console.log('Visiting:', currentNode);
      visited.add(currentNode);
      for (const neighbor of graph[currentNode]) {
        queue.enqueue(neighbor);
      }
    }
  }
}

3. 消息队列系统

class MessageQueue {
  constructor() {
    this.queue = new ObjectQueue();
    this.subscribers = new Set();
  }

  publish(message) {
    this.queue.enqueue(message);
    this.notifySubscribers();
  }

  subscribe(callback) {
    this.subscribers.add(callback);
  }

  notifySubscribers() {
    while (!this.queue.isEmpty()) {
      const message = this.queue.dequeue();
      this.subscribers.forEach(sub => sub(message));
    }
  }
}

性能对比测试

// 测试10,000次操作
function testPerformance(QueueClass) {
  const queue = new QueueClass();
  const start = performance.now();
  
  for (let i = 0; i < 10000; i++) {
    queue.enqueue(i);
  }
  
  for (let i = 0; i < 10000; i++) {
    queue.dequeue();
  }
  
  return performance.now() - start;
}

console.log('ArrayQueue:', testPerformance(ArrayQueue), 'ms');
console.log('ObjectQueue:', testPerformance(ObjectQueue), 'ms');
console.log('LinkedListQueue:', testPerformance(LinkedListQueue), 'ms');

最佳实践建议

1. 小规模数据：使用数组实现简单快捷
2. 高频操作：选择对象或链表实现
3. 固定大小队列：考虑循环队列实现
4. 优先级处理：优先队列是最佳选择
5. TypeScript：建议使用泛型增强类型安全

class GenericQueue<T> {
  private items: T[] = [];
  
  enqueue(item: T): void {
    this.items.push(item);
  }
  
  dequeue(): T | undefined {
    return this.items.shift();
  }
}

总结

JavaScript实现队列有多种方式，各有优缺点。理解不同实现方式的特性，才能在实际开发中选择最适合的方案。对于大多数生产环境，推荐使用对象或链表实现以获得最佳性能，而数组实现则适合快速原型开发和小规模数据处理。 “`