Алгоритмы и структуры данных на TypeScript: полное руководство

Введение: Почему алгоритмы и структуры данных важны в TypeScript?

В современной веб-разработке TypeScript занимает лидирующие позиции, предлагая строгую типизацию и мощные инструменты для создания масштабируемых приложений. Однако даже самый элегантный код не будет эффективным без понимания фундаментальных алгоритмов и структур данных. Эта статья — ваш путеводитель в мир оптимизированного кода на TypeScript. Мы разберем ключевые структуры данных, покажем, как их реализовать с учетом типов, и рассмотрим классические алгоритмы. После прочтения вы сможете писать не только работающий, но и быстрый, предсказуемый код.

1. Базовые структуры данных с типизацией

TypeScript позволяет строго определить, какие типы данных могут храниться в структуре. Это предотвращает ошибки на этапе компиляции. Рассмотрим три фундаментальные структуры.

1.1. Стек (Stack) — принцип LIFO

Стек работает по принципу "последним пришел — первым вышел" (Last In, First Out). Идеально подходит для задач, где нужно откатывать действия (например, история в браузере).

// Реализация стека с дженериком T
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;
    }
}

// Пример использования
const numberStack = new Stack<number>();
numberStack.push(10);
numberStack.push(20);
console.log(numberStack.pop()); // 20

1.2. Очередь (Queue) — принцип FIFO

Очередь работает по принципу "первым пришел — первым вышел" (First In, First Out). Используется для обработки задач в порядке их поступления, например, в системах очередей сообщений.

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];
    }

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

// Пример с пользовательским типом
interface Task {
    id: number;
    name: string;
}
const taskQueue = new Queue<Task>();
taskQueue.enqueue({ id: 1, name: 'Обработать заказ' });
taskQueue.enqueue({ id: 2, name: 'Отправить email' });

1.3. Связный список (Linked List)

Связный список состоит из узлов, каждый из которых ссылается на следующий. В отличие от массива, вставка и удаление элементов в середине списка не требует сдвига всех элементов.

class ListNode<T> {
    value: T;
    next: ListNode<T> | null = null;

    constructor(value: T) {
        this.value = value;
    }
}

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

    add(value: T): void {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    print(): void {
        let current = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}

// Использование
const list = new LinkedList<string>();
list.add('TypeScript');
list.add('Python');
list.print(); // TypeScript, Python

2. Алгоритмы сортировки и поиска

Сортировка данных — одна из самых частых операций. TypeScript позволяет создавать универсальные функции, которые работают с любыми типами данных.

2.1. Быстрая сортировка (Quick Sort)

Один из самых эффективных алгоритмов со средней сложностью O(n log n). Работает по принципу "разделяй и властвуй".

function quickSort<T>(arr: T[]): T[] {
    if (arr.length <= 1) return arr;

    const pivot = arr[arr.length - 1];
    const left: T[] = [];
    const right: T[] = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

const unsorted = [5, 2, 9, 1, 5, 6];
console.log(quickSort(unsorted)); // [1, 2, 5, 5, 6, 9]

2.2. Бинарный поиск (Binary Search)

Работает только на отсортированных массивах. Делит массив пополам на каждом шаге, имея сложность O(log n).

function binarySearch<T>(arr: T[], target: T): number {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Не найден
}

const sortedArr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(sortedArr, 7)); // 3
console.log(binarySearch(sortedArr, 2)); // -1

3. Деревья и графы: работа с иерархическими данными

Деревья и графы — основа для работы с вложенными структурами, маршрутами и социальными связями.

3.1. Бинарное дерево поиска (BST)

Каждый узел имеет не более двух потомков. Левый потомок всегда меньше родителя, правый — больше. Это обеспечивает быстрый поиск.

class TreeNode<T> {
    value: T;
    left: TreeNode<T> | null = null;
    right: TreeNode<T> | null = null;

    constructor(value: T) {
        this.value = value;
    }
}

class BinarySearchTree<T> {
    root: TreeNode<T> | null = null;

    insert(value: T): void {
        const newNode = new TreeNode(value);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return;