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

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

TypeScript no es solo una extensión de JavaScript. Gracias a su tipado estricto y capacidades modernas, TypeScript es ideal para implementar algoritmos y estructuras de datos complejos. En este artículo, analizaremos las estructuras de datos y algoritmos clave con ejemplos prácticos en TypeScript. Aprenderás a implementar una pila, cola, lista enlazada, tabla hash, y también dominarás los algoritmos de búsqueda binaria y ordenamiento.

1. Pila y cola: estructuras de datos fundamentales

La pila y la cola son estructuras básicas que se utilizan en todas partes: desde el manejo de llamadas a funciones hasta la gestión de tareas en el navegador.

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

La pila funciona bajo el principio de "último en entrar, primero en salir". La implementamos usando un array y genéricos de 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;    }}

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

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

La cola funciona bajo el principio de "primero en entrar, primero en salir". Implementación en 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;    }}

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

Importante: La operación shift() en JavaScript tiene una complejidad de O(n), ya que desplaza todos los elementos. Para una cola más eficiente, utiliza una lista enlazada o un búfer circular.

2. Lista enlazada (Linked List)

Una lista enlazada es una secuencia de nodos, donde cada nodo almacena datos y una referencia al siguiente nodo. En TypeScript, podemos usar interfaces para un tipado estricto.

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