Estrutura De Dados

Resumo Prova de Estrutura de Dados

Pilhas:

Principais Operações: push() ; pop() ; top()

Aplicação: Calculadoras, compiladores e S.O’s.

Características:

- É uma estrutura linear de dados (ELD).

- LIFO (Last In First Out)

- Possuem a ordem invertida.

- São usadas para acesso rápido aos dados mais recentes.

- Geralmente são pequenas e são melhores implementadas em array[].

- As pilhas dinâmicas ocupam mais memória mas por outro lado não possuem limite.

Filas:

Principais Operações: entrar() ou enqueue() ; sair() ou dequeue() ; primeiro() ; valor()

Aplicação: Qualquer sistema que necessite de ordem de chegada.(Ordem de processos – Buffer de Impressora - uso de Array[]).

Características:

- É uma estrutura linear de dados (ELD).

- FIFO (First In First Out)

- Possuem a ordem preservada.

- Pode ser Circular (não possui início nem fim – uso de Array[])

- As filas dinâmicas ocupam mais memória mas por outro lado não possuem limite.

Listas:

Principais Operações:

• Atômicas: inserirAntesAtual() ; inserirDepoisAtual() ; removerAtual() ; acessarAtual() ; buscar(chave)

• Do Cursor: vaParaPrimeiro() ; vaParaUltimo() ; avançarXPosicoes() ; retrocederXPosicoes()

Aplicação: Qualquer sistema que necessite de um armazenamento temporário de dados. Ex: Lista de e-mails.

- É uma estrutura linear de dados (ELD).

- É uma estrutura “liberal”.

- Possui um atributo chamado cursor que determina uma possibilidade de métodos.

- É necessário varrer todos os elementos para efetuar uma busca.

- As técnicas do “pé atrás” e “da visão além do alcance” só servem para listas simples.

- Possibilidade da lista duplamente encadeada.

Hash:

- Geralmente é um Array de Listas.

- Pode ser uma Lista de Listas, mas é ruim por deixar o acesso extremamente lento, portanto não é recomendado.

- Fator de Carga: É a quantidade média de elementos (chaves) que devem ser alocados em cada posição do array.

- O fator de carga geralmente recomendado é de 2 a 4.

- O tamanho da tabela (Array) é geralmente baseado no Fator de Carga.

- As posições do array também são chamados de grupos e devem ser sempre números.

- Colisão: É quando duas chaves diferentes resultam no mesmo grupo ao passar pela mesma função Hash.

- Chaves Sinônimas: É quando essas chaves sofrem Colisão.

- Quando haver a necessidade de redimensionar a tabela deve-se criar uma nova tabela e re-inserir as chaves novamente com uma nova função Hash.

Características de uma boa função Hash:

- Ela é rápida;

- Distribui uniformemente os dados na tabela;

- Usa todos os dígitos da chave para o cálculo do código Hash (grupo);