h2 Resumo Completo: Pilhas, Filas, Listas e Hash

Resumo Prova de Estrutura de Dados

Pilhas:

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

Aplicação: Calculadoras, compiladores e Sistemas Operacionais (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 houver 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);

- Não restringe o tamanho da tabela;

- O usuário tem a liberdade de decidir o tamanho da tabela em função do melhor desempenho e fator de carga desejado;

Exemplos de Função Hash:

- Função do Resto; Função da Dobra; Função da Potência; Função Randômica Programada;

Exemplos de questão de Prova:

1. Qual a utilidade do uso de um esquema circular na implementação de uma fila?

R: Ao se optar pela implementação circular, você consegue economizar espaço e ganhar performance, se comparado com uma fila não circular. Como as filas geralmente são implementadas em um array, se ela não fosse circular, deveria haver métodos para realocar o conteúdo para o início do array, sempre que um ou alguns elementos fossem retirados da lista. E por causa disso o array deveria ser necessariamente um pouco maior do que o caso circular, pois existe uma certa perda de espaço para não prejudicar totalmente a performance.

1. Considere que existe uma tabela de espalhamento de tamanho N e um conjunto de dados de tamanho M, já distribuídos na tabela. Num determinado momento, há uma modificação nos requisitos do sistema e o conjunto de dados passa a ter o dobro do tamanho original (M*2). Para manter o desempenho da tabela de hash em relação à recuperação de elementos, uma alternativa é dobrar também o tamanho da tabela de espalhamento (N*2). No caso de executar-se esta ação em tempo de execução (com os primeiros M dados já na tabela), seria necessário re-distribuir todos os elementos já inseridos ou não? Por quê?

R: O fator desempenho em uma tabela de distribuição está ligado diretamente à função e ao fator de carga aplicados na mesma. No caso é necessário criar outra tabela que suporte os grupos adicionais, possua outra função de distribuição e mantenha o mesmo fator de carga; para então redistribuir os dados da tabela antiga para a nova através do novo método de inserção; mantendo assim a fidelidade no gerenciamento dos dados.

6) Qual estrutura de dados você utilizaria para implementar um programa que, dado um texto qualquer, apresenta como resultado uma tabela contendo todas as palavras e o número de vezes que cada uma delas aparece. Apresente um algoritmo básico (máx 10 linhas) deste programa, considerando que existe uma função LerProximaPalavra (para que eu saiba como vocês resolveriam o problema) e explique o por quê de sua escolha, apresentando argumentos relacionados à eficiência da estrutura escolhida nas operações necessárias para este programa. Exemplo de resultado deste programa: (3 pts)

Qual -1, estrutura - 2, de - 8, dados - 2, você - 2 ,....

R: