Listas, Pilhas e Filas
As estruturas de dados dinâmicas mais simples em programação são as Listas. Essas estruturas são utilizadas quando a quantidade de elementos armazenados na estrutura não é previamente conhecida.
Por exemplo, podemos pensar numa biblioteca que irá cadastrar seus livros. A principio, seria possível utilizar um simples vetor de livros, ilustrado na Figura 1, para realizar essa tarefa.
Figura 1. Vetor de livros
Existem três problemas principais nessa solução:
Até que o vetor seja totalmente preenchido, haverá desperdício de memória.
Quando o vetor é totalmente preenchido nenhum novo livro poderá ser cadastrado.
Caso algum livro seja excluído esse vetor possuirá espaços vazios.
Para solucionar esse problema, podemos criar uma lista dinâmica. Nesse caso, a lista de livros poderá crescer e diminuir durante a execução do programa. Retomando o exemplo do livro, imagine que cada livro cadastrado utilize 1 Kbyte de memória dinâmica (não sabe o que é memória dinâmica?) e que há um vetor de seis posições. A Figura 2 ilustra a diferença no uso de memória entre uma implementação de lista usando um vetor estático e uma lista dinâmica.
Figura 2. Vetor estático Vs. uma lista dinâmica
Para implementação de uma lista dinâmica, cada nó é alocado na memória dinâmica e possui um ponteiro para o próximo elemento da lista. Além disso, essa implementação deve possuir um conjunto básico de métodos:
Inserir nó: esse método deve alocar uma área em memória para o novo nó e apontar o ponteiro do último nó para esse novo nó.
Encontrar nó: em listas simples, esse método deverá percorrer a lista inteira no pior caso.
Excluir nó: utiliza o método anterior e libera a memória correspondente. Além disso, deve
Tradicionalmente, listas dinâmicas são implementadas através de estruturas (não sabe o que é estrutura?) ou registros (não sabe o que é registro?) armazenadas na memória dinâmica. A estrutura que implementa um nó de uma lista deve incluir, além do conteúdo da informação do nó, um ponteiro para o próximo nó. Tipicamente, a definição da estrutura é da forma:
Listagem 1. Código em C
typedef struct noh {
struct noh* proximo;
} noh;
Listagem 2. Código em Pascal
Type noh=record
noh: proximo;
end
Cada nó de um lista é de memória dinâmica através de suas rotinas de alocação dinâmica de memória, que estão presentes na biblioteca padrão da linguagem. Há duas atividades básicas relacionadas à manipulação desta área:
Requisitar uma área de memória dentro do espaço livre disponível
Liberar uma área de memória
Em C, a alocação de memória é suportada pela rotina malloc (não conhece malloc?). Esta rotina recebe como argumento a quantidade em bytes que deverá ser alocada. Por isso utilizamos também a função sizeof que irá retornar o número de bytes ocupados por um tipo. O valor de retorno do malloc é o endereço do início da área que o sistema operacional alocou. Por exemplo, para reservar o espaço necessário para o nó de uma lista, seria necessário ter inicialmente declarado a variável que receberá o ponteiro para um nó:
noh *area;
area = malloc(sizeof(struct noh));
Para liberar uma área alocada por malloc, a rotina free deve ser utilizada. Assim, o exemplo acima poderia ser complementado da seguinte forma:
free(area);
Em Pascal, vamos utilizar a função new (não conhece a função new?), que aloca um espaço em memória para a variável recebida como argumento. A função para liberação de memória em Pascal é a função dispose.
var area : noh;
new(area);
dispose(area);
Filas e pilhas são estruturas usualmente implementadas através de listas, adicionando regras ao métodos de manipulação dos nós dessa lista.
Uma fila (queue) tipicamente estabelece uma política FIFO -- first in, first out -- de acesso aos dados. Em outras palavras, a ordem estabelecida na lista é a ordem de inserção. No momento de retirar um nó da lista, o nó mais antigo (o primeiro que entrou) é o primeiro a ser retirado.
Uma pilha (stack), por outro lado, estabelece uma política LIFO -- last in, first out. Uma estrutura de pilha também oferece basicamente duas operações de manipulação, PUSH, para inserção no topo da pilha, e POP, para retirada do topo da pilha.
Exercícios
- Crie uma lista para armazenamento de alunos de uma faculdade.
Implemente uma função que tenha como valor de retorno o comprimento de uma lista, isto é, calcule o número de nós da lista.
Escreva um algoritmo que inverta a ordem dos elementos dessa lista.
Escreva uma função que receba uma lista encadeada terminada em NULL e devolva a soma das chaves dos nodes da lista. Escreva duas versões: uma iterativa e uma recursiva.
Transforme essa lista em uma fila.
Transforme essa lista em uma pilha.
Escreva uma função que construa um vetor inteiro com o mesmo "conteúdo" de uma lista encadeada dada: o primeiro elemento do vetor deve ter o mesmo valor que o item do primeiro nó, o segundo elemento do vetor deve ter o mesmo valor que o item do segundo nó etc. Planeje com cuidado a "entrada" e a "saída" da sua função.
