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

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

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

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

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

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

Реализация Стека (Stack)

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

Реализация Очереди (Queue)

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 queue = new Queue<string>();
queue.enqueue('A');
queue.enqueue('B');
console.log(queue.dequeue()); // A
console.log(queue.front()); // B

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

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

Поиск элементов — одна из самых частых операций. Линейный поиск прост, но медленен на больших данных. Бинарный поиск работает за O(log 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 = [3, 7, 1, 9, 4];
console.log(linearSearch(numbers, 9)); // 3

Бинарный поиск (рекурсивная версия)

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

    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
        return mid;
    }

    if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

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

Для итеративной версии используйте цикл while. TypeScript помогает избежать ошибок, связанных с типами: дженерик <T> гарантирует, что массив и целевой элемент одного типа.

3. Сортировка: Быстрая сортировка (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 = [8, 3, 1, 7, 0, 4, 2];
console.log(quickSort(unsorted)); // [0, 1, 2, 3, 4, 7, 8]

Эта версия проста для понимания, но использует дополнительную память. Для оптимизации можно реализовать сортировку "in-place" (без создания новых массивов).

4. Работа с графами: Поиск в ширину (BFS)

Графы используются для моделирования связей: социальные сети, карты, маршруты. BFS (Breadth-First Search) позволяет найти кратчайший путь в невзвешенном графе. Реализуем его с помощью очереди.

interface Graph {
    [key: string]: string[];
}

function bfs(graph: Graph, start: string): string[] {
    const visited: Set<string> = new Set();
    const queue: string[] = [start];
    const result: string[] = [];

    visited.add(start);

    while (queue.length > 0) {
        const vertex = queue.shift()!;
        result.push(vertex);

        for (const neighbor of graph[vertex]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }

    return result;
}

// Пример графа
const graph: Graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'F'],
    D: ['B'],
    E: ['B', 'F'],
    F: ['C', 'E']
};

console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E', 'F']

TypeScript позволяет строго описать структуру графа через интерфейс, что делает код самодокументируемым и безопасным. Обратите внимание на использование Set для отслеживания посещённых вершин — это гарантирует уникальность и быстроту проверки.