13. Pilhas e Filas Encadeadas

Prévia do material em texto

Ju
d
so
n
 S
an
to
s 
S
an
ti
ag
o
PILHAS E FILAS ENCADEADAS
Alocação Encadeada
Pilha
 Para pilhas é mais fácil considerar as listas 
encadeadas sem o nó cabeça
 O topo é o primeiro nó da pilha
Algoritmo: Inserção na pilha
função empilhar(x)
ocupar(pt)
pt.info = novo-valor
pt.prox = topo 
topo = pt
λ
topo
43
14
64
Pilha
 Implementação em C/C++ da função de 
inserção em pilhas encadeadas:
void Empilhar(aluno & novo, aluno* & topo)
{
aluno * pt = new aluno;
*pt = novo;
pt->prox = topo;
topo = pt; 
}
λ
topo
43
14
64
Pilha
 O algoritmo de remoção verifica se a pilha 
esta vazia (topo == λ) antes de remover
Algoritmo: Remoção da pilha
função desempilhar()
se topo ≠ λ então
| pt = topo
| topo = topo.prox
| valor-recuperado = pt.info 
| desocupar(pt)
senão
| “Pilha vazia” 
λ
topo
32
43
14
64
Pilha
 Implementação em C/C++ da função de 
remoção em pilhas encadeadas:
void Desempilhar(aluno* & topo, aluno & removido)
{
if (topo != NULL)
{
aluno * pt = topo;
topo = topo->prox;
removido = *pt;
delete pt; 
}
else
cout << "Pilha vazia!" << endl;
}
λ
topo
43
14
64
Fila
 O algoritmo de inserção em filas insere 
sempre no fim
Algoritmo: Inserção na fila
função enfileirar(x) 
ocupar(pt)
pt.info = novo-valor
pt.prox = λ
se fim ≠ λ então
| fim.prox = pt
senão
| inicio = pt
fim = pt 
λ
inicio fim
43 14 64
Fila
 Implementação em C/C++ da função de 
inserção em filas encadeadas:
void Enfileirar(aluno & novo, aluno* & inicio, aluno* & fim)
{
aluno * pt = new aluno; 
*pt = novo;
pt->prox = NULL;
if (fim != NULL)
fim->prox = pt;
else
inicio = pt;
fim = pt;
}
λ
inicio fim
43 14 64
Fila
 O algoritmo de remoção remove sempre o 
elemento apontado pelo ponteiro inicio
Algoritmo: Remoção da fila
função desenfileirar()
se inicio ≠ λ então
| pt = inicio
| inicio = inicio.prox
| se inicio == λ então
| | fim = λ
| valor-recuperado = pt.info
| desocupar(pt)
senão
| “Fila vazia”
λ
inicio fim
43 14 64
Fila
 Implementação em C/C++ da função de 
remoção em filas encadeadas:
void Desenfileirar(aluno & removido, aluno* & inicio, aluno* & fim)
{
if (inicio != NULL)
{
aluno * pt = inicio;
inicio = inicio->prox;
if (inicio == NULL)
fim = NULL;
removido = *pt;
delete pt;
}
else
cout << "Fila vazia!" << endl;
}
λ
inicio fim
43 14 64
Aplicação
 A ordenação por distribuição é uma aplicação 
em que é preciso usar filas com alocação 
encadeada
 Seja uma lista L de n chaves representadas 
por um número inteiro numa base b. O 
problema consiste em ordenar essa lista.
 O algoritmo utiliza b filas, denotadas por Fi
 Seja d o comprimento máximo da 
representação das chaves na base b
Aplicação
 O algoritmo executa d iterações. Em cada 
uma delas a lista é inteiramente percorrida
 A primeira iteração destaca o dígito menos 
significativo de cada chave
 Se este dígito for k, a chave é inserida na fila 
Fk
 Ao terminar o percurso pela lista, as chaves se 
encontram distribuídas pelas filas, que devem 
então ser concatenadas em seqüência
Aplicação
 Inserção de L[j] na fila Fk: Fk L[j] 
 Remoção de um elemento da lista Fk e seu 
armazenamento em L[j]: L[j]  Fk
Algoritmo: Ordenação por distribuição
para i = 1 até d faça
| para j = 0 até n-1 faça
| | k = i-ésimo dígito menos significativo de L[j].chave
| | Fk  L[j]
| j = 0
| para k = 0 até b-1 faça
| | enquanto Fk ≠ ø faça
| | | L[j]  Fk
| | | j = j + 1
Lista Circular
 A busca em uma lista ordenada pode ser 
melhorada se apontarmos o último elemento 
da lista para o elemento cabeça
 A condição de parada deve ser alterada pois o 
teste de fim de lista nunca é satisfeito
ptlista
54 88 90 69
Lista Circular
 O ganho de desempenho aparece colocando 
o elemento procurado na cabeça da lista
(solução semelhante ao caso seqüencial)
 Modificações correspondentes devem ser 
introduzidas nos algoritmos de inserção e 
remoção
 O mesmo princípio, com as devidas 
adaptações, pode ser empregado para listas 
não ordenadas
Lista Circular
 Ao final da busca pont aponta para o último 
elemento pesquisado
Algoritmo: Busca em uma lista circular ordenada
procedimento busca-cir(x,ant,pont)
ant = ptlista
ptlista.chave = x
pont = ptlista.prox
enquanto pont.chave < x faça
| ant = pont
| pont = pont.prox
se pont ≠ ptlista e pont.chave == x então
| “chave localizada”
senão
| “chave não localizada”
Lista Duplamente Encadeada
 Nos algoritmos vistos até agora o ponteiro 
ant permite acessar o elemento anterior
 Entretanto isto não é suficiente se quisermos 
percorrer a lista nos dois sentidos
 O gasto de memória adicional é justificado 
pela praticidade obtida com o percurso da 
lista nos dois sentidos
ptlista 54 88 90 69
Lista Duplamente Encadeada
 Na busca a função retorna indicando o 
elemento buscado ou o seu consecutivo
Algoritmo: Busca em uma lista duplamente encadeada
função busca-dup(x)
ultimo = ptlista.ant
se x ≤ ultimo.chave então
| pont = ptlista.prox
| enquanto pont.chave < x faça
| | pont = pont.prox
| busca-dup = pont
senão
| busca-dup = ptlista
Lista Duplamente Encadeada
 O algoritmo de inserção:
Algoritmo: Inserção em uma lista duplamente encadeada
pont = busca-dup(x)
se pont = ptlista ou pont.chave ≠ x então
| anterior = pont.ant
| ocupar(pt)
| pt.info = novo-valor
| pt.chave = x
| pt.ant = anterior
| pt.prox = pont
| anterior.prox = pt
| pont.ant = pt
senão
| “elemento já está na lista”
Lista Duplamente Encadeada
 O algoritmo de remoção:
Algoritmo: Remoção em uma lista duplamente encadeada
pont = busca-dup(x)
se pont ≠ ptlista e pont.chave = x então
| anterior = pont.ant
| posterior = pont.prox
| anterior.prox = posterior
| posterior.ant = anterior
| valor-recuperado = pont.info
| desocupar(pont)
senão
| “elemento não está na lista”
Conclusão
 Listas encadeadas são mais eficientes que as 
listas seqüenciais quando os dados estão 
ordenados e nas operações de fusão ou cisão
de listas
 Elas utilizam alocação dinâmica de memória 
e a organização lógica de lista é feita através 
de ponteiros
 Filas e pilhas também se beneficiam do 
encadeamento se o número de elementos é 
desconhecido