TypeScript 算法与数据结构：实用指南

TypeScript 算法与数据结构：从理论到实践

理解算法与数据结构是区分经验丰富的开发者和新手的基础。TypeScript 凭借其严格的类型检查和现代特性，能够编写可靠且可读的代码来解决经典问题。在本文中，我们将通过使用 TypeScript 的实际示例来解析关键的数据结构和算法。您将学习如何实现栈、队列、二分查找和快速排序，并了解图的基本操作。

1. 基本数据结构：栈和队列

栈和队列是最简单但极其有用的数据结构。栈遵循 LIFO（后进先出）原则，而队列遵循 FIFO（先进先出）原则。在 TypeScript 中，可以方便地基于数组并使用泛型来实现类型安全。

栈的实现

class Stack<T> {\n    private items: T[] = [];\n\n    push(item: T): void {\n        this.items.push(item);\n    }\n\n    pop(): T | undefined {\n        return this.items.pop();\n    }\n\n    peek(): T | undefined {\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// 使用示例\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

队列的实现

class Queue<T> {\n    private items: T[] = [];\n\n    enqueue(item: T): void {\n        this.items.push(item);\n    }\n\n    dequeue(): T | undefined {\n        return this.items.shift();\n    }\n\n    front(): T | undefined {\n        return this.items[0];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// 使用示例\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

请注意：内置方法 shift() 的时间复杂度为 O(n)，因此对于大量数据，最好基于链表实现队列。

2. 搜索算法：线性搜索和二分查找

元素搜索是最常见的操作之一。线性搜索简单，但在大数据集上较慢。二分查找的时间复杂度为 O(log n)，但要求数组已排序。

线性搜索

function linearSearch<T>(arr: T[], target: T): number {\n    for (let i = 0; i < arr.length; i++) {\n        if (arr[i] === target) {\n            return i;\n        }\n    }\n    return -1;\n}\n\nconst numbers = [3, 7, 1, 9, 4];\nconsole.log(linearSearch(numbers, 9)); // 3

二分查找（递归版本）

function binarySearch<T>(arr: T[], target: T, left: number = 0, right: number = arr.length - 1): number {\n    if (left > right) {\n        return -1;\n    }\n\n    const mid = Math.floor((left + right) / 2);\n\n    if (arr[mid] === target) {\n        return mid;\n    }\n\n    if (arr[mid] > target) {\n        return binarySearch(arr, target, left, mid - 1);\n    } else {\n        return binarySearch(arr, target, mid + 1, right);\n    }\n}\n\nconst sortedArray = [1, 3, 5, 7, 9, 11];\nconsole.log(binarySearch(sortedArray, 7)); // 3\nconsole.log(binarySearch(sortedArray, 6)); // -1

对于迭代版本，请使用 while 循环。TypeScript 有助于避免与类型相关的错误：泛型 <T> 确保数组和目标元素类型一致。

3. 排序：快速排序

快速排序是最有效的算法之一，平均时间复杂度为 O(n log n)。R