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實現隊列有多種方式，各有優缺點。理解不同實現方式的特性，才能在實際開發中選擇最適合的方案。對于大多數生產環境，推薦使用對象或鏈表實現以獲得最佳性能，而數組實現則適合快速原型開發和小規模數據處理。 “`