Acrobat Distiller 4 0 for2010-11-09 17-19-46846

Prévia do material em texto

Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 1 
 
Estruturas lineares com disciplina de acesso 
Diversas aplicações envolvendo listas lineares requerem implementações que impõem limites 
para as operações de inclusão e remoção de elementos. Basicamente trata-se de situações em que 
a posição do novo elemento é pré-determinada, bem como o critério para determinar quem deve 
ser removido da lista. Tais estruturas são muitas vezes denominadas de estruturas lineares com 
disciplina de acesso, e existem dois tipos principais: 
• First In First Out (FIFO), os novos elementos são acrescentados no final da lista, e a 
exclusão ocorre na extremidade oposta. Assim, ao remover um elemento, selecionamos 
aquele que está a mais tempo na lista, o que foi incluído a mais tempo. Precisamos 
monitorar as duas extremidades da lista, pois na ponta inicial fazemos a exclusão e na 
final fazemos a inclusão. A analogia básica deste tipo de estrutura é uma fila de pessoas 
em que não há qualquer tipo de prioridade de atendimento, apenas a ordem de entrada 
das pessoas na fila. As extremidades costumam ser denominadas de início e final. 
 
 
 
 
Fig. 1: Uma fila com 5 pessoas. 
• Last In First Out (LIFO), os novos elementos são acrescentados na mesma extremidade 
de onde são removidos. Com isso, o elemento mais antigo na lista é o último a ser 
removido e o elemento mais recente na lista é o primeiro a ser removido. Dessa forma, 
para implementar uma estrutura LIFO precisamos monitorar apenas uma de suas 
extremidades. A analogia fundamental deste tipo de estrutura é a pilha de objetos, tais 
como pratos ou livros, e a extremidade sobre a qual devemos manter controle costuma ser 
chamada de topo. 
 
 
 
 
 
Fig. 2: Uma pilha com 5 pratos. 
Como qualquer lista linear, as estruturas LIFO (pilhas) e FIFO (filas) podem ser implementadas 
por encadeamento ou por contigüidade. Neste material será dada atenção apenas à 
implementação por encadeamento. A discussão da implementação desses dois tipos de estrutura 
será realizada por meio de uma lista encadeada simples de números inteiros, cujo tipo de dado 
dos elementos é dado na figura 3. Nos exemplos dados, optou-se por manter como descritor da 
lista também a quantidade de elementos da lista e, por simplicidade, não serão utilizadas 
subrotinas, para permitir melhor entendimento das operações básicas. Posteriormente, uma 
implementação equivalente utilizando subrotinas será apresentada. 
Início da fila Final da fila 
EntradaSaída 
Topo da pilha
SaídaEntrada
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 2 
 
 
 
 
 
 
Fig. 3: Definição do tipo de dados dos elementos da lista. 
Pilhas 
Como vimos anteriormente, o aspecto essencial da implementação de uma pilha (no inglês: 
stack) diz respeito à forma como são construídas as suas rotinas de inclusão (ou empilhamento, 
no inglês: push) e exclusão (ou desempilhamento, no inglês: pop) de elementos. Como 
precisamos monitorar apenas uma das extremidades da lista, o topo, a variável descritora da lista 
possui uma estrutura bastante simples, como mostra a figura 4. A inicialização do descritor 
consiste apenas em colocar um nulo em seu membro topo e um zero em seu membro qtde, 
como mostra a figura 5. 
 
struct descrPilha
{
TLista *topo;
int qtde;
};
 descritor.topo = NULL;
descritor.qtde = 0; 
typedef struct descrPilha DPilha;
(…)
DPilha descritor;
 Fig. 5: Inicialização do descritor da pilha. 
Fig. 4: Definição do tipo e da variável descritora da pilha. 
A rotina de inclusão consiste em alocar a memória para o novo elemento, preenchê-lo com o 
conteúdo útil correspondente e fazer com que seu elemento seguinte seja aquele que era o topo 
da pilha até aquele momento. Finalmente, o endereço de memória do novo elemento deve ser 
colocado como sendo o novo valor do topo no descritor e o contador de elementos precisa ser 
incrementado para refletir a nova quantidade de elementos da pilha. Tudo isso é realizado pelo 
código apresentado na figura 6. 
 
(...)
aux = (TLista *) malloc(sizeof( TLista ));
aux->valor = numero;
aux->prox = descritor.topo;
descritor.topo = aux;
descritor.qtde++;
(...)
Fig. 6: Inclusão de um elemento na pilha. 
A figura 7 apresenta a situação inicial de uma pilha com 3 elementos e a posterior inclusão de 
um novo nó por meio do código apresentado anteriormente. 
 
struct regLista
{
int valor;
struct regLista *prox;
};
typedef struct regLista TLista;
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fig. 7: Representação da pilha antes e depois da inclusão de um elemento. 
A rotina de exclusão vai, caso a pilha não esteja vazia, obter o endereço do elemento a ser 
excluído e copiá-lo para uma variável auxiliar. Em seguida, vai atualizar o descritor do topo e da 
quantidade e, por fim, eliminar a variável correspondente ao elemento indicado. O código da 
figura 8 realiza essa sequência de tarefas. 
 
(...)
if( descritor.topo != NULL )
{
aux = descritor.topo;
descritor.topo = descritor.topo->prox;
descritor.qtde--;
free(aux);
}
(...)
Fig. 8: Exclusão de um elemento da pilha. 
A figura 9 mostra a remoção de um elemento de uma pilha que contém originalmente 4 
elementos. 
A simplicidade da implementação da pilha independe de a lista linear ser ou não duplamente 
encadeada. Utilizamos pilhas em diversas situações práticas, como para gerenciar a execução das 
rotinas em um computador (isso é feito por meio da pilha de execução do sistema), implementar 
recursos de ‘desfazer’ (undo) em aplicações como editores, bancos de dados e jogos, e no 
gerenciamento dos links visitados em um browser de navegação na internet, em que podemos 
topo qtde
•••• 3
descritor
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
topo qtde
•••• 4
descritor
valor prox
5 ••••
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
Estado da pilha ANTES 
da inclusão 
Estado da pilha DEPOIS 
da inclusão 
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 4 
 
sempre retornar de uma página diretamente para a visitada anteriormente. Também é muito útil 
para o processamento de strings, seja reconhecendo palíndromos, invertendo palavras, 
verificando balanceamento de delimitadores e modificando a notação de expressões aritméticas. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fig. 9: Representação da pilha antes e depois da exclusão de um elemento. 
O programa apresentado a seguir implementa uma pilha básica de números inteiros em 
linguagem C. Para testá-lo, adapte-o para imprimir o conteúdo da pilha antes e após a exclusão. 
#include <stdio.h>
struct regLista
{ int valor;
struct regLista *prox;
};
typedef struct regLista TLista;
struct descrPilha
{ TLista *topo;
int qtde;
};
typedef struct descrPilha DPilha;
int main()
{ int numero;
DPilha descritor;
TLista *aux;
descritor.topo = NULL;
descritor.qtde = 0;
topo qtde
•••• 3
descritor
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
topo qtde
•••• 4
descritor
valor prox
5 ••••
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
Estado da pilha ANTES 
da exclusão 
Estado da pilha DEPOIS
da exclusão 
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 5 
 
while(1)
{ printf("Informe o numero:\n");
 scanf("%d", &numero);
if( numero < 0 ) break;
aux = (TLista *) malloc(sizeof( TLista ));
aux->valor = numero;
aux->prox = descritor.topo;
descritor.topo = aux;
descritor.qtde++;
}
printf("\n\nDigite 1 para excluir ou outra coisa para encerrar:\n");
scanf("%d", &numero);
if(numero == 1)
{ if( descritor.topo != NULL )
{ aux = descritor.topo;
descritor.topo = descritor.topo->prox;
descritor.qtde--;
printf("\n\nExcluindo o valor %d da pilha\n", aux->valor);
free(aux);
}
else
printf("\n\nA lista estah vazia\n");
}
return 0;
}
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari6 
 
Filas 
As filas (no inglês: queue) caracterizam-se por possuírem rotinas de inclusão (ou enfileiramento, 
no inglês: enqueue) e exclusão (ou desenfileiramento, no inglês: dequeue) de elementos 
operando em extremidades distintas da estrutura. Por esse motivo, o descritor da lista precisa 
carregar pelo menos dois ponteiros, uma para o seu início e outro para o seu final, como mostra a 
figura 10. A inicialização do descritor consiste apenas em colocar um nulo em seus ponteiros e 
um zero em seu membro qtde, como mostra a figura 11. 
 
struct descrFila
{
TLista *inicio;
TLista *final;
int qtde;
};
 descritor.inicio = NULL;
descritor.final = NULL;
descritor.qtde = 0; 
typedef struct descrFila DFila;
(…)
DFila descritor;
 Fig. 11: Inicialização do descritor da fila. 
Fig. 10: Definição do tipo e da variável descritora da fila. 
A rotina de inclusão em um fila aloca a nova variável dinamicamente e a configura com os dados 
úteis correspondentes. Como o novo elemento é o último da fila, seu ponteiro para o próximo 
recebe um nulo, indicando que não existe nada além dele naquele momento. O endereço de 
memória do novo elemento é colocado no ponteiro descritor para o final da lista e no ponteiro de 
próximo do até então último elemento. Finalmente, o descritor de quantidade é incrementado. 
Essa sequência de operações está indicada no código da figura 12. 
 
(...)
aux = (TLista *) malloc(sizeof( TLista ));
aux->valor = numero;
aux->prox = NULL;
if( descritor.inicio == NULL )
descritor.inicio = aux;
else
descritor.final->prox = aux;
descritor.final = aux;
descritor.qtde++;
(...)
Fig. 12: Inclusão de um elemento na fila. 
A figura 13 apresenta a situação inicial de uma fila com 3 elementos e a posterior inclusão de um 
novo nó por meio do código apresentado anteriormente. 
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fig. 13: Representação da fila antes e depois da inclusão de um elemento. 
 
A rotina de exclusão é semelhante à da pilha, uma vez que o elemento removido é o que 
antecede logicamente todos os outros. Compare o código da figura 14 com o da exclusão da 
pilha mostrado anteriormente. 
 
(...)
if( descritor.inicio != NULL )
{
aux = descritor.inicio;
descritor.inicio = descritor.inicio->prox;
descritor.qtde--;
if( descritor.qtde == 0 )
descritor.final = NULL;
free(aux);
}
(...)
Fig. 14: Exclusão de um elemento da fila. 
A figura 15 mostra a remoção de um elemento de uma fila que contém originalmente 4 
elementos. 
inicio final qtde
•••• •••• 3
descritor
valor prox
5 ••••
valor prox
10 ••••
valor prox
2 /
valor prox
5 ••••
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
inicio final qtde
•••• •••• 4
descritor
Estado da fila ANTES 
da inclusão 
Estado da fila DEPOIS 
da inclusão 
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fig. 15: Representação da fila antes e depois da exclusão de um elemento. 
As filas são extensamente utilizadas em aplicações de computação, como filas de impressão e 
outros jobs para processamento. Também são utilizadas para simular o comportamento de filas 
do mundo real e para orientar a sequência de processamento em aplicações dirigidas por eventos. 
O programa a seguir ilustra a implementação completa de uma fila de números inteiros 
representada por encadeamento em linguagem C. Para testá-lo, adapte-o para imprimir o 
conteúdo da fila antes e após a exclusão. 
#include <stdio.h>
struct regLista
{ int valor;
struct regLista *prox;
};
typedef struct regLista TLista;
struct descrFila
{ TLista *inicio;
TLista *final;
int qtde;
};
typedef struct descrFila DFila;
int main()
{ int numero;
DFila descritor;
TLista *aux;
descritor.inicio = NULL;
inicio final qtde
•••• •••• 3
descritor
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
valor prox
5 ••••
valor prox
10 ••••
valor prox
2 ••••
valor prox
3 /
inicio final qtde
•••• •••• 4
descritor
Estado da fila DEPOIS 
da exclusão 
Estado da fila ANTES
da exclusão 
Estruturas de Dados 
Pilhas e Filas 
Prof. Antonio Cesar de Barros Munari 9 
 
descritor.final = NULL;
descritor.qtde = 0;
while(1)
{ printf("Informe o numero:\n");
scanf("%d", &numero);
if( numero < 0 ) break;
aux = (TLista *) malloc(sizeof( TLista ));
aux->valor = numero;
aux->prox = NULL;
if( descritor.inicio == NULL )
descritor.inicio = aux;
else
descritor.final->prox = aux;
descritor.final = aux;
descritor.qtde++;
}
printf("\n\nDigite 1 para excluir ou outra coisa para encerrar:\n");
scanf("%d", &numero);
if(numero == 1)
{ if( descritor.inicio != NULL )
{ aux = descritor.inicio;
descritor.inicio = descritor.inicio->prox;
descritor.qtde--;
if( descritor.qtde == 0 )
descritor.final = NULL;
printf("\n\nExcluindo o valor %d da lista\n", aux->valor);
free(aux);
}
else
printf("\n\nA lista estah vazia\n");
}
return 0;
}