TypeScript 队列实战：从零实现简单、循环、双端、优先队列，附完整测试代码

燃愿君

发布于 2025-09-11 14:28:02

14500

代码可运行

运行总次数：0

代码可运行

队列是一种遵循先进先出（FIFO，First-In-First-Out） 原则的元素集合。这意味着最早添加的元素会最先被移除，就像超市排队结账时，顾客按到达顺序依次被服务一样。

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

在这篇实操教程中，你将学习如何使用链表在 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)），无需像数组那样移动元素。

接下来，我们先简要了解链表的基础知识，再开始实现队列。

四、什么是链表？

链表是一种存储元素的方式：每个元素（称为“节点”）包含两部分——实际数据和指向后一个节点的引用（或指针）。

与数组不同（数组元素在内存中连续存储），链表通过引用将节点连接成链状结构。

为什么用循环双向链表？

本教程将使用循环双向链表（Circular Doubly Linked List） 实现队列，它的特点是：

每个节点同时指向“下一个节点”和“上一个节点”；
最后一个节点的“下一个”指向第一个节点，第一个节点的“上一个”指向最后一个节点，形成闭环。

这种结构的优势在于：

支持双向遍历，无需处理“首尾为 null”的特殊情况；
简化队列的首尾操作（如双端队列的头尾插入/删除）；
保持操作效率为O(1)。

已提供的循环双向链表实现

教程已在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，适用于简单顺序任务；
循环队列：固定容量，适用于缓存缓冲区；
双端队列：双向操作，兼具队列与栈的特性；
优先队列：按优先级处理，适用于任务调度。

掌握队列的关键在于理解适用场景——既不要低估它在解耦和顺序处理中的作用，也不要在需要随机访问的场景中强行使用。

现在，你可以尝试在自己的项目中使用这些队列实现，解决实际开发中的顺序任务或异步问题了！祝你编码愉快！

本文是由葡萄城技术开发团队发布，转载请注明出处：葡萄城官网

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

typescript

本文系转载，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

typescript

登录后参与评论

0 条评论

热度