Guia de Tipos Abstratos e Estruturas de Dados

Tipo Abstrato de Dados (TAD): define o conjunto de valores e as operações sobre os valores, mas não define sua implementação. Exemplos: lista, pilha, fila, árvore.

Estrutura de Dados (ED): é uma maneira particular de se implementar um Tipo Abstrato de Dados. Exemplos: sequencial, encadeado.

Lista

Lista: Conjunto de itens interligados cujas operações de inserção e remoção podem ser feitas em qualquer parte.

O conjunto mínimo de regras de negócio necessárias à funcionalidade de uma lista inclui:

• Inserir um item na lista
• Remover um item da lista
• Encontrar um item na lista
• Contar quantos itens pertencem à lista
• Descobrir qual item está em uma dada posição

Pilha

Pilha: Conjunto de itens interligados cujas operações de inserção e remoção só podem ser feitas no topo. Inserção e remoção são baseadas no princípio LIFO (last in, first out) ou, em português, UEPS (último a entrar, primeiro a sair).

Operações que se aplicam a todas as pilhas:

• Inserir um item no topo da pilha
• Remover um item do topo da pilha

Fila

Fila: Conjunto de itens interligados cuja operação de inserção é feita no final e a operação de remoção é feita no início.

Inserção e remoção são baseadas no princípio FIFO (first in, first out) ou, em português, PEPS (primeiro a entrar, primeiro a sair).

Operações que se aplicam a todas as filas:

• Inserir um item no final da fila
• Remover um item do início da fila

Estrutura Sequencial

• Os itens são armazenados em posições contíguas da memória;
• O tamanho da estrutura deve ser definido na sua criação;
• A estrutura pode ser percorrida em qualquer direção;
• Qualquer item pode ser acessado diretamente.

Pontos positivos: Facilidade de acesso a cada item; custo baixo e constante para inserção ao final dos itens ou remoção do último item.

Pontos negativos: Alto custo para inserir ou remover itens no meio, pois implica o deslocamento de outros itens. O tamanho fixo pode implicar a alocação de memória não utilizada ou falta de espaço.

Estrutura Encadeada

• Cada item é encadeado por um ponteiro que aponta para o item seguinte da estrutura;
• Permite armazenamento em posições não contíguas de memória;
• O acesso a um determinado item é feito passando por todos os itens que o precedem.

Pontos positivos: Não tem desperdício de memória, pois a memória alocada pela estrutura é aquela utilizada pelos itens. Custo baixo para inserção ou remoção de itens.

Ponto negativo: Custo alto para acessar um determinado item porque implica passar por todos os itens que o precedem na estrutura.