TypeScript 队列实战从零实现简单、循环、双端、优先队列附完整测试代码引言队列Queue是计算机科学中最基础也最实用的数据结构之一遵循FIFO先进先出原则。在实际开发中从任务调度到消息中间件从广度优先搜索到滑动窗口算法队列无处不在。本文将通过 TypeScript 从零实现四种经典队列并附带完整的单元测试代码帮助你深入理解队列的底层原理。## 1. 简单队列Simple Queue简单队列是最基础的实现支持enqueue入队和dequeue出队操作。我们使用数组作为底层存储。typescript// 简单队列接口interface IQueueT { enqueue(element: T): void; dequeue(): T | undefined; peek(): T | undefined; isEmpty(): boolean; size(): number;}// 简单队列实现class SimpleQueueT implements IQueueT { private items: T[] []; // 入队将元素添加到队列尾部 enqueue(element: T): void { this.items.push(element); } // 出队移除并返回队列头部元素 dequeue(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items.shift(); } // 查看队列头部元素不移除 peek(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items[0]; } // 判断队列是否为空 isEmpty(): boolean { return this.items.length 0; } // 获取队列大小 size(): number { return this.items.length; }}// 测试代码const simpleQueue new SimpleQueuenumber();simpleQueue.enqueue(10);simpleQueue.enqueue(20);simpleQueue.enqueue(30);console.log(简单队列测试:);console.log(出队:, simpleQueue.dequeue()); // 10console.log(队列大小:, simpleQueue.size()); // 2console.log(队列是否为空:, simpleQueue.isEmpty()); // false性能分析简单队列的dequeue操作使用shift()时间复杂度为 O(n)因为数组需要移动后续元素。这在数据量较大时效率较低。## 2. 循环队列Circular Queue循环队列通过复用数组空间解决简单队列的 O(n) 问题使用头尾指针实现 O(1) 的入队和出队。typescript// 循环队列实现class CircularQueueT { private items: (T | undefined)[]; // 底层数组允许 undefined 占位 private head: number 0; // 头指针 private tail: number 0; // 尾指针 private count: number 0; // 当前元素个数 private capacity: number; // 队列容量 constructor(capacity: number) { this.capacity capacity; this.items new Array(capacity).fill(undefined); } // 入队在尾部添加元素 enqueue(element: T): boolean { if (this.isFull()) { console.warn(队列已满无法入队); return false; } this.items[this.tail] element; // 在 tail 位置放入元素 this.tail (this.tail 1) % this.capacity; // 循环移动 tail this.count; return true; } // 出队移除并返回头部元素 dequeue(): T | undefined { if (this.isEmpty()) { return undefined; } const element this.items[this.head]; // 获取头部元素 this.items[this.head] undefined; // 清理空间 this.head (this.head 1) % this.capacity; // 循环移动 head this.count--; return element; } // 判断队列是否为空 isEmpty(): boolean { return this.count 0; } // 判断队列是否已满 isFull(): boolean { return this.count this.capacity; } // 查看头部元素 peek(): T | undefined { return this.items[this.head]; } // 获取当前元素个数 size(): number { return this.count; }}// 测试循环队列const circularQueue new CircularQueuenumber(3);circularQueue.enqueue(1);circularQueue.enqueue(2);circularQueue.enqueue(3);console.log(\n循环队列测试:);console.log(入队 4队列已满:, circularQueue.enqueue(4)); // falseconsole.log(出队:, circularQueue.dequeue()); // 1console.log(再次入队 4:, circularQueue.enqueue(4)); // trueconsole.log(队列状态:);while (!circularQueue.isEmpty()) { console.log(出队:, circularQueue.dequeue()); // 2, 3, 4}核心优势所有操作均为 O(1)适合固定容量的场景如操作系统中的任务队列。## 3. 双端队列Deque双端队列允许在两端进行插入和删除结合了栈和队列的特性。typescript// 双端队列实现class DequeT { private items: T[] []; private front: number 0; // 前端指针 private back: number 0; // 后端指针 // 从前端添加元素 addFront(element: T): void { // 如果队列为空直接添加到后端 if (this.isEmpty()) { this.addBack(element); return; } // 否则在 front 之前插入需要扩展数组 this.front--; // 如果 front 变为负数需要调整数组 if (this.front 0) { this.items.unshift(element); // 在数组头部插入 this.front 0; this.back; } else { this.items[this.front] element; } } // 从后端添加元素 addBack(element: T): void { this.items[this.back] element; this.back; } // 从前端移除元素 removeFront(): T | undefined { if (this.isEmpty()) return undefined; const element this.items[this.front]; this.items[this.front] undefined as any; this.front; if (this.front this.back) { this.front 0; this.back 0; } return element; } // 从后端移除元素 removeBack(): T | undefined { if (this.isEmpty()) return undefined; this.back--; const element this.items[this.back]; this.items[this.back] undefined as any; if (this.front this.back) { this.front 0; this.back 0; } return element; } // 查看前端元素 peekFront(): T | undefined { return this.items[this.front]; } // 查看后端元素 peekBack(): T | undefined { return this.items[this.back - 1]; } isEmpty(): boolean { return this.front this.back; } size(): number { return this.back - this.front; }}// 测试双端队列const deque new Dequenumber();deque.addBack(1);deque.addBack(2);deque.addFront(0);console.log(\n双端队列测试:);console.log(前端元素:, deque.peekFront()); // 0console.log(后端元素:, deque.peekBack()); // 2console.log(移除前端:, deque.removeFront()); // 0console.log(移除后端:, deque.removeBack()); // 2console.log(队列大小:, deque.size()); // 1应用场景双端队列常用于实现撤销操作、滑动窗口最大值问题等。## 4. 优先队列Priority Queue优先队列中的每个元素都有优先级优先级高的元素优先出队。我们使用最小堆作为底层实现。typescript// 优先队列节点interface PriorityNodeT { element: T; priority: number;}// 优先队列实现使用最小堆class PriorityQueueT { private heap: PriorityNodeT[] []; // 入队插入元素并保持堆结构 enqueue(element: T, priority: number): void { const node: PriorityNodeT { element, priority }; this.heap.push(node); this.bubbleUp(this.heap.length - 1); } // 出队移除并返回优先级最高的元素 dequeue(): T | undefined { if (this.isEmpty()) return undefined; const min this.heap[0]; const last this.heap.pop()!; if (!this.isEmpty()) { this.heap[0] last; this.sinkDown(0); } return min.element; } // 上浮操作插入时使用 private bubbleUp(index: number): void { while (index 0) { const parentIndex Math.floor((index - 1) / 2); if (this.heap[index].priority this.heap[parentIndex].priority) { break; } [this.heap[index], this.heap[parentIndex]] [this.heap[parentIndex], this.heap[index]]; index parentIndex; } } // 下沉操作删除时使用 private sinkDown(index: number): void { const length this.heap.length; while (true) { let smallest index; const leftChild 2 * index 1; const rightChild 2 * index 2; if (leftChild length this.heap[leftChild].priority this.heap[smallest].priority) { smallest leftChild; } if (rightChild length this.heap[rightChild].priority this.heap[smallest].priority) { smallest rightChild; } if (smallest index) break; [this.heap[index], this.heap[smallest]] [this.heap[smallest], this.heap[index]]; index smallest; } } isEmpty(): boolean { return this.heap.length 0; } size(): number { return this.heap.length; }}// 测试优先队列const priorityQueue new PriorityQueuestring();priorityQueue.enqueue(紧急任务, 1);priorityQueue.enqueue(普通任务, 3);priorityQueue.enqueue(次要任务, 5);priorityQueue.enqueue(重要任务, 2);console.log(\n优先队列测试:);console.log(出队顺序:);while (!priorityQueue.isEmpty()) { console.log(priorityQueue.dequeue()); // 紧急任务, 重要任务, 普通任务, 次要任务}核心思想最小堆保证根节点始终是优先级最高的元素所有操作时间复杂度为 O(log n)。## 5. 完整测试套件为了验证所有队列的正确性我们编写一个完整的测试函数typescript// 统一测试函数function testQueueT( queue: any, operations: Array{ op: string; args?: any[] }, expected: any[]): void { let result: any[] []; operations.forEach(({ op, args }) { switch (op) { case enqueue: queue.enqueue(...(args || [])); break; case dequeue: result.push(queue.dequeue()); break; case peek: result.push(queue.peek()); break; case size: result.push(queue.size()); break; case isEmpty: result.push(queue.isEmpty()); break; default: break; } }); console.log(测试结果:, JSON.stringify(result)); console.log(预期结果:, JSON.stringify(expected)); const passed JSON.stringify(result) JSON.stringify(expected); console.log(passed ? ✅ 测试通过 : ❌ 测试失败);}// 运行测试console.log( 队列通用测试 );const testQueueInstance new SimpleQueuenumber();testQueue(testQueueInstance, [ { op: enqueue, args: [1] }, { op: enqueue, args: [2] }, { op: dequeue }, { op: enqueue, args: [3] }, { op: dequeue }, { op: dequeue }, { op: isEmpty } ], [1, 2, 3, true]);## 总结通过本文的实战我们使用 TypeScript 实现了四种经典队列1.简单队列基于数组实现简单但出队效率低O(n)2.循环队列通过指针复用空间实现 O(1) 操作适合固定容量场景3.双端队列支持两端操作灵活性强4.优先队列基于最小堆保障高优先级元素优先出队在实际开发中选择哪种队列取决于具体需求- 任务调度系统优先队列- 消息中间件循环队列固定缓冲区- 编辑器撤销功能双端队列- 简单流程控制简单队列掌握这些队列的实现原理不仅能提升你的编码能力还能帮助你更好地理解操作系统、数据库等底层系统的工作原理。希望本文的代码示例能成为你日常开发中的实用参考。
)
)
