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

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

Алгоритмы и структуры данных — это фундамент, на котором строится вся современная разработка программного обеспечения. Независимо от того, пишете ли вы фронтенд на React, бэкенд на Node.js или мобильное приложение, глубокое понимание этих концепций позволяет создавать эффективные, масштабируемые и быстрые приложения. В этой статье мы подробно разберем ключевые алгоритмы и структуры данных на TypeScript — языке, который сочетает в себе гибкость JavaScript и строгость статической типизации.

TypeScript идеально подходит для изучения алгоритмов: строгая типизация помогает избежать ошибок на этапе компиляции, а поддержка дженериков (generics) позволяет создавать универсальные и переиспользуемые структуры данных. Мы начнем с простых концепций и постепенно перейдем к более сложным темам, сопровождая каждый шаг наглядными примерами кода.

1. Основные структуры данных: Стек и Очередь

Стек (Stack) и Очередь (Queue) — это базовые линейные структуры данных, которые используются повсеместно: от управления историей браузера до планирования задач в операционных системах. Рассмотрим их реализацию на TypeScript.

Стек (LIFO — Last In, First Out)

Стек работает по принципу "последним пришел — первым вышел". Основные операции: push (добавление элемента) и pop (извлечение последнего элемента).

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

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

    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 stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2

Очередь (FIFO — First In, First Out)

Очередь работает по принципу "первым пришел — первым вышел". Основные операции: enqueue (добавление в конец) и dequeue (извлечение из начала).

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

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

    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 queue = new Queue<string>();
queue.enqueue("Первый");
queue.enqueue("Второй");
queue.enqueue("Третий");
console.log(queue.dequeue()); // "Первый"
console.log(queue.front()); // "Второй"

2. Алгоритмы поиска: Линейный и Бинарный поиск

Поиск данных — одна из самых частых операций в программировании. Мы рассмотрим два основных подхода: линейный поиск (простой, но медленный) и бинарный поиск (быстрый, но требующий отсортированных данных).

Линейный поиск

Алгоритм последовательно проверяет каждый элемент массива, пока не найдет искомый. Временная сложность: O(n).

function linearSearch<T>(arr: T[], target: T): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Возвращаем индекс найденного элемента
        }
    }
    return -1; // Элемент не найден
}

// Пример
const numbers = [10, 20, 30, 40, 50];
console.log(linearSearch(numbers, 30)); // 2
console.log(linearSearch(numbers, 60)); // -1

Бинарный поиск

Бинарный поиск работает только на отсортированных массивах. Он делит массив пополам на каждом шаге, отбрасывая половину, где искомого элемента точно нет. Временная сложность: O(log n).

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

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = sortedArr[mid];

        if (midValue === target) {
            return mid;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Пример
const sortedNumbers = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedNumbers, 7)); // 3
console.log(binarySearch(sortedNumbers, 4)); // -1

Важно: Бинарный поиск значительно быстрее линейного на больших объемах данных. Например, для массива из 1 миллиона элементов бинарному поиску потребуется всего около 20 итераций, в то время как линейному — до 1 миллиона.

3. Алгоритмы сортировки: Пузырьковая и Быстрая сортировка

Сортировка — это процесс упорядочивания элементов. Мы разберем два алгоритма: простую пузырьковую сортировку (для понимания основ) и эффективную быструю сортировку (для реальных проектов).

Пузырьковая сортировка (Bubble Sort)

Алгоритм многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке. Временная сложность: O(n²) в худшем случае.

function bubbleSort(arr: number[]): number[] {
    const n = arr.length;
    const result = [...arr]; // Создаем копию, чтобы не мутировать оригинал

    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - 1 - i; j++) {
            if (result[j] > result[j + 1]) {
                // Меняем местами
                [result[j], result[j + 1]] = [result[j + 1], result[j]];
                swapped = true;
            }
        }
        // Если за проход не было обменов, массив уже отсортирован
        if (!swapped) break;
    }
    return result;
}

// Пример
const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(unsorted)); // [11, 12, 22, 25, 34, 64