10. Pilhas e Filas

Prévia do material em texto

Ju
d
so
n
 S
an
to
s 
S
an
ti
ag
o
PILHAS E FILAS
Alocação Seqüencial
Objetivos da Aula
Conhercer as estruturas de dados pilha e fila e 
seus principais algoritmos de manipulação
Inserção e remoção em pilhas
Inserção e remoção em filas
Aplicações
Notação Polonesa
Introdução
 O armazenamento seqüencial em listas é 
empregado quando as estruturas sofrem 
poucas inserções e remoções
64 75 77 8615 34 42 51 ×
Remoção implica em movimentar elementos
64 75 77 8615 34 42 51 52
Inserção implica em movimentar elementos
L
is
ta
s 
O
rd
en
ad
as
Introdução
 A situação ideal acontece quando inserções e 
remoções não implicam na movimentação de 
elementos da lista
87 22 5465 38 42 12 ×
Remoção é trivial
87 22 5465 38 42 12 52
Inserção é trivialL
is
ta
s 
 N
ão
 O
rd
en
ad
as
Introdução
 Essa situação ideal ocorre quando o elemento 
é inserido ou removido no início ou final da 
lista: Pilhas e Filas
Inserção/Remoção
87 22 5465 38 42 12 52
Inserção
87 22 5465 38 42 12 52
Remoção
P
ilh
as
F
ila
s FIFO
LIFO
Pilhas
 Uma pilha possui as seguintes características:
 Utiliza a organização sequencial de dados
 Define as operações:
 Inserção (empilhar)
 Remoção (desempilhar)
 É uma lista em que os elementos só podem ser 
inseridos ou removidos do final
Inserção/Remoção
87 22 5465 38 42 12 52
P
ilh
a LIFO
Pilhas
 No caso genérico considera-se sempre que a 
primeira posição de uma lista inicia no 
endereço 0 (zero)
 Uma alternativa ao caso genérico é usar uma 
variável para indicar o inicio e o fim da lista
87 22 5465 38 42 12 52
0 1 2 3 4 5 6 7 8 9
87 22 5465 52
0 1 2 3 4 5 6 7 8 9
inicio = 3
fim = 7
 No caso de pilhas apenas uma variável 
precisa ser considerada, a variável topo da 
pilha
int main (void)
{
int topo;
int pilha[6];
pilha[0] = 61;
pilha[1] = 22;
pilha[2] = 75;
topo = 2;
...
}
Pilhas
61
22
75
topo = 2
0
1
2
3
4
5
Inserção em Pilhas
 O algoritmo de inserção apresentado abaixo 
considera a memória disponível de M 
posições e possui complexidade O(1)
41
84
50
72
topo
Algoritmo: Insersão na pilha P
função empilhar(x)
se topo ≠ M-1 então
| topo = topo + 1 
| P[topo] = x
senão
| "Pilha está cheia"
M = 6
0
1
2
3
4
5
Inserção em Pilhas
 Implementação da inserção em pilhas em 
linguagem C/C++:
bool empilhar(int pilha[], int tam, int & topo, int x)
{
if (topo != tam-1)
{
topo = topo + 1;
pilha[topo] = x;
return true;
} 
else
{
cout << "pilha cheia" << endl;
return false;
} 
} 41
84
50
72
topo
0
1
2
3
4
5
Remoção em Pilhas
 O algoritmo de remoção apresentado abaixo 
considera a memória disponível de M 
posições e possui complexidade O(1)
Algoritmo: Remoção na pilha P
função desempilhar()
se topo >= 0 então
| valor = P[topo]
| topo = topo - 1
senão
| "Pilha está vazia"
41
84
50
72
topo
M 
0
1
2
3
4
5
Remoção em Pilhas
 Implementação da inserção em pilhas em 
linguagem C/C++:
bool desempilhar(int pilha[], int & topo, int & valor)
{
if (topo >= 0)
{
valor = pilha[topo];
topo = topo – 1;
return true;
}
else
{
cout << "pilha vazia\n"; 
return false;
} 
}
41
84
50
72
topo
M 
0
1
2
3
4
5
Filas
 Uma fila possui as seguintes características:
 Utiliza a organização sequencial de dados
 Define as operações:
 Inserção (enfileirar)
 Remoção (desenfileirar)
 É uma lista em que os elementos só podem ser 
inseridos no fim e removidos do início
87 22 5465 38 42 12 52
InserçãoRemoção
F
ila FIFO
Filas
 As filas exigem duas variáveis de controle, 
uma de início da fila e outra de fim da fila
 Para inserir um elemento incrementa-se a 
variável fim de fila, para remover incrementa-
se a variável início de fila
87 22 5465 38 42 12 52
fim = 7inicio = 0
0 1 2 3 4 5 6 7 8 9
Filas
 Ao fazer inserções e remoções, a fila se 
movimenta dentro da estrutura seqüencial
87 22 54 1538 42 12 52
fim = 8inicio = 1
0 1 2 3 4 5 6 7 8 9
87 22 5465 38 42 12 52
fim = 7inicio = 0
0 1 2 3 4 5 6 7 8 9
Inserção do 
elemento 15
Remoção de 
um elemento 
 Para eliminar esse problema considera-se os 
M elementos como se estivessem em círculo
Filas
87 22 54 15 412 52
fim = 9inicio = 3
0 1 2 3 4 5 6 7 8 9
87 22 54 15 481 12 52
fim = 0 inicio = 3
0 1 2 3 4 5 6 7 8 9
Inserção do 
elemento 81
Inserção em Filas
 No algoritmo de inserção, a variável prov
armazena provisoriamente a posição 
calculada repeitando a circularidade
Com a fila vazia
inicio = fim = -1
Algoritmo: Inserção na fila F
função enfileirar(x)
prov = (fim + 1) mod M
se prov ≠ inicio então
| fim = prov
| F[fim] = x 
| se inicio == -1 então
| | inicio = 0
senão
| "Fila está cheia"
87 22 54 38 65
fim = 7inicio = 3
0 1 2 3 4 5 6 7
Inserção em Filas
 Inserção em fila em linguagem C/C++:
bool enfileirar(int fila[], int tam, int & inicio, int & fim, int x)
{
int prov = (fim + 1) % tam;
if (prov != inicio)
{
fim = prov;
fila[fim] = x;
if (inicio == -1)
inicio = 0;
return true;
} 
else
{
cout << "fila cheia" << endl;
return false;
} 
}
87 22 54 38 65
fim = 7inicio = 3
0 1 2 3 4 5 6 7
Remoção em Filas
 O algoritmo de remoção também utiliza o 
operador mod para respeitar a circularidade
Algoritmo: Remoção na fila F
função desenfileirar()
se inicio ≠ -1 então
| valor = F[inicio]
| se inicio == fim então
| | inicio = fim = -1
| senão
| | inicio = (inicio + 1) mod M
senão
| "Fila está vazia"
8765 38 42
fim = 3inicio = 0
0 1 2 3 4
Remoção em Filas
 Remoção em filas em linguagem C/C++:
bool desenfileirar(int fila[], int tam, 
int & inicio, int & fim, int & valor)
{
if (inicio != -1)
{
valor = fila[inicio];
if (inicio == fim)
inicio = fim = – 1;
else
inicio = (inicio + 1) % tam;
return true;
}
else
{
cout << "fila vazia\n"; 
return false;
} 
}
8765 38 42
fim = 3inicio = 0
0 1 2 3 4
Aplicações
 Redes de Computadores
 Um simulador de tráfego de rede usa uma fila de 
recepção de dados
 Programação de Interfaces Gráficas
 O Windows usa uma fila de eventos para cada 
janela aberta na interface
 Editor de Texto
 A operação desfazer (ctrl-z) usa uma pilha
 Compiladores
 Análise da sintaxe de uma expressão usa pilha
Aplicação: Notação Polonesa
 A notação polonesa é uma representação 
para expressões aritméticas
 Ela é conveniente porque não é ambígua
como a notação tradicional, que exige regras 
de prioridade
 Notação tradicional: A * B –C / D
 Notação parentizada: ((A * B) – (C / D))
 Notação polonesa: – * A B / C D
 Notação polonesa reversa: A B * C D / –
Aplicação: Notação Polonesa
 Exercício: construir um conversor da notação 
parentizada para a notação polonesa reversa.
 Algumas constatações que podem auxiliar:
 Os operandos aparecem na mesma ordem na 
notação tradicional e na notação polonesa reversa
 Na notação polonesa reversa, os operandos 
aparecem na ordem em que devem ser calculados 
(da esquerda para a direita)
 Os operadores aparecem imediatamente após 
seus operandos
Aplicação: Notação Polonesa
Algoritmo: Conversão de notações
indexp = 0
indpol = -1
enquanto indexp < n faça
| se exp[indexp] é operando então
| | indpol = indpol + 1
| | pol[indpol] = exp[indexp]
| senão
| | se exp[indexp] é operador então
| | | empilhar(exp[indexp]) 
| | senão
| | |se exp[indexp] = ")" então
| | | | se desempilhar(operador) então
| | | | | indpol = indpol + 1
| | | | | pol[indpol] = operador
| | | | senão
| | | | | "expressão errada"
| └ └ └ └
| indexp = indexp + 1
└
Conclusão
 Estruturas de dados seqüenciais:
 Listas: inserções e remoções podem ser feitas em 
qualquer lugar, podem ser mantidas ordenadas ou 
não ordenadas
 Pilhas: as inserções e remoções são sempre feitas 
de um único lado da estrutura, chamado de topo 
da pilha
 Filas: inserções e remoções feitas nas 
extremidades - inserções no fim e remoções no 
início da fila