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

队列是一种遵循

先进先出（FIFO，First-In-First-Out）

原则的元素集合。这意味着最早添加的元素会最先被移除，就像超市排队结账时，顾客按到达顺序依次被服务一样。

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

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

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

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

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

四、什么是链表？

链表是一种存储元素的方式：每个元素（称为“节点”）包含两部分——

实际数据

和

指向后一个节点的引用（或指针）

。

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

为什么用循环双向链表？

本教程将使用

循环双向链表（Circular Doubly Linked List）

实现队列，它的特点是：

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

这种结构的优势在于：

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

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

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

教程已在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(); } }