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生態中，隊列概念廣泛應用于事件處理、狀態管理、異步流程控制等領域，是每個開發者必須掌握的基礎知識。 “`