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

Algoritmos e Estruturas de Dados em TypeScript: da Teoria à Prática

Compreender algoritmos e estruturas de dados é a base que diferencia um desenvolvedor experiente de um iniciante. TypeScript, graças à tipagem forte e aos recursos modernos, permite escrever código confiável e legível para resolver problemas clássicos. Neste artigo, abordaremos as principais estruturas de dados e algoritmos com exemplos práticos usando TypeScript. Você aprenderá como implementar pilha, fila, busca binária e ordenação rápida, além de conhecer os fundamentos do trabalho com grafos.

1. Estruturas de Dados Básicas: Pilha e Fila

Pilha e fila são estruturas simples, mas extremamente úteis. A pilha funciona pelo princípio LIFO (Last In, First Out), enquanto a fila opera como FIFO (First In, First Out). Em TypeScript, é conveniente implementá-las com base em arrays usando genéricos para segurança de tipos.

Implementação da Pilha (Stack)

class Stack<T> {\n    private items: T[] = [];\n\n    push(item: T): void {\n        this.items.push(item);\n    }\n\n    pop(): T | undefined {\n        return this.items.pop();\n    }\n\n    peek(): T | undefined {\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Exemplo de uso\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

Implementação da Fila (Queue)

class Queue<T> {\n    private items: T[] = [];\n\n    enqueue(item: T): void {\n        this.items.push(item);\n    }\n\n    dequeue(): T | undefined {\n        return this.items.shift();\n    }\n\n    front(): T | undefined {\n        return this.items[0];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Exemplo de uso\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

Observe: o método embutido shift() tem complexidade O(n), portanto, para grandes volumes de dados, é melhor implementar a fila com base em uma lista encadeada.

2. Algoritmos de Busca: Linear e Binária

A busca de elementos é uma das operações mais comuns. A busca linear é simples, mas lenta em grandes conjuntos de dados. A busca binária opera em O(log n), mas requer um array ordenado.

Busca Linear

function linearSearch<T>(arr: T[], target: T): number {\n    for (let i = 0; i < arr.length; i++) {\n        if (arr[i] === target) {\n            return i;\n        }\n    }\n    return -1;\n}\n\nconst numbers = [3, 7, 1, 9, 4];\nconsole.log(linearSearch(numbers, 9)); // 3

Busca Binária (versão recursiva)

function binarySearch<T>(arr: T[], target: T, left: number = 0, right: number = arr.length - 1): number {\n    if (left > right) {\n        return -1;\n    }\n\n    const mid = Math.floor((left + right) / 2);\n\n    if (arr[mid] === target) {\n        return mid;\n    }\n\n    if (arr[mid] > target) {\n        return binarySearch(arr, target, left, mid - 1);\n    } else {\n        return binarySearch(arr, target, mid + 1, right);\n    }\n}\n\nconst sortedArray = [1, 3, 5, 7, 9, 11];\nconsole.log(binarySearch(sortedArray, 7)); // 3\nconsole.log(binarySearch(sortedArray, 6)); // -1

Para a versão iterativa, use o loop while. TypeScript ajuda a evitar erros relacionados a tipos: o genérico <T> garante que o array e o elemento alvo sejam do mesmo tipo.

3. Ordenação: Ordenação Rápida (Quick Sort)

A ordenação rápida é um dos algoritmos mais eficientes, com complexidade média O(n log n). R