🗂️ Estrutura de Dados
Fundamentos essenciais para organizar, armazenar e manipular dados de forma eficiente
⚡ Arrays • Listas • Pilhas • Filas • Dicionários • Complexidade O(n)
📌 O que são Estruturas de Dados?
Estruturas de dados são formas de organizar e armazenar dados em um computador para que possam ser usados de maneira eficiente. Cada estrutura tem suas próprias características, vantagens e desvantagens.
💡 A escolha certa da estrutura de dados pode transformar um algoritmo lento (O(n²)) em um extremamente rápido (O(log n)).
📊 Complexidade de Tempo (Big O)
- O(1) – Constante: acesso direto por índice
- O(log n) – Logarítmica: busca binária
- O(n) – Linear: percorrer todos os elementos
- O(n²) – Quadrática: loops aninhados
// Exemplo O(n) - percorrer array
function buscarElemento(arr, alvo) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === alvo) return i;
}
return -1;
}
📋 1. Array (Vetor)
Coleção ordenada de elementos acessíveis por índice. É a estrutura mais básica e amplamente utilizada.
// Declaração e operações
const frutas = ["maçã", "banana", "laranja"];
// Acesso O(1)
console.log(frutas[0]); // "maçã"
// Inserção no final O(1)
frutas.push("uva");
// Remoção do final O(1)
frutas.pop();
// Inserção no início O(n)
frutas.unshift("morango");
// Busca linear O(n)
const index = frutas.indexOf("banana");
📌 Arrays são ótimos para acesso indexado, mas inserções/remoções no início são custosas (O(n)).
🔗 2. Lista Ligada (Linked List)
Sequência de nós onde cada nó contém um valor e uma referência para o próximo nó.
class Node {
constructor(valor) {
this.valor = valor;
this.proximo = null;
}
}
class ListaLigada {
constructor() {
this.cabeca = null;
}
inserir(valor) {
const novoNo = new Node(valor);
novoNo.proximo = this.cabeca;
this.cabeca = novoNo;
}
imprimir() {
let atual = this.cabeca;
while (atual) {
console.log(atual.valor);
atual = atual.proximo;
}
}
}
const lista = new ListaLigada();
lista.inserir(10);
lista.inserir(20);
lista.imprimir(); // 20, 10
💡 Listas ligadas são excelentes para inserções/remoções frequentes no início ou meio.
🥞 3. Pilha (Stack) - LIFO
Estrutura Last-In-First-Out: o último elemento inserido é o primeiro a ser removido.
class Pilha {
constructor() {
this.itens = [];
}
push(elemento) { this.itens.push(elemento); }
pop() { return this.itens.pop(); }
peek() { return this.itens[this.itens.length - 1]; }
isEmpty() { return this.itens.length === 0; }
}
const pilha = new Pilha();
pilha.push("A");
pilha.push("B");
pilha.push("C");
console.log(pilha.pop()); // "C"
console.log(pilha.peek()); // "B"
📌 Aplicações: undo/redo, navegação de páginas, avaliação de expressões.
📬 4. Fila (Queue) - FIFO
Estrutura First-In-First-Out: o primeiro elemento inserido é o primeiro a ser removido.
class Fila {
constructor() {
this.itens = [];
}
enfileirar(elemento) { this.itens.push(elemento); }
desenfileirar() { return this.itens.shift(); }
frente() { return this.itens[0]; }
isEmpty() { return this.itens.length === 0; }
}
const fila = new Fila();
fila.enfileirar("Pessoa 1");
fila.enfileirar("Pessoa 2");
fila.enfileirar("Pessoa 3");
console.log(fila.desenfileirar()); // "Pessoa 1"
console.log(fila.frente()); // "Pessoa 2"
📌 Aplicações: filas de impressão, processamento de tarefas, buffers.
🗺️ 5. Dicionário / HashMap
Estrutura que armazena pares chave-valor. Busca por chave é O(1) em média.
// JavaScript Object / Map
const dicionario = new Map();
// Inserção O(1)
dicionario.set("nome", "João");
dicionario.set("idade", 30);
dicionario.set("cidade", "São Paulo");
// Busca O(1)
console.log(dicionario.get("nome")); // "João"
// Verificar existência O(1)
console.log(dicionario.has("idade")); // true
// Remoção O(1)
dicionario.delete("cidade");
// Iteração
dicionario.forEach((valor, chave) => {
console.log(`${chave}: ${valor}`);
});
💡 Dicionários são ideais para buscas rápidas, caches, contagem de frequência.
🌲 6. Conjunto (Set)
Coleção de valores únicos, sem duplicatas. Baseado em hash.
const conjunto = new Set();
conjunto.add(1);
conjunto.add(2);
conjunto.add(2); // ignorado (duplicado)
conjunto.add(3);
console.log(conjunto.size); // 3
console.log(conjunto.has(2)); // true
// Remover elemento
conjunto.delete(2);
// Converter array para conjunto (remover duplicatas)
const numeros = [1, 2, 2, 3, 4, 4, 5];
const unicos = [...new Set(numeros)];
console.log(unicos); // [1, 2, 3, 4, 5]
📌 Útil para garantir unicidade, operações de interseção e diferença entre coleções.
📊 Tabela de Complexidade
| Estrutura | Acesso | Busca | Inserção | Remoção |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Lista Ligada | O(n) | O(n) | O(1)* | O(1)* |
| Pilha | O(n) | O(n) | O(1) | O(1) |
| Fila | O(n) | O(n) | O(1) | O(1) |
| HashMap/Map | O(1) | O(1) | O(1) | O(1) |
| Set | O(1) | O(1) | O(1) | O(1) |
* Inserção/remoção no início ou com referência direta.
📝 Exercícios de Fixação
1. Inverter um Array
Implemente uma função que inverta os elementos de um array sem usar o método reverse().
2. Remover Duplicatas de um Array
Usando Set, remova elementos duplicados de um array.
3. Pilha: Verificar Parênteses Balanceados
Use uma pilha para verificar se os parênteses em uma expressão estão balanceados.
4. Contar Frequência com Map
Dado um array de strings, conte quantas vezes cada string aparece usando Map.
5. Fila: Simulação de Atendimento
Implemente uma fila de atendimento com operações de entrar na fila e chamar próximo.
✅ Boas Práticas
- ✔️ Escolha a estrutura adequada para a operação mais frequente
- ✔️ Considere a complexidade de tempo e espaço
- ✔️ Use Map/Set em vez de Object para chaves dinâmicas
- ✔️ Arrays são ótimos para acesso indexado, ruins para inserção no início
- ✔️ Pilhas e filas resolvem problemas específicos de ordem
📚 Referências e Prática
- 📖 "Entendendo Algoritmos" – Aditya Bhargava
- 📖 "Estruturas de Dados e Algoritmos com JavaScript" – Loiane Groner
- 💻 LeetCode – problemas de estrutura de dados
- 💻 HackerRank – prática estruturada
- 💻 Codewars – desafios diários
🎯 Pratique 15-30 minutos por dia para consolidar os conceitos.
🚀 Aplicações Práticas
- Arrays: listas de dados, resultados de API
- Pilhas: undo/redo, navegação de histórico
- Filas: processamento assíncrono, filas de mensagens
- Map/Dicionário: caches, configurações, agrupamentos
- Set: conjuntos únicos, interseções, tags
Post a Comment