Estruturas de Dados

Prévia do material em texto

Resumo Completo sobre Estruturas de Dados:
1. Introdução:
● Conceito: Estruturas de dados são maneiras organizadas de armazenar e gerenciar 
informações em um computador.
● Importância: Permitem que os programas acessem e manipulem dados de forma 
eficiente, otimizando o desempenho e a escalabilidade.
● Tipos de Dados:
○ Primitivos: Números (int, float), caracteres (char), booleanos (true/false).
○ Compostos: Strings (sequências de caracteres), arrays (coleções de elementos 
do mesmo tipo).
2. Arrays:
● Definição: Armazenamento sequencial de elementos do mesmo tipo em posições de 
memória contíguas.
● Características:
○ Acesso aleatório: Elementos podem ser acessados diretamente por seu índice.
○ Inserção/Remoção: Eficiente no final do array, mas custosa no meio.
○ Tamanho fixo: Pré-definido na criação, limitando o número de elementos.
● Operações:
○ Acesso: array[indice].
○ Inserção: array.push(valor).
○ Remoção: array.pop(), array.splice(indice, qtde).
○ Busca: array.indexOf(valor).
● Aplicações: Armazenar listas de dados homogêneos (números, nomes, etc.).
3. Listas Vinculadas:
● Definição: Coleção de elementos ("nós") conectados por ponteiros, sem posições de 
memória fixas.
● Características:
○ Flexibilidade: Inserção/remoção em qualquer posição sem reordenação.
○ Memória dinâmica: Adaptam-se ao número de elementos armazenados.
○ Acesso sequencial: Acesso a elementos por meio de ponteiros, menos eficiente 
que arrays para acesso aleatório.
● Tipos:
○ Simplesmente Encadeadas: Ponteiros apontam apenas para o próximo nó.
○ Duplamente Encadeadas: Ponteiros apontam para o próximo e para o anterior.
○ Circulares: O último nó aponta para o primeiro, formando um ciclo.
● Operações:
○ Acesso: Através de ponteiros, começando pelo nó inicial.
○ Inserção: Em qualquer posição, atualizando ponteiros dos nós adjacentes.
○ Remoção: Localizando o nó e atualizando ponteiros dos nós adjacentes.
○ Busca: Percorrendo a lista desde o início até encontrar o elemento desejado.
● Aplicações: Implementação de filas, pilhas, conjuntos, etc., onde a ordem de inserção é 
importante.
4. Pilhas:
● Definição: Estrutura LIFO ("Last In, First Out").
● Características:
○ Elementos são empilhados na ordem de inserção, mas removidos na ordem 
inversa.
● Operações:
○ Empilhar (push(valor)): Adiciona um elemento ao topo da pilha.
○ Desempilhar (pop()): Remove e retorna o elemento do topo da pilha.
○ Consultar topo (top()): Retorna o elemento do topo da pilha sem removê-lo.
● Aplicações: Desfazer/refazer em editores de texto, chamadas de função recursivas, 
gerenciamento de memória em sistemas operacionais.
5. Filas:
● Definição: Estrutura FIFO ("First In, First Out").
● Características:
○ Elementos são enfileirados na ordem de inserção e desenfileirados na mesma 
ordem.
● Operações:
○ Enfileirar (enqueue(valor)): Adiciona um elemento ao final da fila.
○ Desenfileirar (dequeue()): Remove e retorna o primeiro elemento da fila.
○ Consultar primeiro (front()): Retorna o primeiro elemento da fila sem removê-lo.
● Aplicações: Gerenciamento de tarefas, buffers de impressão, sistemas de atendimento 
(como bancos ou supermercados).
6. Dicionários (Tabelas Hash):
● Definição: Armazenamento de pares chave-valor, permitindo acesso rápido por chave.
● Características:
○ Organização por chave: Utiliza uma função hash para mapear chaves para 
índices na tabela.
○ Acesso eficiente por chave: Permite busca, inserção e remoção por chave em 
tempo médio constante (ideal para grandes conjuntos de dados).
○ **Colisões