Shared 函数库

Appearance

Queue ​

队列（FIFO）数据结构，先进先出。

函数签名 ​

typescript
function createQueue<T>(): Queue<T>

interface Queue<T> {
  enqueue(item: T): void
  dequeue(): T | undefined
  peek(): T | undefined
  size(): number
  isEmpty(): boolean
  clear(): void
  toArray(): T[]
}

API 说明 ​

enqueue(item: T): void ​

在队列尾部添加元素。

参数：

  • item: 要添加的元素

时间复杂度：O(1)

dequeue(): T | undefined ​

移除并返回队列头部的元素。

返回值：

  • 队列头部的元素，如果队列为空则返回 undefined

时间复杂度：O(n)（使用 shift 方法）

peek(): T | undefined ​

查看队列头部的元素，但不移除。

返回值：

  • 队列头部的元素，如果队列为空则返回 undefined

时间复杂度：O(1)

size(): number ​

获取队列中元素的数量。

返回值：

  • 队列中元素的数量

时间复杂度：O(1)

isEmpty(): boolean ​

检查队列是否为空。

返回值：

  • 如果队列为空则返回 true，否则返回 false

时间复杂度：O(1)

clear(): void ​

清空队列中的所有元素。

时间复杂度：O(1)

toArray(): T[] ​

返回队列中所有元素的数组副本（从队首到队尾）。

返回值：

  • 包含所有元素的数组

时间复杂度：O(n)

使用示例 ​

typescript
import { createQueue } from '@shared/functions/data-structures/Queue'

// 创建队列
const queue = createQueue<number>()

// 入队操作
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

// 查看队首
console.log(queue.peek())  // 1

// 出队操作
console.log(queue.dequeue())  // 1
console.log(queue.dequeue())  // 2

// 获取队列大小
console.log(queue.size())  // 1

// 检查是否为空
console.log(queue.isEmpty())  // false

// 转换为数组
console.log(queue.toArray())  // [3]

// 清空队列
queue.clear()
console.log(queue.isEmpty())  // true

工作原理 ​

队列是一种先进先出（FIFO）的数据结构，类似于现实中的排队场景：

  • 新元素总是添加到队尾（enqueue）
  • 移除操作总是从队首开始（dequeue）
  • 先加入的元素先被移除

本实现使用数组作为底层数据结构：

  • enqueue 使用 push 添加到数组末尾 - O(1)
  • dequeue 使用 shift 从数组开头移除 - O(n)

应用场景 ​

  1. 任务调度：按顺序处理任务
  2. 广度优先搜索（BFS）：图的遍历算法
  3. 消息队列：异步消息处理
  4. 打印队列：按顺序打印文档
  5. 缓冲区管理：数据流处理

性能优化建议 ​

如果需要频繁的出队操作，可以考虑使用循环队列或链表实现来提高性能。当前实现的 dequeue 操作为 O(n)，因为使用了数组的 shift 方法。

Copyright © 2023-present