Algoritmos y estructuras de datos en TypeScript: guía práctica

Algoritmos y estructuras de datos en TypeScript: de la teoría a la práctica

La comprensión de algoritmos y estructuras de datos es la base que distingue a un desarrollador experimentado de un principiante. TypeScript, gracias a su tipado estricto y capacidades modernas, permite escribir código confiable y legible para resolver problemas clásicos. En este artículo, analizaremos las estructuras de datos y algoritmos clave con ejemplos prácticos usando TypeScript. Aprenderás cómo implementar una pila, una cola, la búsqueda binaria y el ordenamiento rápido, y también te familiarizarás con los fundamentos del trabajo con grafos.

1. Estructuras de datos básicas: Pila y Cola

La pila y la cola son estructuras simples pero extremadamente útiles. La pila funciona bajo el principio LIFO (Last In, First Out), mientras que la cola sigue FIFO (First In, First Out). En TypeScript, es conveniente implementarlas basándose en un array utilizando genéricos para la seguridad de tipos.

Implementación de la Pila (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// Ejemplo de uso\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

Implementación de la Cola (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// Ejemplo de uso\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

Ten en cuenta: el método incorporado shift() tiene una complejidad de O(n), por lo que para grandes volúmenes de datos es mejor implementar la cola basándose en una lista enlazada.

2. Algoritmos de búsqueda: Lineal y Binaria

La búsqueda de elementos es una de las operaciones más comunes. La búsqueda lineal es simple pero lenta en grandes conjuntos de datos. La búsqueda binaria funciona en O(log n), pero requiere un array ordenado.

Búsqueda Lineal

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

Búsqueda Binaria (versión 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 la versión iterativa, usa un bucle while. TypeScript ayuda a evitar errores relacionados con los tipos: el genérico <T> garantiza que el array y el elemento objetivo sean del mismo tipo.

3. Ordenamiento: Ordenamiento Rápido (Quick Sort)

El ordenamiento rápido es uno de los algoritmos más eficientes con una complejidad promedio de O(n log n). R