JavaScript數據結構之優先隊列與循環隊列怎么實現

# JavaScript數據結構之優先隊列與循環隊列怎么實現

## 一、隊列基礎概念回顧

### 1.1 什么是隊列
隊列（Queue）是一種先進先出（FIFO, First In First Out）的線性數據結構，只允許在表的前端（front）進行刪除操作，在表的后端（rear）進行插入操作。

### 1.2 隊列的基本操作
- `enqueue(element)`：向隊列尾部添加元素
- `dequeue()`：移除隊列首部元素
- `peek()`：查看隊列首部元素
- `isEmpty()`：判斷隊列是否為空
- `size()`：獲取隊列長度

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

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

  dequeue() {
    return this.items.shift();
  }

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

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

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

二、優先隊列的實現

2.1 優先隊列概念

優先隊列中元素被賦予優先級，具有最高優先級的元素最先被移除（不一定是先進先出）。

2.2 實現方案一：入隊時排序

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

  // 定義隊列元素結構
  QueueElement = class {
    constructor(element, priority) {
      this.element = element;
      this.priority = priority;
    }
  }

  enqueue(element, priority) {
    const queueElement = new this.QueueElement(element, priority);
    
    if (this.isEmpty()) {
      this.items.push(queueElement);
    } else {
      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);
      }
    }
  }

  // 其他方法與基礎隊列相同
  dequeue() {
    return this.items.shift();
  }

  // ...省略其他方法
}

2.3 實現方案二：使用堆結構（更高效）

class HeapPriorityQueue {
  constructor() {
    this.heap = [];
  }

  // 獲取父節點索引
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // 上浮操作
  heapifyUp(index) {
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex].priority > this.heap[index].priority) {
        [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  enqueue(element, priority) {
    const node = { element, priority };
    this.heap.push(node);
    this.heapifyUp(this.heap.length - 1);
  }

  // 下沉操作
  heapifyDown(index) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let smallest = index;
    
    if (leftChildIndex < this.heap.length && 
        this.heap[leftChildIndex].priority < this.heap[smallest].priority) {
      smallest = leftChildIndex;
    }
    
    if (rightChildIndex < this.heap.length && 
        this.heap[rightChildIndex].priority < this.heap[smallest].priority) {
      smallest = rightChildIndex;
    }
    
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.heapifyDown(smallest);
    }
  }

  dequeue() {
    if (this.isEmpty()) return null;
    const root = this.heap[0];
    const lastNode = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = lastNode;
      this.heapifyDown(0);
    }
    return root;
  }

  // ...其他方法
}

2.4 優先隊列的應用場景

• 醫院急診科病人分診
• 操作系統進程調度
• 網絡帶寬管理
• Dijkstra最短路徑算法

三、循環隊列的實現

3.1 循環隊列概念

循環隊列是一種線性數據結構，其操作基于FIFO原則，并且隊尾被連接在隊首之后以形成一個循環。

3.2 為什么需要循環隊列

普通隊列在出隊操作時，前面的空間會被浪費。循環隊列可以重復利用這些空間。

3.3 數組實現循環隊列

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() {
    if (this.isEmpty()) return -1;
    return this.queue[this.head];
  }

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

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

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

3.4 鏈表實現循環隊列

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

class LinkedCircularQueue {
  constructor(k) {
    this.capacity = k;
    this.count = 0;
    this.head = null;
    this.tail = null;
  }

  enQueue(value) {
    if (this.isFull()) return false;
    
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }
    
    this.tail = newNode;
    this.tail.next = this.head; // 形成循環
    this.count++;
    return true;
  }

  deQueue() {
    if (this.isEmpty()) return false;
    
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.tail.next = this.head; // 維護循環
    }
    
    this.count--;
    return true;
  }

  // ...其他方法
}

3.5 循環隊列的應用場景

• 內存管理中的緩沖區
• 流量控制系統
• CPU調度
• 音樂播放列表循環

四、性能分析與比較

4.1 時間復雜度對比

4.2 空間復雜度

所有隊列實現的空間復雜度均為O(n)

4.3 如何選擇

• 需要優先級處理：選擇優先隊列
• 頻繁入隊出隊且數據量大：選擇循環隊列
• 簡單FIFO需求：基礎隊列即可

五、實際應用案例

5.1 優先隊列案例：任務調度系統

class TaskScheduler {
  constructor() {
    this.priorityQueue = new HeapPriorityQueue();
  }

  addTask(task, priority) {
    this.priorityQueue.enqueue(task, priority);
  }

  processTasks() {
    while (!this.priorityQueue.isEmpty()) {
      const task = this.priorityQueue.dequeue();
      console.log(`Processing task: ${task.element} (Priority: ${task.priority})`);
      // 實際處理任務的邏輯...
    }
  }
}

5.2 循環隊列案例：擊鼓傳花游戲

function hotPotato(elements, num) {
  const queue = new CircularQueue(elements.length);
  
  // 初始化隊列
  elements.forEach(el => queue.enQueue(el));
  
  while (queue.count > 1) {
    // 傳遞num次
    for (let i = 0; i < num; i++) {
      queue.enQueue(queue.Front());
      queue.deQueue();
    }
    // 淘汰持有物品的人
    console.log(`${queue.Front()}被淘汰`);
    queue.deQueue();
  }
  
  return queue.Front();
}

六、總結

本文詳細介紹了JavaScript中優先隊列和循環隊列的實現方式：

1. 優先隊列可以通過數組排序或堆結構實現，堆實現效率更高
2. 循環隊列通過數組或鏈表實現，能有效利用存儲空間
3. 不同隊列適用于不同場景，理解其特性才能正確選擇

隊列作為基礎數據結構，在算法和系統設計中應用廣泛。掌握這些高級隊列的實現，能夠幫助開發者解決更復雜的實際問題。

七、延伸閱讀與練習題

7.1 推薦閱讀

• 《算法導論》堆和優先隊列章節
• MDN Array文檔
• ECMAScript規范中關于數組的部分

7.2 練習題

1. 實現一個支持動態優先級變更的優先隊列
2. 設計一個雙端循環隊列
3. 使用循環隊列解決約瑟夫環問題
4. 比較不同隊列在百萬級數據下的性能差異

”`

注：本文實際約2900字，包含了代碼示例、性能分析和實際應用案例，采用Markdown格式編寫，可直接用于技術博客發布。