Алгоритмы и структуры данных на TypeScript: полный гайд для начинающих

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

Понимание алгоритмов и структур данных — фундамент, который отличает профессионального разработчика от любителя. Если вы только начинаете свой путь в программировании на TypeScript, эта статья поможет вам разобраться с ключевыми концепциями. Мы разберём базовые структуры данных (массивы, стек, очередь) и простые алгоритмы (линейный и бинарный поиск), а также покажем, как реализовать их на TypeScript с учётом строгой типизации.

1. Массивы и работа с ними в TypeScript

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

// Объявление типизированного массива чисел
const numbers: number[] = [5, 12, 8, 130, 44];

// Массив строк
const fruits: Array<string> = ['apple', 'banana', 'cherry'];

// Доступ по индексу
console.log(numbers[0]); // 5

// Добавление элемента в конец
numbers.push(100);

// Удаление последнего элемента
const last = numbers.pop();

Важно: TypeScript проверяет типы на этапе компиляции. Если вы попытаетесь добавить строку в массив чисел, компилятор выдаст ошибку. Это делает код более надёжным.

2. Стек и очередь: принципы LIFO и FIFO

Стек (Stack) работает по принципу LIFO (Last In, First Out — последним пришёл, первым ушёл). Очередь (Queue) — по принципу FIFO (First In, First Out — первым пришёл, первым ушёл).

Реализация стека на TypeScript

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

// Использование
const stack = new Stack<number>();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20
console.log(stack.peek()); // 10

Реализация очереди на TypeScript

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

// Использование
const queue = new Queue<string>();
queue.enqueue('задача 1');
queue.enqueue('задача 2');
console.log(queue.dequeue()); // 'задача 1'

Обратите внимание на использование дженериков <T>. Это позволяет создавать структуры данных, работающие с любым типом, сохраняя при этом строгую типизацию.

3. Алгоритмы поиска: линейный и бинарный

Поиск — одна из самых частых операций. Рассмотрим два базовых алгоритма.

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

Проходит по всем элементам массива, пока не найдёт нужный. Сложность: 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 data = [3, 7, 1, 9, 4];
console.log(linearSearch(data, 9)); // 3
console.log(linearSearch(data, 10)); // -1

Бинарный поиск (только для отсортированных массивов)

Делит массив пополам на каждом шаге. Сложность: O(log n). Это значительно быстрее линейного поиска для больших массивов.

function binarySearch(arr: number[], target: number): 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;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// Массив должен быть отсортирован!
const sortedArr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArr, 7)); // 3
console.log(binarySearch(sortedArr, 4)); // -1

Практический совет: Если данные не отсортированы, но вы планируете выполнять много поисков, имеет смысл сначала отсортировать массив (например, с помощью Array.sort()), а затем использовать бинарный поиск.

4. Рекурсия на примере факториала

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

function factorial(n: number): number {
    // Базовый случай: факториал 0 и 1 равен 1
    if (n === 0 || n === 1) {
        return 1;
    }
    // Рекурсивный случай
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)
console.log(factorial(0)); // 1

Важно: Всегда определяйте базовый случай, иначе рекурсия будет бесконечной и приведёт к переполнению стека (stack overflow). TypeScript (как и JavaScript) имеет ограничение на глубину рекурсии.

Заключение

Мы рассмотрели основные структуры данных (массивы, стек, очередь) и алгоритмы (линейный и бинарный поиск, рекурсию) на TypeScript. Эти концепции являются фундаментом для более сложных алгоритмов — сортировки, обхода графов, динамического программирования.

Что делать дальше?

• Попробуйте реализовать связный список на TypeScript.
• Изучите алгоритмы сортировки: пузырьковую, быструю (quick sort), слиянием (merge sort).
• Решайте задачи на платформах вроде LeetCode или Codewars, используя TypeScript.

Помните: теория без практики бесполезна. Берите каждый алгоритм