Estruturas de Dados Avançadas

Estruturas de Dados Avançadas

Dentre as principais estruturas de dados avançadas temos: pilhas, filas, listas e árvores. Estas estruturas armazenam dados e são manipuladas por funções básicas do tipo: cria, insere, elimina, consulta e altera.

As mesmas podem ser implementadas tanto da forma estática quanto da forma dinâmica.

Pilha

Uma pilha pode ser vista como um local onde são inserido dados um sobre o outro, sendo sempre inserido sobre o último da pilha (topo da pilha). Para retirarmos os dados, devemos também respeitar a ordem pelo qual eles foram inseridos, ou seja, retirando somente o último elemento do topo. Este tipo de estrutura é também conhecida como LIFO (“Last In First Out” = “Último a Entrar é o Primeiro a Sair”) ou

FILO (“First In Last Out” = “Primeiro a Entrar é o Último a Sair”).

As estruturas de pilha são comumente usadas em algoritmos de gerenciamento de memória (escopo de variáveis e retorno de procedimentos), compiladores e em outras aplicações.

Quando uma pilha é criada, não existe nenhum elemento inserido e dizemos que ela está vazia, podendo ser estática ou dinâmica.

Fila

É um tipo de lista linear em que a inserção é feita numa extremidade e a eliminação na outra. Conhecida como estrutura FIFO (First In ,First Out), podendo ser seqüencial ou encadeada.

Pelas suas características, as filas têm as eliminações feitas no seu início e as inserções feitas no seu final. A implementação encadeada dinâmica torna mais simples as operações (usando uma lista de duas cabeças). Já a implementação seqüencial é um pouco mais complexa (podendo ser utilizado o conceito de fila circular), onde pode ser usada quando há previsão do tamanho máximo da fila.

Exemplos: escalonamento de "Jobs": fila de processos aguardando os recursos do sistema operacional; fila de pacotes a serem transmitidos numa rede de comutação de pacotes; simulação - fila de caixa em banco.

Lista Circular

Lista é uma estrutura onde os dados são inseridos em qualquer posição, em função de uma política qualquer. Geralmente, os dados são inseridos por ordenação. Para eliminar um determinado elemento é necessário uma informação qualquer que especifique qual elemento deverá ser eliminado (nome, código, tipo, etc).

A lista circular é uma espécie de lista simples ou duplamente encadeada, com uma característica adicional para o deslocamento na lista, onde a mesma não tem fim.
Para tornar a lista interminável, o ponteiro seguinte do último elemento apontará para o primeiro elemento da lista, em vez do valor NULL. Nas listas circulares, nunca chegaremos a uma posição a partir da qual não poderemos mais nos mover. Chegando ao último elemento, o deslocamento vai recomeçar no primeiro elemento. Podendo ser compreendida como uma rotação.

Árvore

Diferentemente das estruturas anteriores onde a organização dos dados é realizada de forma linear, onde a propriedade básica é a relação seqüencial mantida entre seus elementos. A estrutura organizacional "não - linear" permite que outros tipos de relação entre dados possam ser representados, como por exemplo, hierarquia e composição. Sendo o exemplo mais significativo de estruturas não-lineares denominado  de árvore, cujos nodos contem dois links, podendo ou não serem nulos. O nodo raiz é o primeiro nodo em uma arvore. Onde cada link no nodo raiz referencia um filho. O filho esquerdo é o nodo raiz da subárvore esquerda e o filho direito é o nodo raiz da subárvore direita. Os filhos de um mesmo nodo são chamados de irmão. Um nodo sem filho é chamado de nodo folha.