TypeScript 隊列實戰：從零實現簡單、循環、雙端、優先隊列，附完整測試代碼

隊列是一種遵循先進先出（FIFO，First-In-First-Out） 原則的元素集合。這意味著最早添加的元素會最先被移除，就像超市排隊結賬時，顧客按到達順序依次被服務一樣。

Queue（隊列）
  尾部（Back） ← 隊首（Front）
    入隊（enqueue）   出隊（dequeue）

a7b23f4919986d9370a9c7f1f5d36c36

在這篇實操教程中，你將學習如何使用鏈表在 TypeScript 中實現隊列。以下是我們將要覆蓋的內容：

前置條件
入門指南
什么是隊列？
什么是鏈表？
什么是簡單隊列？
什么是循環隊列？
什么是雙端隊列？
什么是優先隊列？
何時使用（以及避免使用）隊列
總結

一、前置條件

要學習本教程，你需要具備以下基礎：

TypeScript 基礎：了解 TypeScript 的核心概念，如接口、類型和類。
算法基礎：掌握數據結構與算法的基本概念，例如能使用大 O 表示法分析時間和空間復雜度。
鏈表數據結構：熟悉鏈表的工作原理。如果你需要補充這部分知識，可以參考于此文章配套的示例代碼工程。

二、入門指南

本教程提供了一個實操項目，幫助你逐步實現隊列并跟進學習。請按以下步驟開始：

克隆項目：從 GitHub 倉庫克隆項目代碼，邊學邊寫。
項目結構：項目文件組織如下：

.
├── index.ts                  // 入口文件
├── examples                  // 示例目錄（存放各隊列的最終實現）
│   ├── 01-linked-list.ts     // 鏈表示例
│   ├── 02-simple-queue.ts    // 簡單隊列示例
│   ├── 03-circular-queue.ts  // 循環隊列示例
│   ├── 04-double-ended-queue.ts  // 雙端隊列示例
│   └── 05-priority-queue.ts  // 優先隊列示例
└── playground                // 實操目錄（用于自己實現代碼）
    ├── 01-linked-list.ts     // 鏈表實操文件
    ├── 02-simple-queue.ts    // 簡單隊列實操文件
    ├── 03-circular-queue.ts  // 循環隊列實操文件
    ├── 04-double-ended-queue.ts  // 雙端隊列實操文件
    └── 05-priority-queue.ts  // 優先隊列實操文件

playground 目錄：用于編寫和測試你的代碼，是核心實操區域。
examples 目錄：存放每個功能的最終實現代碼。如果遇到問題卡殼，可以參考這里的解決方案（建議先自己嘗試再看答案）。

三、什么是隊列？

隊列是一種以先進先出（FIFO） 順序管理元素的數據結構——最早進入隊列的元素會最早被取出。

生活中的隊列示例

打印機處理任務時，如果你發送 3 個文檔打印，打印機將按接收順序依次處理：第一個文檔先打印，然后是第二個，最后是第三個。

編程中的隊列應用

隊列常用于需要按順序處理任務的場景，例如：

Web 服務器將 incoming 請求排隊，逐個處理；
聊天應用將消息排隊，按輸入順序發送；
導航應用將位置點排隊，用于廣度優先搜索（BFS） 逐層探索地圖。

4 種常見隊列類型

簡單隊列（Simple Queue）：僅允許從尾部添加元素、從頭部移除元素，嚴格遵循 FIFO。
循環隊列（Circular Queue）：與簡單隊列類似，但尾部元素會“連接”到頭部，形成循環，可復用空間。
雙端隊列（Double-Ended Queue，簡稱 Deque）：允許從頭部和尾部同時添加或移除元素，類似公交站排隊時，人可以從兩端進出。
優先隊列（Priority Queue）：不按到達順序處理元素，而是按“優先級”處理——優先級高的元素先被處理（如外賣 App 中，VIP 訂單優先于普通訂單）。

隊列的核心操作

所有隊列都包含一組基礎操作，本教程將重點實現以下常用操作：

enqueue（入隊）：將元素添加到隊列尾部（如顧客排到隊伍末尾）；
dequeue（出隊）：移除并返回隊列頭部的元素；
getFront（獲取隊首）：查看隊首元素但不移除（如查看隊伍最前面是誰）；
getRear（獲取隊尾）：查看隊尾元素但不移除（如查看隊伍最后是誰）；
isEmpty（判空）：檢查隊列是否為空；
isFull（判滿）：檢查隊列是否達到最大容量；
peek（預覽）：與 getFront 功能相同，快速查看隊首元素；
size（獲取大小）：返回隊列中的元素數量（如統計隊伍人數）。

為什么用鏈表實現隊列？

實現隊列的方式有多種，但本教程將使用基于鏈表的隊列——因為鏈表在“尾部插入”和“頭部刪除”這兩個隊列核心操作上效率極高（時間復雜度為O(1)），無需像數組那樣移動元素。

接下來，我們先簡要了解鏈表的基礎知識，再開始實現隊列。

a0f0591a27c5ba2f1095016c7edf314b

四、什么是鏈表？

鏈表是一種存儲元素的方式：每個元素（稱為“節點”）包含兩部分——實際數據和指向后一個節點的引用（或指針）。

與數組不同（數組元素在內存中連續存儲），鏈表通過引用將節點連接成鏈狀結構。

為什么用循環雙向鏈表？

本教程將使用循環雙向鏈表（Circular Doubly Linked List） 實現隊列，它的特點是：

每個節點同時指向“下一個節點”和“上一個節點”；
最后一個節點的“下一個”指向第一個節點，第一個節點的“上一個”指向最后一個節點，形成閉環。

這種結構的優勢在于：

支持雙向遍歷，無需處理“首尾為 null”的特殊情況；
簡化隊列的首尾操作（如雙端隊列的頭尾插入/刪除）；
保持操作效率為O(1)。

1f3b48ba74192ece70210d5f43c6a654

已提供的循環雙向鏈表實現

教程已在src/playground/01-linked-list.ts中提供了循環雙向鏈表的代碼，你可以直接使用。以下是核心代碼及說明：

// ?? src/playground/01-linked-list.ts

/**
 * 雙向鏈表的節點類
 */
export class NodeItem<T> {
  value: T;
  next: NodeItem<T> | null = null; // 指向后一個節點
  prev: NodeItem<T> | null = null; // 指向前一個節點

  constructor(value: T) {
    this.value = value;
  }
}

/**
 * 循環雙向鏈表類
 */
export class LinkedList<T> {
  private head: NodeItem<T> | null = null; // 頭節點
  private tail: NodeItem<T> | null = null; // 尾節點
  private currentSize: number = 0; // 當前節點數量

  /**
   * 向鏈表頭部添加節點
   * @param value 要添加的值
   */
  prepend(value: T): void { /* 實現略 */ }

  /**
   * 向鏈表尾部添加節點
   * @param value 要添加的值
   */
  append(value: T): void { /* 實現略 */ }

  /**
   * 移除并返回頭部節點的值
   * @returns 頭節點的值，為空時返回undefined
   */
  deleteHead(): T | undefined { /* 實現略 */ }

  /**
   * 移除并返回尾部節點的值
   * @returns 尾節點的值，為空時返回undefined
   */
  deleteTail(): T | undefined { /* 實現略 */ }

  /**
   * 查看頭部節點的值（不移除）
   * @returns 頭節點的值，為空時返回undefined
   */
  getHead(): T | undefined { /* 實現略 */ }

  /**
   * 查看尾部節點的值（不移除）
   * @returns 尾節點的值，為空時返回undefined
   */
  getTail(): T | undefined { /* 實現略 */ }

  /**
   * 檢查鏈表是否為空
   * @returns 為空返回true，否則返回false
   */
  isEmpty(): boolean { /* 實現略 */ }

  /**
   * 獲取鏈表當前大小
   * @returns 節點數量
   */
  size(): number { /* 實現略 */ }
}

該鏈表提供了 8 個核心方法，恰好滿足隊列實現的需求。接下來，我們開始實現第一個隊列——簡單隊列。

五、什么是簡單隊列？

簡單隊列是最基礎的隊列類型，嚴格遵循 FIFO 原則：只能從尾部添加元素，從頭部移除元素，就像火車站售票窗口前的隊伍。

簡單隊列的實現

打開src/playground/02-simple-queue.ts，按以下代碼實現簡單隊列（核心是復用上面的循環雙向鏈表）：

// ?? src/playground/02-simple-queue.ts
import { LinkedList } from "./01-linked-list";

/**
 * 基于循環雙向鏈表實現的簡單隊列
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>; // 用鏈表存儲隊列元素
  private maxSize?: number; // 可選的最大容量（不設置則無上限）

  /**
   * 構造函數
   * @param maxSize 可選，隊列的最大容量
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * 入隊：將元素添加到隊列尾部
   * @param item 要添加的元素
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("隊列已滿");
    }
    this.list.append(item); // 復用鏈表的append方法（添加到尾部）
  }

  /**
   * 出隊：移除并返回隊列頭部元素
   * @returns 隊首元素，為空時返回undefined
   */
  dequeue(): T | undefined {
    return this.list.deleteHead(); // 復用鏈表的deleteHead方法（刪除頭部）
  }

  /**
   * 獲取隊首元素（不移除）
   * @returns 隊首元素，為空時返回undefined
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * 獲取隊尾元素（不移除）
   * @returns 隊尾元素，為空時返回undefined
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * 檢查隊列是否為空
   * @returns 為空返回true，否則返回false
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * 檢查隊列是否已滿
   * @returns 已滿返回true，否則返回false
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * 預覽隊首元素（與getFront功能相同）
   * @returns 隊首元素，為空時返回undefined
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * 獲取隊列當前大小
   * @returns 元素數量
   */
  size(): number {
    return this.list.size();
  }
}

簡單隊列的工作原理

由于復用了鏈表的方法，簡單隊列的實現非常簡潔，核心邏輯如下：

enqueue（入隊）：先檢查隊列是否已滿，若未滿則調用鏈表的append方法將元素添加到尾部；
dequeue（出隊）：直接調用鏈表的deleteHead方法刪除并返回頭部元素；
判空/判滿：通過鏈表的isEmpty和自定義的isFull（結合maxSize）實現；
獲取首尾元素：復用鏈表的getHead和getTail方法。

測試簡單隊列

實現完成后，在項目根目錄運行以下命令測試代碼是否正確：

npm run test:file 02

如果測試失敗，可以參考src/examples/02-simple-queue.ts中的最終代碼調試。

六、什么是循環隊列？

循環隊列是一種固定容量的隊列，尾部元素與頭部元素“相連”形成閉環——當頭部元素被移除后，其空間可以被新元素復用，就像自助餐臺上循環補充的餐盤。

循環隊列與簡單隊列的區別

循環隊列的核心特點是必須指定最大容量（簡單隊列的最大容量是可選的），因此更適合需要控制內存或資源的場景（如實時系統、緩存緩沖區）。

循環隊列的實現

打開src/playground/03-circular-queue.ts，實現代碼如下：

// ?? src/playground/03-circular-queue.ts
import { LinkedList } from "./01-linked-list";

/**
 * 基于循環雙向鏈表實現的循環隊列
 */
export class CircularQueue<T> {
  private list: LinkedList<T>;
  private maxSize: number; // 循環隊列必須有固定最大容量

  /**
   * 構造函數（必須傳入最大容量）
   * @param maxSize 隊列的最大容量
   */
  constructor(maxSize: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * 入隊：添加元素到尾部
   * @param item 要添加的元素
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("循環隊列已滿");
    }
    this.list.append(item);
  }

  /**
   * 出隊：移除并返回頭部元素
   * @returns 隊首元素，為空時返回undefined
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  // 以下方法與SimpleQueue一致，略去注釋
  getFront(): T | undefined { return this.list.getHead(); }
  getRear(): T | undefined { return this.list.getTail(); }
  isEmpty(): boolean { return this.list.isEmpty(); }
  isFull(): boolean { return this.list.size() >= this.maxSize; }
  peek(): T | undefined { return this.getFront(); }
  size(): number { return this.list.size(); }
}

循環隊列的核心差異

與簡單隊列相比，循環隊列只有 2 個關鍵區別：

構造函數：maxSize是必填參數，強制隊列有固定容量；
設計意圖：循環隊列針對“固定緩沖區”場景設計，例如網絡數據傳輸中的數據包緩存——當隊列滿時必須等待前序元素被處理，才能添加新元素。

測試循環隊列

運行以下命令測試：

npm run test:file 03

七、什么是雙端隊列？

雙端隊列（Deque，全稱 Double-Ended Queue）是一種靈活的隊列：允許從頭部和尾部同時添加或移除元素，就像公交站的“雙向排隊”——人可以從隊首或隊尾上車/下車。

雙端隊列的實現

打開src/playground/04-double-ended-queue.ts，實現代碼如下：

// ?? src/playground/04-double-ended-queue.ts
import { LinkedList } from "./01-linked-list";

/**
 * 基于循環雙向鏈表實現的雙端隊列
 */
export class Deque<T> {
  private list: LinkedList<T>;
  private maxSize?: number; // 可選最大容量

  /**
   * 構造函數
   * @param maxSize 可選，隊列的最大容量
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * 從頭部入隊
   * @param item 要添加的元素
   */
  enqueueFront(item: T): void {
    if (this.isFull()) {
      throw new Error("雙端隊列已滿");
    }
    this.list.prepend(item); // 復用鏈表的prepend方法（添加到頭部）
  }

  /**
   * 從尾部入隊
   * @param item 要添加的元素
   */
  enqueueRear(item: T): void {
    if (this.isFull()) {
      throw new Error("雙端隊列已滿");
    }
    this.list.append(item); // 復用鏈表的append方法（添加到尾部）
  }

  /**
   * 從頭部出隊
   * @returns 隊首元素，為空時返回undefined
   */
  dequeueFront(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * 從尾部出隊
   * @returns 隊尾元素，為空時返回undefined
   */
  dequeueRear(): T | undefined {
    return this.list.deleteTail(); // 復用鏈表的deleteTail方法（刪除尾部）
  }

  // 以下方法與SimpleQueue一致，略去注釋
  getFront(): T | undefined { return this.list.getHead(); }
  getRear(): T | undefined { return this.list.getTail(); }
  isEmpty(): boolean { return this.list.isEmpty(); }
  isFull(): boolean { return this.maxSize !== undefined && this.list.size() >= this.maxSize; }
  peek(): T | undefined { return this.getFront(); }
  size(): number { return this.list.size(); }
}

雙端隊列的核心特點

雙端隊列的關鍵在于雙向操作能力，這使其同時具備“隊列”和“棧”的特性：

若只使用enqueueRear和dequeueFront：表現為普通隊列（FIFO）；
若只使用enqueueFront和dequeueFront：表現為棧（LIFO，后進先出）。

適用場景包括： undo/redo 功能（前一步操作可從隊尾撤銷）、滑動窗口算法（兩端添加/移除窗口元素）。

測試雙端隊列

運行以下命令測試：

npm run test:file 04

八、什么是優先隊列？

優先隊列不遵循 FIFO 原則，而是按元素的優先級處理：優先級高的元素先出隊，就像醫院急診室——重癥患者優先于輕癥患者被救治。

優先隊列的實現

打開src/playground/05-priority-queue.ts，實現代碼如下（核心是“插入時排序”）：

// ?? src/playground/05-priority-queue.ts
import { LinkedList, NodeItem } from "./01-linked-list";

/**
 * 帶優先級的元素接口
 */
interface PriorityItem<T> {
  value: T;       // 元素值
  priority: number; // 優先級（數字越大，優先級越高）
}

/**
 * 基于循環雙向鏈表實現的優先隊列
 */
export class PriorityQueue<T> {
  private list: LinkedList<PriorityItem<T>>; // 存儲帶優先級的元素
  private maxSize?: number;

  constructor(maxSize?: number) {
    this.list = new LinkedList<PriorityItem<T>>();
    this.maxSize = maxSize;
  }

  /**
   * 入隊：按優先級插入元素（優先級高的靠前）
   * @param value 元素值
   * @param priority 優先級（數字越大優先級越高）
   */
  enqueue(value: T, priority: number): void {
    if (this.isFull()) {
      throw new Error("優先隊列已滿");
    }

    const newItem: PriorityItem<T> = { value, priority };

    // 若隊列為空，直接插入頭部
    if (this.isEmpty()) {
      this.list.prepend(newItem);
      return;
    }

    // 遍歷鏈表，找到插入位置（確保鏈表按優先級降序排列）
    let current = this.list["head"]; // 訪問鏈表的私有head屬性
    let count = 0;
    while (current && current.value.priority >= priority && count < this.size()) {
      current = current.next;
      count++;
    }

    // 若遍歷到隊尾，直接添加到尾部
    if (count === this.size()) {
      this.list.append(newItem);
    } else {
      // 否則在當前位置插入新節點（手動維護鏈表的循環結構）
      const newNode = new NodeItem(newItem);
      newNode.next = current;
      newNode.prev = current!.prev;

      if (current!.prev) {
        current!.prev.next = newNode;
      } else {
        this.list["head"] = newNode; // 若插入到頭部，更新head
      }

      current!.prev = newNode;
      // 維護循環：尾節點的next指向新head，新head的prev指向尾節點
      this.list["tail"]!.next = this.list["head"];
      this.list["head"]!.prev = this.list["tail"];
      this.list["currentSize"]++; // 更新鏈表大小
    }
  }

  /**
   * 出隊：移除并返回優先級最高的元素（隊首）
   * @returns 優先級最高的元素值，為空時返回undefined
   */
  dequeue(): T | undefined {
    // 隊首元素就是優先級最高的，直接刪除并返回其value
    return this.list.deleteHead()?.value;
  }

  /**
   * 獲取優先級最高的元素（不移除）
   * @returns 優先級最高的元素值
   */
  getFront(): T | undefined {
    return this.list.getHead()?.value;
  }

  /**
   * 獲取優先級最低的元素（不移除）
   * @returns 優先級最低的元素值
   */
  getRear(): T | undefined {
    return this.list.getTail()?.value;
  }

  // 以下方法與其他隊列一致，略去注釋
  isEmpty(): boolean { return this.list.isEmpty(); }
  isFull(): boolean { return this.maxSize !== undefined && this.list.size() >= this.maxSize; }
  peek(): T | undefined { return this.getFront(); }
  size(): number { return this.list.size(); }
}

優先隊列的核心邏輯

優先隊列的關鍵在于入隊時的排序：

每個元素都關聯一個優先級（數字越大優先級越高）；
入隊時遍歷鏈表，將元素插入到“第一個優先級低于它”的元素前面，確保鏈表始終按優先級降序排列；
出隊時直接刪除隊首元素（即優先級最高的元素），效率為O(1)。

適用場景包括：任務調度（高優先級任務先執行）、Dijkstra 最短路徑算法（優先選擇距離最近的節點）。

測試優先隊列

運行以下命令測試：

npm run test:file 05

九、何時使用隊列（以及何時避免使用）

隊列是處理“順序任務”和“異步流程”的利器，但并非萬能。正確判斷適用場景是關鍵。

適合使用隊列的場景

順序處理任務：需要按 arrival 順序處理的場景，如打印機任務隊列、API 請求限流。
異步通信：消息隊列（如 RabbitMQ、Kafka）用于解耦微服務——生產者發送消息到隊列，消費者異步處理，避免服務直接依賴。
緩沖數據流：實時系統（如視頻流、傳感器數據）中，用隊列緩沖突發數據，避免下游處理不及時導致數據丟失。
算法實現：廣度優先搜索（BFS）、拓撲排序等算法必須依賴隊列。

避免使用隊列的場景

需要隨機訪問元素：隊列只支持首尾操作，若需訪問中間元素（如“查找第 5 個元素”），效率極低（O(n)），此時應使用數組或鏈表。
復雜搜索/排序：隊列不適合“按條件搜索元素”或“動態排序”，應使用哈希表、二叉搜索樹等數據結構。
過度解耦系統：在微服務中盲目使用隊列會增加調試難度（如消息丟失、延遲排查），且可能導致“隊列積壓”（backpressure），反而降低系統穩定性。

十、總結

隊列是一種基礎但強大的數據結構，核心價值在于按順序管理元素和支持異步處理。本教程通過循環雙向鏈表實現了 4 種常見隊列：

簡單隊列：基礎 FIFO，適用于簡單順序任務；
循環隊列：固定容量，適用于緩存緩沖區；
雙端隊列：雙向操作，兼具隊列與棧的特性；
優先隊列：按優先級處理，適用于任務調度。

掌握隊列的關鍵在于理解適用場景——既不要低估它在解耦和順序處理中的作用，也不要在需要隨機訪問的場景中強行使用。

現在，你可以嘗試在自己的項目中使用這些隊列實現，解決實際開發中的順序任務或異步問題了！祝你編碼愉快！

posted @ 2025-09-09 12:17 葡萄城技術團隊閱讀(378) 評論(0) 收藏舉報

刷新頁面返回頂部

TypeScript 隊列實戰：從零實現簡單、循環、雙端、優先隊列，附完整測試代碼

一、前置條件

二、入門指南

三、什么是隊列？

4 種常見隊列類型

為什么用鏈表實現隊列？

四、什么是鏈表？

五、什么是簡單隊列？

六、什么是循環隊列？

七、什么是雙端隊列？

八、什么是優先隊列？

九、何時使用隊列（以及何時避免使用）

十、總結

公告