队列是一种遵循先进先出（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，适用于简单顺序任务；
- 循环队列：固定容量，适用于缓存缓冲区；
- 双端队列：双向操作，兼具队列与栈的特性；
- 优先队列：按优先级处理，适用于任务调度。
掌握队列的关键在于理解适用场景——既不要低估它在解耦和顺序处理中的作用，也不要在需要随机访问的场景中强行使用。
现在，你可以尝试在自己的项目中使用这些队列实现，解决实际开发中的顺序任务或异步问题了！祝你编码愉快！
