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

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

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

Начать курс

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

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

1. Стек и очередь: фундаментальные структуры данных

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

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

Стек работает по принципу «последний пришёл — первый ушёл». Реализуем его с помощью массива и дженериков 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()); // 20
console.log(numberStack.peek()); // 10

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

Очередь работает по принципу «первый пришёл — первый ушёл». Реализация на 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'

Важно: Операция shift() в JavaScript имеет сложность 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[] = [];
        while (current) {
            values.push(current.value);
            current = current.next;
        }
        console.log(values.join(' -> '));
    }
}

// Пример использования
const list = new LinkedList<number>();
list.append(1);
list.append(2);
list.prepend(0);
list.print(); // 0 -> 1 -> 2
list.delete(1);
list.print(); // 0 -> 2

Связные списки эффективны для вставки и удаления элементов в начале списка (O(1)), но медленны для доступа по индексу (O(n)).

3. Хеш-таблица (Hash Table)

Хеш-таблица — одна из самых полезных структур данных. Она обеспечивает доступ к данным за O(1) в среднем. Реализуем простую версию с разрешением коллизий методом цепочек.

class HashTable<K, V> {
    private buckets: Array<Array<[K, V]>>;
    private size: number;

    constructor(size: number = 32) {
        this.size = size;
        this.buckets = new Array(size).fill(null).map(() => []);
    }

    private hash(key: K): number {
        const strKey = String(key);
        let hash = 0;
        for (let i = 0; i < strKey.length; i++) {
            hash = (hash + strKey.charCodeAt(i) * i) % this.size;
        }
        return hash;
    }

    set(key: K, value: V): void {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value; // обновление существующего ключа
                return;
            }
        }
        bucket.push([key, value]);
    }

    get(key: K): V | undefined {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        for (const [storedKey, storedValue] of bucket) {
            if (storedKey === key) {
                return storedValue;
            }
        }
        return undefined;
    }

    delete(key: K): boolean {
        const index = this.hash(key);
        const bucket = this.buckets[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        return false;
    }
}

// Пример использования
const phoneBook = new HashTable<string, string>();
phoneBook.set('Alice', '123-456');
phoneBook.set('Bob', '789-012');
console.log(phoneBook.get('Alice')); // '123-456'
phoneBook.delete('Bob');
console.log(phoneBook.get('Bob'));   // undefined

В реальных проектах используйте встроенный Map или Set, но понимание внутреннего устройства хеш-таблицы — важный навык.