Algoritmos e Estruturas de Dados em TypeScript: Guia Prático

Algoritmos e Estruturas de Dados em TypeScript: na Prática

TypeScript não é apenas uma extensão do JavaScript. Graças à tipagem estática e aos recursos modernos, o TypeScript é ideal para implementar algoritmos e estruturas de dados complexos. Neste artigo, abordaremos as principais estruturas de dados e algoritmos com exemplos práticos em TypeScript. Você aprenderá como implementar pilha, fila, lista encadeada, tabela hash, além de dominar os algoritmos de busca binária e ordenação.

1. Pilha e Fila: Estruturas de Dados Fundamentais

Pilha e fila são estruturas básicas usadas em toda parte: desde o processamento de chamadas de funções até o gerenciamento de tarefas no navegador.

Pilha (Stack) — LIFO (Last In, First Out)

A pilha funciona pelo princípio "o último a entrar é o primeiro a sair". Vamos implementá-la usando um array e genéricos do 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;    }}

// Exemplo de usoconst numberStack = new Stack<number>();numberStack.push(10);numberStack.push(20);console.log(numberStack.pop()); // 20console.log(numberStack.peek()); // 10

Fila (Queue) — FIFO (First In, First Out)

A fila funciona pelo princípio "o primeiro a entrar é o primeiro a sair". Implementação em 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;    }}

// Exemplo de usoconst stringQueue = new Queue<string>();stringQueue.enqueue('A');stringQueue.enqueue('B');console.log(stringQueue.dequeue()); // 'A'console.log(stringQueue.front());   // 'B'

Importante: A operação shift() em JavaScript tem complexidade O(n), pois desloca todos os elementos. Para uma fila mais eficiente, use uma lista encadeada ou um buffer circular.

2. Lista Encadeada (Linked List)

A lista encadeada é uma sequência de nós, onde cada nó armazena dados e uma referência ao próximo nó. Em TypeScript, podemos usar interfaces para tipagem estrita.

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[] = [];