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

TypeScript中的算法与数据结构：实战篇

TypeScript不仅仅是JavaScript的超集。得益于严格的类型系统和现代特性，TypeScript非常适合实现复杂的算法与数据结构。本文将结合实际TypeScript示例，讲解关键的数据结构与算法。您将学习如何实现栈、队列、链表、哈希表，并掌握二分查找与排序算法。

1. 栈与队列：基础数据结构

栈和队列是基础数据结构，广泛应用于函数调用处理到浏览器任务管理等场景。

栈 (Stack) — LIFO (后进先出)

栈遵循"后进先出"原则。我们使用数组和TypeScript泛型来实现：

class Stack<T> {    private items: T[] = [];

    push(item: T): void {        this.items.push(item);    }

    pop(): T | undefined {        return this.items.pop();    }

    peek(): T | undefined {        return this.items[this.items.length - 1];    }

    isEmpty(): boolean {        return this.items.length === 0;    }

    size(): number {        return this.items.length;    }}

// 使用示例const numberStack = new Stack<number>();numberStack.push(10);numberStack.push(20);console.log(numberStack.pop()); // 20console.log(numberStack.peek()); // 10

队列 (Queue) — FIFO (先进先出)

队列遵循"先进先出"原则。TypeScript实现如下：

class Queue<T> {    private items: T[] = [];

    enqueue(item: T): void {        this.items.push(item);    }

    dequeue(): T | undefined {        return this.items.shift();    }

    front(): T | undefined {        return this.items[0];    }

    isEmpty(): boolean {        return this.items.length === 0;    }

    size(): number {        return this.items.length;    }}

// 使用示例const stringQueue = new Queue<string>();stringQueue.enqueue('A');stringQueue.enqueue('B');console.log(stringQueue.dequeue()); // 'A'console.log(stringQueue.front());   // 'B'

重要提示： JavaScript中的shift()操作时间复杂度为O(n)，因为需要移动所有元素。如需更高性能的队列，请使用链表或环形缓冲区。

2. 链表 (Linked List)

链表是由节点组成的序列，每个节点存储数据并指向下一个节点。在TypeScript中，我们可以使用接口实现严格类型定义。

interface ListNode<T> {    value: T;    next: ListNode<T> | null;}

class LinkedList<T> {    private head: ListNode<T> | null = null;

    append(value: T): void {        const newNode: ListNode<T> = { value, next: null };        if (!this.head) {            this.head = newNode;            return;        }        let current = this.head;        while (current.next) {            current = current.next;        }        current.next = newNode;    }

    prepend(value: T): void {        const newNode: ListNode<T> = { value, next: this.head };        this.head = newNode;    }

    delete(value: T): void {        if (!this.head) return;        if (this.head.value === value) {            this.head = this.head.next;            return;        }        let current = this.head;        while (current.next) {            if (current.next.value === value) {                current.next = current.next.next;                return;            }            current = current.next;        }    }

    print(): void {        let current = this.head;        const values: T[] = [];