domingo, 6 de março de 2011

Estruturas de Dados: Listas, Filas e Pilhas

Estrutura de dados é a forma como os dados podem ser dispostos de forma organizada para habilitar de uma forma formal acessá-los, alterá-los ou removê-los de forma eficiente.


O objetivo da estrutura de dados é dispor os dados de forma coerente para seu armazenamento ou acesso. A organização e os métodos que acessam e manipulam estes dados estruturados são chamados de algoritmos de estruturas de dados, como fila, lista, pilha, árvore, grafo, etc;


As estruturas de dados podem ser organizadas ou armazenadas utilizando de formas ou estruturas homogêneas e heterogêneas. As estruturas homogêneas são representadas por vetores e matrizes que tem como objetivo de armazenamento de dados de um tipo único, como inteiros ou strings. Neste caso, estas estruturas são utilizadas em situações onde somente um tipo de dados é suficiente para organização das informações, mas, isso não é o suficiente ou não atende a todos os cenários.


As estruturas de dados heterogêneas vem suprir a lacuna das estruturas homogêneas. As estruturas heterogêneas permitem a composição ou armazenamento de dados de diferentes tipos simultaneamente, como, inteiros, strings, float, double, etc.


Os vetores ou arrays são estruturas de dados chamadas de lineares e estáticas que permitem um número finito ou fixo de elementos de um determinado tipo em seu conteúdo. O acesso a este tipo de estrutura é muito rápido pois necessita de apenas seu índice para acessar qualquer item em sua estrutura. O ponto negativo deste tipo de estrutura é a remoção dos elementos, visto que na remoção, deixará um espaço "vazio" entre os elementos, sendo assim, deve haver um algoritmos que possa reorganizar os dados para deixá-los de forma organizada sem estes espaços.


Os arrays podem ser unidimensional, bidimensional ou ter mais dimensões se necessário. Porém, os uni ou bidimensionais são os mais utilizados. 


Essa estrutura é muito recomendada quando a quantidade de dados não se alteram durante seu armazenamento ou remoção ou mesmo através do tempo.


Exemplo: String[] S = new String[5];


Lista


Uma Lista é uma estrutura de dados linear. Podemos armazenar dados em uma estrutura homogênea, porém, como dito anteriormente pode haver uma limitação quanto a dados e quanto a manipulação destes dados.


Podemos utilizar uma estrutura heterogênea ligando os dados entre sí. Essa ligação pode ser direcional ou bidirecional. Basicamente uma lista ligada direcional ou bidirecional é composta por nós que apontam para o próximo ou anterior elemento da lista, com exceção do último, que não aponta para ninguém. Para compor uma lista encadeada, basta guardar seu primeiro elemento.


Numa lista encadeada existem dois ou três campos. Um campo reservado para colocar o dado a ser armazenado e os outros campos para apontar para o próximo ou anterior elemento da lista. Normalmente a implementação é feita com ponteiros.




Na linguagem C podemos exemplificar da seguinte forma:


struct lista {
  struct lista *ponteiroanterior;
  int valor;
  struct lista *ponteiroproximo;
}


Quando utilizamos uma lista em uma estrutura heterogênea, onde pode-se adicionar novos elementos quando necessário, faz desta estrutura de dados muito recomendada para casos onde a quantidade de informação é indeterminada e a ordem de armazenamento não é importante. Porém, esta estrutura permite de forma mais fácil de se aplicar algoritmos de ordenação que permitiria classificar os dados.


As listas são bastante utilizadas quando não há uma ordem para inserir ou remover os dados, podendo estes dados serem inseridos no início ou fim da lista ou mesmo entre os elementos já existentes.


Fila


As filas são estruturas baseadas no princípio FIFO (first in, first out) ou PEPS (primeiro a entrar, primeiro a sair), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: Enfilera, que adiciona um elemento ao final da fila, e Desinfilera, que remove o elemento no início da fila. A operação Desinfilera só pode ser aplicado se a fila não estiver vazia, portanto, há também outras funções como checar se a fila esta vazia e liberar a fila que também são utilizadas.


Uma Fila é recomendada para casos em que os dados armazenados possuem uma ordem onde o item mais velho da fila é o primeiro a ser removido.




Pilha


Uma pilha é um tipo de estrutura de dados baseado no princípio de LIFO (Last In First Out) ou UEPS (último a entrar, primeiro a sair) onde os elementos que foram inseridos por último serão os primeiros a serem removidos.


Pilhas são usadas em diversos sistemas e como exemplo muito próximo nosso são as alterações feitas por nós que são devidamente armazenadas em uma Pilha o que nos permite "Voltar" e desfazer cada ação nos aplicativos como Microsoft Word, Excel entre outros.


Uma Pilha é muito recomendada para casos em que os dados armazenados mais novos ou recentes devem ser removidos primeiros.


Tanto a Lista, Fila quanto a Pilha podem ser desenvolvidas ou programadas através de encadeamento dos dados utilizando de estruturas heterogêneas.

Referências:


6 comentários:

Nycollebr disse...

bem resumidinho e tbm fácil de entender. obg

Nycollebr disse...

bem resumidinho e tbm fácil de entender. obg

Ediee disse...

Muito boa explicação !!!!

Ediee disse...
Este comentário foi removido pelo autor.
Unknown disse...

Deveria ter mais exemplos praticos.
O conteudo por mim esta muito bom. Obrigado.

Lu disse...

Muito obrigado!