Dominando Estruturas de Dados: Do Básico ao Avançado

Estruturas de dados são fundamentais na programação e na ciência da computação. Este artigo é uma jornada completa por esse tema, começando do básico e avançando até conceitos mais complexos. O conteúdo é estruturado em aulas, conforme um curso de Estruturas de Dados personalizado. Vamos lá!

1. Apresentação da Disciplina

A disciplina de Estruturas de Dados é essencial para qualquer programador. Ela ensina como organizar e manipular dados de maneira eficiente. Os conceitos aprendidos aqui são aplicáveis em diversas linguagens de programação e são a base para a resolução de problemas complexos.

2. Criação de uma Primeira Estrutura

Antes de mergulhar em estruturas complexas, é importante entender como criar uma estrutura de dados simples. Vamos criar uma lista linear sequencial como exemplo.

class ListaSequencial {
    constructor() {
        this.elementos = [];
    }

    adicionar(elemento) {
        this.elementos.push(elemento);
    }
}

3. Lista Linear Sequencial

As listas lineares sequenciais são fundamentais e podem ser usadas para armazenar dados em sequência.

3.1 Continuação da Lista Linear Sequencial

Uma vez que você entende a adição de elementos, é importante saber como acessar e remover itens.

class ListaSequencial {
    // Métodos anteriores...

    remover(index) {
        return this.elementos.splice(index, 1);
    }

    acessar(index) {
        return this.elementos[index];
    }
}

4. Lista Ligada

Uma lista ligada é uma estrutura que consiste em nós, onde cada nó contém um dado e uma referência ao próximo nó.

4.1 Implementação Estática

Na implementação estática, utilizamos arrays para armazenar nós.

class No {
    constructor(dado) {
        this.dado = dado;
        this.proximo = null;
    }
}

class ListaLigada {
    constructor() {
        this.cabeca = null;
    }

    adicionar(dado) {
        const novoNo = new No(dado);
        // lógica para adicionar o nó
    }
}

4.2 Implementação Dinâmica

Na implementação dinâmica, os nós são alocados à medida que são necessários.

class ListaLigada {
    // Métodos anteriores...

    adicionar(dado) {
        const novoNo = new No(dado);
        // lógica para adicionar o novo nó
    }
}

4.3 Lista Ligada Circular com Nó Cabeça

Uma lista ligada circular tem a característica de que o último nó aponta para o primeiro.

class ListaCircular {
    constructor() {
        this.cabeca = null;
    }

    adicionar(dado) {
        // lógica para adicionar em uma lista circular
    }
}

5. Pilhas

Pilhas são estruturas de dados que seguem o princípio LIFO (Last In, First Out).

5.1 Implementação Estática

class PilhaEstatica {
    constructor(tamanho) {
        this.itens = new Array(tamanho);
        this.topo = -1;
    }

    push(elemento) {
        this.itens[++this.topo] = elemento;
    }

    pop() {
        return this.itens[this.topo--];
    }
}

5.2 Implementação Dinâmica

Na implementação dinâmica, a pilha pode crescer conforme necessário.

class PilhaDinamica {
    constructor() {
        this.itens = [];
    }

    push(elemento) {
        this.itens.push(elemento);
    }

    pop() {
        return this.itens.pop();
    }
}

6. Filas

Filas seguem o princípio FIFO (First In, First Out).

6.1 Implementação Estática

class FilaEstatica {
    constructor(tamanho) {
        this.itens = new Array(tamanho);
        this.frente = 0;
        this.traseira = 0;
    }

    enqueue(elemento) {
        this.itens[this.traseira++] = elemento;
    }

    dequeue() {
        return this.itens[this.frente++];
    }
}

6.2 Implementação Dinâmica

class FilaDinamica {
    constructor() {
        this.itens = [];
    }

    enqueue(elemento) {
        this.itens.push(elemento);
    }

    dequeue() {
        return this.itens.shift();
    }
}

7. Deque

Um Deque (Double Ended Queue) permite inserções e remoções em ambas as extremidades.

class Deque {
    constructor() {
        this.itens = [];
    }

    adicionarFrente(elemento) {
        this.itens.unshift(elemento);
    }

    adicionarTras(elemento) {
        this.itens.push(elemento);
    }

    removerFrente() {
        return this.itens.shift();
    }

    removerTras() {
        return this.itens.pop();
    }
}

8. Matrizes Esparsas

Matrizes esparsas são usadas quando a maioria dos elementos são zeros. Elas podem ser armazenadas de forma mais eficiente.

class MatrizEsparsa {
    constructor() {
        this.elementos = {};
    }

    adicionar(linha, coluna, valor) {
        if (valor !== 0) {
            this.elementos[`${linha},${coluna}`] = valor;
        }
    }

    acessar(linha, coluna) {
        return this.elementos[`${linha},${coluna}`] || 0;
    }
}

9. Árvores

As árvores são estruturas hierárquicas e são fundamentais para diversos algoritmos.

9.1 Árvores Binárias de Pesquisa

As árvores binárias de pesquisa (BST) permitem buscas, inserções e remoções rápidas.

class No {
    constructor(dado) {
        this.dado = dado;
        this.esquerda = null;
        this.direita = null;
    }
}

class ArvoreBinaria {
    constructor() {
        this.raiz = null;
    }

    inserir(dado) {
        // lógica para inserir na árvore
    }

    buscar(dado) {
        // lógica para buscar na árvore
    }
}

9.2 Árvores N-árias e Tries

Árvores N-árias permitem que cada nó tenha N filhos, enquanto Tries são usadas para armazenar strings de maneira eficiente.

class Trie {
    constructor() {
        this.children = {};
        this.fimDePalavra = false;
    }

    inserir(palavra) {
        // lógica para inserir uma palavra
    }
}

9.3 Árvores AVL

As árvores AVL são uma forma de árvore binária de pesquisa que se mantém balanceada.

class NoAVL {
    // implementação do nó AVL
}

class ArvoreAVL {
    // implementação da árvore AVL
}

10. Grafos

Os grafos são estruturas complexas que representam relações entre objetos.

10.1 Representação de Grafos

Os grafos podem ser representados por listas de adjacência ou matrizes de adjacência.

class Grafo {
    constructor() {
        this.vertices = {};
    }

    adicionarVertice(v) {
        this.vertices[v] = [];
    }

    adicionarAresta(v1, v2) {
        this.vertices[v1].push(v2);
        this.vertices[v2].push(v1); // se for não direcionado
    }
}

10.2 Busca em Largura e Profundidade

Esses algoritmos são usados para percorrer grafos.

function buscaEmLargura(grafo, inicio) {
    // implementação do algoritmo
}

function buscaEmProfundidade(grafo, inicio) {
    // implementação do algoritmo
}

10.3 Algoritmo de Dijkstra

O Algoritmo de Dijkstra é usado para encontrar o caminho mais curto em um grafo ponderado.

function dijkstra(grafo, inicio) {
    // implementação do algoritmo
}

Conclusão

Neste artigo, cobrimos uma jornada completa pelo mundo das estruturas de dados, desde conceitos básicos como listas e pilhas até grafos e árvores avançadas. A compreensão dessas estruturas permite que você resolva problemas de programação de maneira mais eficiente e eficaz. Pratique a implementação e utilize esses conceitos em projetos reais para solidificar seu aprendizado!