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

1. Crie uma lista para armazenamento de alunos de uma faculdade.

2. 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.

3. Escreva um algoritmo que inverta a ordem dos elementos dessa lista.

4. 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.

5. Transforme essa lista em uma fila.

6. Transforme essa lista em uma pilha.

7. 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.