Conceitos e operações em listas lineares genéricas

Consideraremos, para fins didáticos, que as listas lineares estão implementadas através de alocação sequencial em vetores de tamanho ilimitado. Posteriormente, quando aprofundarmos o estudo, trataremos os casos reais de listas alocadas sequencialmente.

Listas lineares são estruturas de dados não primitivas, usadas para reunir um conjunto de elementos que guardam relação entre si.

Uma lista linear pode armazenar tipos de dados complexos, isto é, cada nó pode ter campos que armazenam elementos com características distintas. Pode-se designar um desses campos como sendo a chave de busca da lista, o qual é utilizado para indexar os nós e é chamado de “chave”.

As listas apresentam casos particulares, chamados de deque, pilha e fila. Tais casos se diferenciam pela forma como as operações de inserção e remoção podem ocorrer na lista. Mas antes de estudarmos esses casos, vamos compreender o funcionamento das operações de inserção, remoção e busca para o caso geral.

Observe os pseudocódigos a seguir, nos quais a lista é representada por “Lista” e possui “n” posições ocupadas.

Algoritmo 1: Busca

                    
1: int buscar ( chave )
2: 	se n > 0
3: 		para i = 1 até i <= n
4: 			se Lista [ i ].chave == chave
6: 			retornar i
7: 	retornar n + 1

                

Repare que no caso da busca (Algoritmo 1) de um elemento da lista, esta é percorrida a partir do início até que o elemento seja encontrado ou o fim da lista seja atingido. O pior caso da busca se dá quando o elemento ocupa a última posição da lista ou não está na lista, o que obriga a se percorrer toda a lista.

Algoritmo 2: Inserção

                    
1: int inserir ( novo_elemento )
2: 	se busca ( novo_elemento.chave ) == n + 1
3: 		Lista [ n + 1 ] == novo_elemento
4: 		n = n + 1
5: 		retornar 1
6: 	senão retornar -1

                

A inserção (Algoritmo 2) precisa, antes de mais nada, verificar se o elemento a ser inserido já se encontra na lista (lembre-se de que as chaves são únicas e distintas). Nesse caso, se o valor retornado da busca for maior que o número de elementos (n) da lista, isso quer dizer que o novo elemento pode ser inserido. Como não se trata de uma lista ordenada, o novo elemento será inserido após a última posição ocupada. Note que se trata de um caso simples, uma vez que a não ocorrência do elemento permite sempre o inserir após a última posição ocupada.

Algoritmo 3: Remoção

                    
						1:	int remover ( chave )
						2:		se n > 0
						3:			int i = busca ( chave )
						4:			se i < n + 1
						5:				para a = i até a < n
						6:					Lista [ i ] = Lista [ i + 1 ]
						7:					n = n -1
						8:			senão retornar -1
						9:		senão retornar “Erro: lista vazia”

                

O algoritmo de remoção (Algoritmo 3) também precisa realizar a busca inicialmente, uma vez que remover um elemento inexistente irá gerar erro. Se esse elemento for encontrado, basta sobrescrever a sua posição com o elemento da posição seguinte e, assim, sucessivamente, até o fim da lista. Talvez lhe pareça um pouco mais difícil apontar a complexidade de pior caso, mas isso é apenas aparente. Na verdade, se você considerar que, seja qual for a posição do elemento a ser removido, todos os elementos posteriores serão manipulados, você perceberá que esse algoritmo sempre opera sobre todos os elementos da lista: Até encontrar, compara; depois de encontrado, copia.

Quando o espaço necessário para guardar os vetores é alocado antecipadamente (o cálculo prévio da quantidade de memória é trivial, como vimos), a alocação é chamada estática. Nesse caso, a quantidade de memória não pode ser alterada em tempo de execução. Isso explica, por exemplo, porque nosso Algoritmo 3 desloca uma posição para a esquerda todos os elementos à direita do que foi removido, ao invés de simplesmente desalocar o elemento a ser removido.

Além disso, na prática, a inserção precisaria verificar se o tamanho do vetor seria ultrapassado com a inserção de um elemento, o que geraria um erro de “overflow”.

Contudo, é possível realizar alocação sequencial de memória com o tamanho definido em tempo de execução. Esse tipo de alocação é chamado de dinâmica e faz uso, em linguagem C, de instruções de reserva de memória como a malloc e outras do tipo. Observe o trecho de código a seguir:

Código 2: Alocação dinâmica

A função malloc solicita ao sistema operacional que reserve, em tempo de execução, uma área contígua de memória igual à “tamanho_vetor” * o tamanho do tipo inteiro.

Como na linguagem C o nome do vetor é um ponteiro para o endereço base desse vetor e os índices são offsets (deslocamentos) a partir desse endereço base, a instrução “vetor [ n ]” tem o mesmo comportamento que no exemplo 1. Isto é, “n” significa o deslocamento a partir do endereço apontado por “vetor”.

Olhemos agora o caso de uma lista ordenada e vejamos qual proveito podemos tirar disso. Obviamente, todos esses algoritmos podem ser aplicados, pois foram pensados para casos gerais. Mas a lista ordenada nos oferece uma vantagem.

Olhemos agora mais um caso particular de listas, as chamadas double ended queue ou “deque”. Nessas listas, as inserções e remoções somente são permitidas nas extremidades. Não há um início e um fim propriamente ditos, pois as inserções podem ocorrer antes da extremidade esquerda e/ou após a extremidade direita. Isso vale para a remoção.

Vimos anteriormente que na alocação sequencial não temos como desalocar o espaço de memória do elemento removido. A solução para isso seria mover todos os elementos à sua direita de forma a sobrescrevê-lo e registrar o encurtamento da lista. Mas isso é um caso geral que comporta remoções internas. Na verdade, se limitamos a remoção às extremidades, esse problema se torna consideravelmente mais simples.

Considere o vetor v = [ a, b, r, t, c, p]. Trata-se claramente de uma lista não ordenada com 6 elementos. Sendo “v” um deque, os únicos elementos que podem ser removidos são o “a” e o “p”.

Vamos usar duas variáveis auxiliares, “aux_esq” e “aux_dir” que registram as posições extremas ocupadas, respectivamente, à esquerda e à direita. No caso, aux_esq = 0 e aux_dir = 5. Para remover “a”, tudo que precisamos fazer é incrementar aux_esq, que passará a valer 1. Dessa forma, a posição 0 é considerada disponível.

Mas essa limitação não é o único problema. Voltemos ao nosso exemplo. Suponha que tenham sido removidos “a” e “b” e se deseje inserir “u” à direita. Essa inserção viola o limite do vetor, gerando overflow, mas na verdade há espaço disponível para tal inserção.

O problema é que como esse espaço está antes da extremidade esquerda, ele não pode ser utilizado, o que acaba desperdiçando memória. Uma forma elegante de se contornar essa limitação é utilizar-se uma lista circular.

Uma lista circular é uma lista na qual as extremidades direita e esquerda estão ligadas. Assim, ultrapassar o limite superior direito, leva à extremidade esquerda, enquanto ultrapassar o limite inferior esquerdo, leva à extremidade direita.

Colocando de outra forma, ao movermo-nos para a esquerda em nosso vetor exemplo “v”, antes da posição 0, estaria a posição 5. Ao movermo-nos para a direita, após a posição 5, está a posição 0. É óbvio que esse não é o comportamento de um vetor, mas tal comportamento pode ser codificado nos algoritmos de remoção e inserção, de forma que a lista se comporte como a lista circular teórica.

Você também não deve confundir esse artifício, que visa ao uso eficiente de memória, com o aumento da capacidade de um vetor. Usemos listas circulares ou não, o número máximo de elementos que um vetor comporta é igual ao número de posições contíguas de memória alocadas.

Como dissemos anteriormente, o uso de alocação sequencial é uma forma de se implementar listas. Conforme mostramos, há vantagens e desvantagens que devem ser pesadas antes da decisão de qual mecanismo utilizar. Na seção seguinte, compreenderemos outro mecanismo de alocação, chamado de alocação encadeada.

Listas lineares dinamicamente encadeadas

Para compreendermos as vantagens de se utilizar a alocação encadeada, convém primeiramente olharmos mais detidamente para a manipulação de memória em um computador.

Ao longo do tempo, devido à execução de múltiplos programas, alocações e desalocações de memória vão deixando espaços com tamanhos distintos disponíveis. Esse problema é chamado de fragmentação de memória e vai tornando cada vez mais difícil alocar posições contíguas de memória na heap.

Listas encadeadas

A primeira coisa que iremos ver é como inserimos um elemento numa lista vazia.

Como dissemos antes, precisamos ter uma referência para a lista. Essa referência é um ponteiro que guardará o endereço do nó cabeça. Logo, para saber se uma lista é vazia, é suficiente testar se o campo “prox” do nó cabeça é nulo.

Se for, a inserção do novo elemento é simples. Basta alocá-lo na memória e fazer o nó cabeça apontar para ele. Apontar significa fazer o campo “prox”, um ponteiro, guardar o endereço de memória do elemento que se quer apontar.

Mas, para reservar esse espaço, a função precisa saber o tipo de dado que será armazenado. Bom, os nós guardam os elementos da lista. Mesmo que esses elementos sejam tipos primitivos, nós precisamos que os nós também possuam um campo ponteiro (ou dois, se for uma lista duplamente ligada) para guardar o endereço do próximo elemento (e do anterior, nas listas com dupla ligação). Assim, um nó da lista é um tipo de dado não primitivo.

Para definir um nó em linguagem C, usaremos a função struct, como pode ser visto no Algoritmo 4. Um nó de uma lista duplamente encadeada teria mais um campo ‒ No *ant –, a fim de guardar o endereço do nó anterior.

Algoritmo 4: Definição genérica de um nó de uma lista simplesmente encadeada.

                    
1	struct No {
2		< tipo > campo1;
3		< tipo > campo2;
4		[...]
5		< tipo > campoN;
6	No *prox; }

                

Repare que definimos uma estrutura chamada “No”, que contém N+1 campos. A instrução struct é usada em linguagem C para instruir o compilador de que os elementos que compõem a estrutura devem ser alocados sequencialmente. Ela define um tipo de dado não primário.

Para nossa discussão, vamos nos concentrar no ponteiro “prox” e por isso vamos usar uma estrutura de nó simples (Código 4), contendo um campo “prox”, do tipo ponteiro; um campo “chave”, do tipo inteiro; e outro campo que é na verdade outra estrutura chamada “Elemento” e cuja definição não faremos. Na prática, “Elemento” poderia estar definida dentro de “No” e a construção dessa forma tem apenas fins didáticos.

Código 4: Definição simples de um nó de lista simplesmente encadeada.

                    
1	struct No {
2		int chave;
3		Elemento elemento;
4		No *prox; }

                

Agora que definimos um tipo de dado útil para construir nossa lista, podemos retomar nossa abordagem de construção da lista.

Portanto, a busca consiste em, partindo-se do nó cabeça, percorrer toda a lista comparando-se as chaves dos nós. Numa lista não ordenada, essa comparação precisa prosseguir até o fim. O fim da lista é encontrado quando o ponteiro “prox” de um nó tem valor nulo, indicando que não há outros nós encadeados.

Já numa lista ordenada, essa busca pode cessar quando a chave do nó comparado for maior do que a buscada ou quando o fim da lista for atingido. Em ambos os casos, porém, o pior caso será quando toda a lista precisa ser verificada. O Código 5 mostra a implementação em linguagem C de uma função de busca em uma lista ordenada.

Código 5: Busca em lista encadeada ordenada

                    
1	No *buscar ( No *no_cabeca , No **aux, int chave ) {
2		No *atual = no_cabeca -> prox;
3		*aux = no_cabeca;
4		while ( atual != NULL ) {
5			if ( atual -> chave < chave ) {
6				*aux = atual;
7				atual = atual -> prox; }
8			else if ( atual -> chave == chave ) {
9				return atual; } //elemento encontrado
10			else
11				return NULL; } //elemento não encontrado
12		return NULL; } //lista vazia
13	}

                

O motivo de termos analisado a busca na lista encadeada ordenada é que este caso particular exibe um comportamento ligeiramente mais complexo. Em uma busca em uma lista não ordenada, a busca necessariamente precisa prosseguir até encontrar o elemento ou o fim da lista. Nesse caso, o procedimento é mais simples, não sendo necessário o teste mostrado na linha 5.

Essa diferença, todavia, não ocorre com os procedimentos de inserção ou remoção. Nesses procedimentos, as operações são as mesmas, embora as listas ordenada e não ordenada guardem diferenças.

Isso é possível uma vez que listas não ordenadas admitem, fora casos particulares de pilhas, filas e deques, a inserção de um elemento em qualquer posição.

Olhemos como a inserção ocorre no Código 6.

Código 6: Inserção em lista encadeada

                    
1	int inserir ( No *no_ant , Elemento novo_elemento , int chave ) {
2		No *aux , *anterior = no_cabeca;
3		No *novo_no = ( No * ) calloc ( 1 , sizeof ( No ) );
4		aux = buscar ( no_cabeca , &anterior , chave );
5		if ( ( novo_no == NULL ) || ( aux != NULL ) )
6			return 0; //falha na inserção
7		else {
8			novo_no -> elemento = novo_elemento;
9			novo_no -> chave = chave;
10			novo_no -> prox = anterior -> prox;
11			anterior -> prox = novo_no;
12			return 1; //inserção bem sucedida }
13		}

                

Agora, observe as linhas 8 a 11 do código mostrado. É nelas que a inserção ocorre.

A remoção é igualmente simples. No caso das listas encadeadas, não precisamos sobrescrever o elemento removido com o posterior, pois esse pode ser efetivamente desalocado.

Assim, a remoção consiste em duas ações básicas: Fazer o nó anterior ao nó que será removido apontar para o nó posterior deste e desalocar o nó removido, o que na linguagem C é feito pela instrução free.

Vejamos o Código 7, que implementa a remoção de um nó em uma lista encadeada.

Código 7: Remoção em lista encadeada.

                    
1	remover ( No *no_cabeca , int chave ) {
2		No *aux , *anterior = no_cabeca;
3		aux = buscar ( no_cabeca , &anterior , chave );
4		if ( aux != NULL ) {
5			anterior -> prox = aux -> prox;
6f			ree ( aux );
7			return 1; //remoção bem sucedida
8		} else
9			return 0; //falha remoção
10		}

                

Essas operações se aplicam à lista simplesmente encadeada. Mas, como vimos antes, podemos construir listas com duplo encadeamento. Para isso, a estrutura do nó mostrado no Código 4 precisa ser modificada para incluir mais um campo do tipo ponteiro, que será usado para apontar para o nó predecessor, conforme observamos no Código 8 (campo “ant”).

Código 8: Definição de um nó para lista duplamente encadeada.

                    
1	struct No {
2		int chave;
3		Elemento elemento;
4		No *prox;
5		No *ant; }

                

Obviamente os procedimentos de inserção e remoção precisam ser adequados. Uma lista duplamente encadeada torna desnecessário manter um ponteiro para o antecessor do nó buscado e exige mais operações na inserção e na remoção.

O procedimento de busca (Código 5) funciona mesmo em listas duplamente encadeadas, mas para estas, ele pode ser simplificado. Mas a existência de um duplo encadeamento não altera a complexidade das operações de inserção, busca e remoção.

Da mesma maneira que na alocação sequencial, podemos transformar uma lista encadeada em circular de forma simples. Basta que o último nó da lista passe a apontar para o nó cabeça. Isso significa fazer o campo “prox” do último nó apontar para o nó cabeça.

Para permitir que o percurso numa lista circular se dê em dois sentidos, faz-se necessário usarmos uma lista duplamente encadeada. Com uma lista desse tipo, para que ela se torne circular, além de fazermos o último nó apontar para o nó cabeça, precisamos fazer o campo “ant” do nó cabeça apontar para o último nó da lista.

Tipo de lista: Pilha

Veremos agora um tipo particular de lista chamada pilha. Uma pilha é um tipo de lista na qual as operações de inserção, remoção e acesso ocorrem sempre numa mesma extremidade, chamada de topo.

Uma pilha segue a regra “O último a chegar é o primeiro a sair”, também conhecida pela sigla LIFO, do inglês Last In, First Out. Colocando de outra maneira, a remoção ocorre na ordem inversa da inserção. Devido à essa característica, pilhas têm a propriedade de inverter sequências.

Pilhas possuem diversas aplicações em informática. A característica de inversão de cadeias tem grande utilidade, permitindo funcionalidades que facilitam o cotidiano, como a funcionalidade de desfazer ações existentes em diversos programas, por exemplo. Cada ação realizada no programa, é inserida na pilha. Quando acionamos a função de desfazer, as ações são desfeitas na ordem inversa em que ocorreram, isto é, da mais recente para a mais antiga. Isso é feito desempilhando as ações a serem revertidas.

Outro importante exemplo de uso de pilhas está relacionado diretamente com a execução de programas computacionais.

Outros casos, como a conversão para número binário, podem ser identificados, mas os exemplos dados devem ser suficientes para mostrar-lhe a importância dessa estrutura de dados.

Em nosso exemplo, utilizamos uma representação genérica de pilha. Mas não se esqueça de que se trata de um tipo particular de lista. Ou seja, da mesma maneira que as listas, podemos implementar a pilha através de alocação sequencial ou encadeada, com diferentes vantagens e desvantagens. Nas próximas subseções, nós veremos essas possibilidades mais detidamente.

Pilhas em alocação sequencial

Uma limitação que você já deve estar imaginando é que pilhas implementadas através de alocação sequencial estão sujeitas à restrição de memória correspondente ao tamanho do vetor definido.

Apesar disso, operacionalizar uma pilha com alocação sequencial é simples. A operação de inserção (empilhamento) sempre ocorre na extremidade, assim como a remoção (desempilhamento). Mais ainda, ambas ocorrem na mesma extremidade. Com isso, não temos a sobrecarga de mover os demais elementos do vetor, como seria se fosse possível fazer tais operações no interior.

Semelhantemente à lista genérica alocada sequencialmente, o desempilhamento não desaloca de fato a memória. O que é feito, nesse caso, é um controle de qual posição do vetor representa o topo. As posições do início até o topo são consideradas ocupadas. As posições maiores que o topo até o limite do vetor, são posições disponíveis, que podem receber elementos.

Portanto, empilhar significa incrementar o topo, e desempilhar, decrementá-lo.

A Figura 5 ilustra essas operações para um vetor genérico.

Vamos verificar, primeiramente, como se processa a operação de empilhamento em uma pilha vazia.

Para pilhas implementadas por meio de vetores, o topo será controlado por uma variável do tipo inteiro chamada de “topo”. A finalidade dessa variável é guardar o índice do vetor que corresponde ao topo da pilha.

Antes de inserirmos um elemento na pilha, precisamos verificar se há posições desocupadas no vetor. Isso é feito comparando-se o valor de “topo” com o tamanho do vetor, o qual é conhecido a priori.

Caso haja espaço, a variável “topo” deve ser incrementada e o novo elemento inserido no novo topo. Esse procedimento pode ser visto no Código 9. Nesse código, MAX_PILHA é o tamanho do vetor que implementa a pilha. A falha ocorrerá se for tentado o empilhamento de um elemento em uma pilha cheia.

Código 9: Função de empilhamento.

                    
1 int push ( Elemento elemento ) {
2 	if ( topo < ( MAX_PILHA – 1 ) ) {
3 		topo++;
4 		pilha [ topo ] = elemento;
5 		return 1; //sucesso
6 	} else
7 		return 0; //falha
8 }

                

O desempilhamento é igualmente uma operação simples. Antes de se remover um elemento da pilha, é preciso verificar-se se ela está vazia. Dessa maneira, se o valor da variável “topo” for maior ou igual a zero, o desempilhamento pode ocorrer. Caso contrário, ele deve ser impedido para se evitar o underflow.

Antes de desempilhar o elemento do topo, esse é acumulado em uma variável temporária para que seu valor possa ser recuperado. Em seguida, basta decrementarmos a variável “topo”, indicando que a posição passou a estar disponível para escrita. Observe a implementação do Código 10.

Código 10: Função de desempilhamento.

                    
1 Elemento pop ( void ) {
2 	Elemento valor_recuperado;
3 	if ( topo >= 0 ) {
4 		valor_recuperado = pilha [ topo ];
5 		topo--;
6 		return valor_recuperado;
7 	} else
8 		return NULL; //falha
9 }

                

Voltando ao nosso exemplo do empilhamento dos elementos a, b, c, d, e.

Antes do primeiro empilhamento, “topo” teria valor -1. Vamos agora considerar que nosso vetor tem 3 posições, isto é, os índices variam de 0 a 2.

A primeira chamada push ( a ), incrementará o valor de “topo” e colocará o elemento “a” na posição 0 (zero) do vetor.

A execução subsequente de push ( b ) e push ( c ), fará com que “topo” tenha valor 2.

Logo, a execução em seguida de push ( d ), será desviada na linha 2 do Código 9, pois topo (2) é igual ao valor da expressão MAX_PILHA (3) – 1.

Entretanto, se executarmos a função pop ( ), “c” será removido da pilha, e o valor de “topo” será decrescido para 1.

Após isso, push ( d ) conseguiria empilhar “d”, tornando a pilha novamente cheia.

Vamos considerar agora o desempilhamento. A execução de pop ( ), irá desempilhar “d”, decrementando “topo”.

A sequência pop ( ), pop ( ) esvaziará completamente a pilha, de forma que a tentativa de se executar uma quarta vez seguida a função pop ( ) não será possível. Na quarta execução, “topo” valerá -1, desviando a execução na linha 3 do Código 10.

Pilhas em alocação dinâmica

No caso de pilhas em alocação encadeada, a situação é diferente. O desempilhamento em uma pilha vazia ainda precisa ser prevenido, contudo, como o limite para empilhamento é a memória disponível, não há necessidade de se verificar a tentativa de empilhamento em uma pilha cheia.

Nesse caso, basta identificar-se quando não for possível uma nova alocação de memória para um novo elemento da pilha.

As operações são muito simples, por se tratar de um caso particular. Apesar de podermos usar listas duplamente encadeadas, a pilha é eficientemente implementada por listas simplesmente encadeadas, não se justificando o uso extra de memória. Também não utilizaremos o nó cabeça – nó especial, criado para facilitar as operações em lista – por ser desnecessário.

Para entendermos como uma pilha é implementada por uma lista de encadeamento simples, vamos começar considerando uma pilha vazia.

Como precisamos sempre saber quem é o topo, utilizaremos uma variável ponteiro chamada “topo”, cuja finalidade é apontar para o último elemento inserido na pilha.

Inicialmente, na pilha vazia, “topo” terá valor nulo.

A execução de uma operação de empilhamento - push ( ) ‒ envolve o recebimento do elemento a ser empilhado, seguido da alocação de um nó para acumular esse valor.

Uma vez que esse nó tenha sido criado, o seu campo “prox” deverá apontar para o mesmo endereço apontado por “topo”.

Sendo a primeira operação em uma pilha vazia, logicamente o campo “prox” desse nó terá valor nulo. Em seguida, o ponteiro “topo” precisa ser atualizado, passando a apontar para o novo nó empilhado.

É fácil notar que a repetição de operações push ( ) vai inserindo os nós na lista, sempre com o novo nó apontando para o último nó inserido.

Assim, a operação de desempilhamento - pop  ( ) - é trivial. Basta caminhar no sentido da lista. Ou seja, a cada operação pop ( ), o ponteiro “topo” passa a apontar para o campo “prox” do nó desempilhado e, após a recuperação do elemento armazenado no nó, este deve ser desalocado.

A operação pop ( ) no último elemento da pilha fará “topo” assumir valor nulo, indicando uma lista vazia. A Figura 6 ilustra a forma como essas operações se processam.

A função de empilhamento pode ser vista no Código 11.

Como estamos lidando com alocação encadeada, precisamos alocar a memória necessária sempre que vamos empilhar um elemento. Isso ocorre na linha 2.

A linha 3 verifica se a alocação foi bem sucedida, caso em que a execução segue para a linha 4. A não alocação pode indicar o esgotamento da memória, tornando inviável novos empilhamentos.

As linhas 4 a 6 são as que efetivamente executam o empilhamento. Na linha 4, o novo elemento é guardado na memória alocada. Em seguida, linha 5, o novo nó passa a apontar para o atual topo da pilha. A atualização do topo, passando a apontar para o nó inserido, se dá na linha 6.

Código 11: Função de empilhamento.

                    
1	int push ( Elemento elemento ) {
2		No *novo_no = ( No * ) calloc ( 1 , sizeof ( No ) );
3		if ( novo_no != NULL ) {
4			novo_no->elemento = elemento;
5			novo_no -> prox = topo;
6			topo = novo_no;
7			return 1; //sucesso
8		} else
9			return 0; //falha
10		}

                

O Código 12 mostra a função de desempilhamento.

Veja que utilizamos um ponteiro auxiliar (aux). O objetivo deste é permitir a desalocação do nó desempilhado.

Na linha 4, testamos para ver se a pilha é vazia, situação em que o desempilhamento geraria um underflow.

Caso não seja, o desempilhamento é possível e é executado pelas linhas 7 e 8. Em 7, o ponteiro topo é atualizado, passando a apontar para o nó seguinte ao que será desempilhado. A linha 8 realiza a liberação de memória do espaço previamente ocupado pelo nó removido.

O elemento guardado no nó desempilhado é acumulado em “elemento_recuperado”, sendo retornado pela função.

Código 12: Função de desempilhamento.

                    
1	int pop ( void ) {
2		No *aux;
3		Elemento elemento_recuperado;
4		if ( topo != NULL ) {
5			elemento_recuperado = topo->elemento;
6			aux = topo;
7			topo = topo->prox;
8			free ( aux );
9			return elemento_recuperado;
10		} else
11			return NULL;
12	}

                

Observe que, em ambos os casos, o número de passos executados é fixo.

Pilhas e expressões aritméticas binárias

A manipulação de expressões aritméticas é um tema importante, que requer uma forma adequada de se representar computacionalmente tais expressões.

Usualmente, expressões aritméticas possuem operadores, que representam as operações aritméticas, operandos, sobre os quais os operadores atuam, e delimitadores, utilizados para estabelecer a precedência das operações.

Tipo de lista: Fila

Uma fila é um tipo particular de lista mais elaborado do que a pilha. No caso de filas, as operações de inserção e remoção ocorrem em duas extremidades.

As inserções sempre ocorrem no final ou retaguarda da fila, enquanto as remoções são executadas na outra extremidade, denominada início.

As filas obedecem à regra “O primeiro a chegar é o primeiro a sair”, também chamada de FIFO, do inglês first in, first out. Por essa razão, precisamos de dois controles para a fila:

• Um para identificar o início da fila.
• Outro para marcar o seu término.

Isso decorre do fato de que as remoções ocorrem na mesma ordem que as inserções. Ilustremos essa situação.

Suponha que vamos enfileirar o conjunto de entrada a, b, c, d, e. Usaremos a mesma simbologia de pilhas, mas, nesse caso, o símbolo de “{“ representa o início da fila e o símbolo de “}” o seu final.

Inicialmente, a fila está vazia e as entradas são lidas na ordem em que aparecem. A Tabela 3 mostra o processamento das entradas pela fila. De maneira similar à pilha, a operação de enfileirar (enqueue) recebe como parâmetro o elemento a ser inserido na fila, mas a operação de desenfileirar (dequeue) não possui parâmetro.

Tabela 3: Processamento de uma cadeia através de uma fila.

Tabela 3. Fonte: O Autor.

Se você observar atentamente a tabela, notará que em nossa fila de exemplo as inserções ocorreram pela direita, fazendo a fila crescer nesse sentido. Já as remoções se deram pela esquerda, provocando o seu encurtamento.

A esquerda é o início da fila e a direita é o fim. Isso pode gerar um problema para filas em alocação sequencial, o que torna sua implementação nesse caso ligeiramente mais complexa. Vamos explorar isso na subseção que trata de filas alocadas sequencialmente, mas procure refletir desde já e tente identificar o problema.

Assim como a pilha, a fila tem ampla aplicação.

Outro exemplo do uso de filas, também se desconsiderando a existência de parâmetros que alterem a ordem de execução, é a implementação de uma fila de impressão. Nesse exemplo, múltiplos usuários podem enviar diversos arquivos para a impressão num mesmo equipamento. Esses arquivos, ao serem recebidos, são colocados numa fila e são impressos seguindo a ordem de chegada. Ou seja, o primeiro a ser recebido é o primeiro a ser impresso.

Há vários outros exemplos do uso de filas, mas estes devem ter mostrado sua relevância e utilidade. Vamos olhar, nas próximas subseções, os detalhes relativos à implementação de filas em alocação sequencial e em alocação encadeada.

Filas em alocação sequencial

Como vimos, a implementação de filas demanda o controle de duas posições, o início e o fim.

A posição final é aquela na qual ocorrem as inserções, e por isso, por onde a lista aumenta. A posição inicial é onde ocorrem as remoções, sendo por onde a fila é encurtada. Isso acarreta um problema para a alocação sequencial.

Imagine uma fila implementada através de um vetor com N posições. Inicialmente, a fila está vazia. Após a chegada do primeiro elemento, a primeira posição do vetor é ocupada. Com a chegada de um segundo elemento, ocupa-se a segunda posição. Suponha que, nesse momento, um elemento seja retirado da fila. Nesse caso, o início da fila, que era a primeira posição, torna-se a segunda posição (a primeira agora está desocupada).

Mesmo se as inserções forem superadas pelas remoções, é possível afirmar-se que, com certeza, a posição inicial se deslocará em direção à retaguarda. Assim, duas situações podem ocorrer:

• Novas inserções podem ser impedidas, devido ao fim da fila atingir o fim do vetor.
• O desperdício de memória relativo aos espaços desocupados antes do início.

Uma possível solução para essa questão seria deslocar todos os elementos da fila uma posição em direção ao início, sempre que houver uma remoção. Dessa forma, o início da fila seria sempre mantido na primeira posição do vetor e, de fato, quando uma inserção não fosse possível seria devido ao vetor estar preenchido.

Outra abordagem possível é implementar a fila através de uma lista circular. Nesse caso, o vetor comporta-se como se após a última posição, estivesse a primeira. Ou seja, uma vez que o fim da fila atinja o fim do vetor, uma nova inserção será possível se a primeira posição estiver livre.

Filas em alocação dinâmica

Vejamos agora o caso de fila implementada em alocação encadeada.

Relembrando o comportamento das filas, notamos que não precisamos percorrer a lista para executar as operações de inserção ou remoção. Uma vez que estas sempre ocorrem nas extremidades, basta mantermos uma referência para essas posições, da mesma maneira que no caso de alocação sequencial.

Isso nos remete à mesma situação da pilha, cuja implementação através de lista simplesmente encadeada mostra-se suficiente e vantajosa. O mesmo ocorre no caso das filas. Embora possamos implementá-las através de uma lista duplamente encadeada, não há vantagem que justifique o gasto extra de memória. Logo, nossa fila será implementada através de uma lista simplesmente encadeada, sem nó cabeça.

Usemos o ponteiro “inicio” para referenciar o início da fila e o ponteiro “fim” para o seu final. Incialmente, vamos definir que a lista vazia será caracterizada por inicio = fim = NULL. O comportamento de filas em alocação encadeada guarda alguma similaridade com o caso de alocação sequencial. As diferenças ficam por conta das duas situações apresentadas no primeiro parágrafo da subseção anterior.

• Novas inserções podem ser impedidas, devido ao fim da fila atingir o fim do vetor.
• O desperdício de memória relativo aos espaços desocupados antes do início.

Consideremos, por exemplo, a situação quando o primeiro elemento for inserido numa fila vazia. Após a inserção, teremos que ambas as variáveis (“inicio” e “fim”) apontarão para o mesmo endereço de memória. Esse endereço será o correspondente ao espaço de memória alocado para o elemento inserido.

Se novas inserções ocorrerem, a variável “inicio” manter-se-á apontando para o primeiro elemento inserido, e a variável “fim” passará a apontar para o novo nó criado.

A remoção, por sua vez, provocará a desalocação do nó apontado por “inicio”, forçando com que a variável passe a apontar para o nó seguinte. A remoção do único elemento na fila, situação em que inicio = fim, torna novamente inicio = fim = NULL.

Na prática, o crescimento é limitado pela memória disponível, mesmo assim, isso não se constitui em óbice significativo normalmente. Por essas razões, também não há necessidade de fazermos uma implementação circular e podemos manter o campo “prox” do último elemento sempre com o valor NULL.

Vamos verificar mais detalhadamente como ocorrem a inserção e a remoção. Quando a função “enfileirar” é chamada, ela recebe como parâmetro o novo elemento a ser inserido. Antes que ele possa ser colocado na fila, precisamos alocar o espaço de memória e guardar o endereço correspondente.

A fila será formada por uma lista de nós com apenas dois campos:

• Elemento – Que guarda o elemento a ser inserido na lista.
• Prox ‒ Que guarda o endereço do próximo nó.

Ao ser criado o nó, devemos fazer “prox” assumir valor nulo. Esse campo só se alterará quando um novo nó for inserido em seguida, caso em que “prox” guardará o valor do endereço desse nó. O nó criado será inserido quando o campo “prox” do nó anterior apontar para ele e o ponteiro “fim” for atualizado com o endereço do nó inserido.

A remoção é ainda mais simples. Basta fazer o ponteiro “inicio” avançar na fila, isto é, inicio = inicio -> prox. Em seguida, desalocamos o nó removido. O Código 15 mostra o enfileiramento e o Código 16 o desenfileiramento.

Código 15: Função enfileirar.

                    
1	int enfileirar ( Elemento elemento ) {
2		No *novo_no = ( No * ) calloc ( 1 , sizeof ( No ) );
3		novo_no -> elemento = elemento;
4		novo_no -> prox = NULL;
5		if ( novo_no != NULL ) {
6			if ( fim != NULL )
7				fim->prox = novo_no;
8			else {
9				inicio = novo_no;
10				fim = novo_no;
11				return 1; //sucesso
12			} else
13				return 0; //falha
14	}

                

Olhando o Código 15, percebemos que a linha 5 verifica se houve sucesso na alocação de um novo nó. Se esse nó tiver sido alocado com sucesso, o programa segue para a linha 6, que verifica se a fila é vazia (pelo que explicamos antes, basta testar um dos ponteiros de controle). Se a fila não for vazia, a linha 7 faz o nó apontado pelo ponteiro “fim” apontar para o novo nó e a linha 10 avança o fim da fila para o nó inserido.

Observe que a linha 10 é executada mesmo se a fila for vazia, caso em que a linha 9 também o é. Isso corresponde à situação que vimos de uma fila com um único nó.

Código 16: Função desenfileirar.

                    
1	Elemento desenfileirar ( void ) {
2		int elemento_recuperado;
3		No *aux = inicio;
4		if ( inicio != NULL ) {
5			inicio = inicio->prox;
6			if ( inicio == NULL )
7				fim = NULL;
8			elemento_recuperado = aux->elemento;
9			free ( aux );
10			return elemento_recuperado; //sucesso
11		} else
12			return NULL; //falha
13	}

                

A função desenfileirar, mostrada no Código 16, é igualmente simples. A linha 4 verifica se a fila é vazia, o que inviabiliza a remoção. Se houver algum elemento na fila, basta avançar-se o ponteiro de “inicio”, o que é feito na linha 5. A linha 6 verifica se a fila se tornou vazia. Se tiver se tornado, o ponteiro “fim” precisa ser ajustado como na linha 7. Finalmente, em 9, o espaço de memória é liberado. Para isso, um ponteiro auxiliar é utilizado.

Da mesma maneira que na alocação sequencial, as operações de inserção e remoção são executadas em um número constante de passos.

A essa altura, você deve ter compreendido que a limitação da execução de inserções e remoções em posições específicas é a responsável pela redução da complexidade, pois torna dispensável a busca nas listas.

Para encerrar, apresentaremos um algoritmo que se vale de filas para realizar a ordenação.

A ordenação é um problema frequentemente enfrentado em computação e o Algoritmo 5 mostrado em pseudocódigo realiza a ordenação de “n” chaves utilizando-se “m” filas, sendo as chaves números inteiros numa base “m” > 1. Ou seja, o número de filas usadas é igual à base usada na representação numérica das chaves. Isso significa que para ordenar chaves decimais, serão utilizadas 10 filas. Esse tipo de ordenação é chamado ordenação por distribuição. O processo todo é relativamente simples.

Para realizar a ordenação, a lista de entrada com as “n” chaves é percorrida. Nessa primeira passagem, é avaliado o dígito menos significativo. As filas auxiliares são F_i, com “i” variando de 0 até “m” – 1. Logo, para o caso decimal, temos que “i” varia de 0 até 9. Os dígitos menos significativos são comparados ao índice “i”. Quando forem iguais, a chave é inserida nessa fila.

Ao fim da passagem, as chaves estarão distribuídas pelas filas, segundo seu dígito menos significativo. Uma nova fila de entrada é, então, construída a partir da concatenação das filas, mantendo-se a ordem de seu índice. Isto é, F₀ – F₁ - ... – F₉.

Uma segunda passagem é feita, tendo como entrada essa nova fila, empregando-se o mesmo princípio, mas agora comparando-se o segundo dígito mais significativo. O algoritmo terminará após a concatenação da última fila, construída a partir da distribuição feita considerando-se o dígito mais significativo.

Algoritmo 5: Ordenação por distribuição.

                    
1	ordenacaoPorDistribuicao ( int m , int n , int Entrada [ ] )
2	int nr_digito = m - 1 , aux
3	int Fila [ nr_digito ]
4	para i = 0 até i < m - 1
5		para j = 0 até n - 1
6			aux = o i-ésimo digito menos significativo de Entrada [ j ]
7			Fila [ aux ] = Entrada [ j ]
8		j = 1
9	para aux = 0 até m - 1
10		enquanto Fila [ aux ] tiver elemento não processado
11			Entrada [ j ] = Fila [ aux ]
12			j++