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

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

1. Queue（队列）
2.   尾部（Back） ← 队首（Front）
3.     入队（enqueue）   出队（dequeue）

复制代码

在这篇实操教程中，你将学习如何使用链表在 TypeScript 中实现队列。以下是我们将要覆盖的内容：

• 前置条件
  
• 入门指南
  
• 什么是队列？
  
• 什么是链表？
  
• 什么是简单队列？
  
• 什么是循环队列？
  
• 什么是双端队列？
  
• 什么是优先队列？
  
• 何时使用（以及避免使用）队列
  
• 总结
  

一、前置条件

要学习本教程，你需要具备以下基础：

• TypeScript 基础：了解 TypeScript 的核心概念，如接口、类型和类。
  
• 算法基础：掌握数据结构与算法的基本概念，例如能使用大 O 表示法分析时间和空间复杂度。
  
• 链表数据结构：熟悉链表的工作原理。如果你需要补充这部分知识，可以参考于此文章配套的示例代码工程。
  

二、入门指南

本教程提供了一个实操项目，帮助你逐步实现队列并跟进学习。请按以下步骤开始：

• 克隆项目：从 GitHub 仓库克隆项目代码，边学边写。
  
• 项目结构：项目文件组织如下：
  

1. .
2. ├── index.ts                  // 入口文件
3. ├── examples                  // 示例目录（存放各队列的最终实现）
4. │   ├── 01-linked-list.ts     // 链表示例
5. │   ├── 02-simple-queue.ts    // 简单队列示例
6. │   ├── 03-circular-queue.ts  // 循环队列示例
7. │   ├── 04-double-ended-queue.ts  // 双端队列示例
8. │   └── 05-priority-queue.ts  // 优先队列示例
9. └── playground                // 实操目录（用于自己实现代码）
10.     ├── 01-linked-list.ts     // 链表实操文件
11.     ├── 02-simple-queue.ts    // 简单队列实操文件
12.     ├── 03-circular-queue.ts  // 循环队列实操文件
13.     ├── 04-double-ended-queue.ts  // 双端队列实操文件
14.     └── 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中提供了循环双向链表的代码，你可以直接使用。以下是核心代码及说明：
[code]//
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！