Estrutura de
Dados
Aplicações com
pilhas e filas
Professor Luiz José Hoffmann Filho
[email protected]
Aplicações de pilhas
• Controle de fluxo de execução
• Avaliação de expressões
• Resolução de problemas por tentativa e erro
Controle de fluxo de
execução
Int main() {
Printf(“chama função A”);
A();
Printf(“chama função B”);
B();
Printf(“chama função C”);
C();
Return;
}
Int A() {
Printf(“chama função B”);
B();
Printf(“chama função C”);
C();
Return;
}
Int B() {
Printf(“chama função C”);
C();
return;
}
Int C() {
Printf(“imprime resultado”);
return;
}
Controle de fluxo de
execução
Instrução
Pilha de controle
Saída de Vídeo
-
[0]
-
Printf(“chama função
A”);
[0]
Chama função A
A();
[0, 3]
-
Printf(“chama função
B”);
[0, 3]
Chama função B
B();
[0, 3, 6]
-
Printf(“chama função
C”);
[0, 3, 6]
Chama função C
C();
[0, 3, 6, 9]
-
Printf(“imprime
resultado”);
[0, 3, 6, 9]
Imprime resultado
Controle de fluxo de
execução
Instrução
Pilha de controle
Saída de Vídeo
Printf(“imprime
resultado”);
[0, 3, 6, 9]
Imprime resultado
Return;
[0, 3, 6]
-
Return;
[0, 3]
-
Printf(“chama função
C”);
[0, 3]
Chama função C
C();
[0, 3, 9]
-
Printf(“imprime
resultado”);
[0, 3, 9]
Imprime resultado
Controle de fluxo de
execução
Instrução
Pilha de controle
Saída de Vídeo
Printf(“imprime
resultado”);
[0, 3, 9]
Imprime resultado
Return;
[0, 3]
-
Return;
[0]
-
Printf(“chama função
B”);
[0, 6]
Chama função B
B();
[0, 6]
-
Printf(“chama função
C”);
[0, 6]
Chama função B
C();
[0, 6, 9]
-
Printf(“imprime
resultado”);
[0, 6, 9]
Imprime resultado
Controle de fluxo de
execução
Instrução
Pilha de controle
Saída de Vídeo
Printf(“imprime
resultado”);
[0, 6, 9]
Imprime resultado
Return;
[0, 6]
-
Return;
[0]
-
Printf(“chama função
C”);
[0]
Chama função C
C();
[0, 9]
-
Printf(“imprime
resultado”);
[0, 9]
Imprime resultado
Return;
[0]
-
Return;
[]
-
Avalição de expressões
• Vamos usar pilha para desenvolver um programa
capaz de avaliar expressões aritméticas composta
por:
o Operandos;
o Operadores aritméticos binários (+, -, *, /)
• Forma infixa:
o 3*9+8/2
o 5*(7-3)
• Resolvida de acordo com a prioridade dos
operadores
Avaliação de expressões
• A existência de prioridades e o uso de parênteses,
dificultam a avaliação das expressões
• Notação Prefixa (notação polonesa):
o Seus operadores são colocandos antes dos operados
• 3*9+8/2 = + * 3 9 / 8 2
• Notação Posfixa (notação polonesa reversa):
o Seus operadores são colocados após seus operandos
• 3*9+8/2 = 3 9 * 8 2 / +
Avaliação de expressões
Infixa
Prefixa
posfixa
A+B*C
+A*BC
ABC*+
(A+B)*C
*+ABC
AB+C*
( A + B) / ( C – D)
/+AB–CD
AB+CD-/
A/(B–C)*D
*/A–BCD
ABC-/D*
Avaliação de expressões
Percorrendo a expressão da esquerda para direira, cada operando encontrado
é armazenado na pilha; quando um operador é encontrado, os dois últimos
operandos são retirados, a operação realizada e seu resultado empilhado.
Exemplo 3 * 9 + 8 / 2 :
Posfixa
Ação para o componente encontrado
Pilha
39*82/+
Empilha 3
[3]
9*82/+
Empilha 9
[3, 9]
*82/+
Desempilha 3 e 9 e empilha 3 * 9
[27]
82/+
Empilha 8
[27, 8]
2/+
Empilha 2
[27, 8, 2]
/+
Desempilha 2 e 8 e empilha 2 / 8
[27, 4]
+
Desempilha 4 e 27 e empilha 4 + 27
[31]
Conversão de infixa para
posfixa
• Percorra da esquerda para direita;
•
•
•
•
Se for um “(“, empilhe-o;
Se for um operando, anexe-o à expressão posfixa;
Se for um operador, enquanto a pilha não estiver vazia e houver no seu
topo um operador com prioridade maior ou igual àquela do lexema
encontrado, desempilhe um operador e anexe-o à posfixa; ao final
empilha o lexema encontrado;
Se for um “)”, desempilhe um operador e anexe-o à expressão posfixa,
até que o “(“ correspondente apareça no topo da pilha. Então,
desempilhe esse “(“ e descarte-o.
–4
Lexema
Ação para o lexema
encontrado
Pilha
Posfixa
2
Anexar à posfixa
[]
2
*
empilhar
[*]
2
(
empilhar
[*, (]
2
7
Anexar à posfixa
[*, (]
27
+
empilhar
[*, (, +]
27
3
Anexar à posfixa
[*, (, +]
273
*
empilhar
[*, (, +, *]
273
5
Anexar à posfixa
[*, (, +, *]
2735
)
Desempilhar e anexar à
posfixa
[*, (]
2735*+
Desempilhar e descartar
[*]
2735*+
Desempilhar e anexar à
posfixa
[]
2735*+*
empilhar
[-]
2735*+*
-
Resolução de problemas
por tentativa e Erro
• Com usar uma pilha para implementar um técnica
conhecida como Backtracking (ou retrocesso),
frequentemente usada em Inteligência Artificial
para resolver problemas por meio de tentativa e
erro.
• Esta técnica é útil em situações em que, a cada
instante, tempos várias opções é não sabemos
avaliar a melhor. Então, escolhemos uma delas e,
caso essa escolha não leve à solução do
problema, retrocedemos e fazemos uma nova
escolha.
Resolução de problemas por
tentativa e Erro
• Problema : Um porco precisa achar o caminha da
saída e um labirinto?
• Como fazer isto utilizando um pilha
Solução
• ?
Aplicações de Filas
• Simulação de atendimento bancário
• Um servidor de impressão
• Fila de processos para serem executados –
escalonamento de CPU
Simulação de atendimento
bancário
• Realizar uma simulação para determinar o tempo
médio que um cliente permanece na fila de uma
agência bancário. Quando um cliente entra na
fila, o horário é anotado. Quando ele sai, o tempo
que ele permaneceu na fila é calculado e
adicionado ao tempo total de espera. Assim, no
final do expediente, podemos determinar quanto
tempo, em média, cada cliente teve de aguardar
para ser atendido. E também quanto tempo, em
média, ele demorou em seu atendimento.
Simulação de atendimento
bancário
• Dois eventos:
o Cliente chega na agência e entra na fila
o Um caixa é liberar, e um cliente é retirar da fila.
• Algoritmo:
o Zerar o cronômetro.
o Enquanto não terminar o expediente:
• Se um cliente chegou, então entra na fila – start cronômetro
• Se há caixas livres e a fila não esta vazia, clientes saem da fila e dirigemse a eles para serem atendidos – para cronômetro.
• Começo a ser atendido – start outro cronômetro
• Terminou de ser atendido – para o cronômetro.
Servidor de Impressão
Exercícios
• Transforme cada uma das seguintes expressões em
prefixas e posfixas:
o
o
o
o
A+B–C
(A + B) * (C -D) + E * F
(A + B) * (C * (D - E) + F) - G
(A + (((B - C) * (D – E ) + F) + G) * ( H - J)
• Aplique o algoritmo de avaliação apresentado, para
avaliar as seguintes expressões posfixas. Pressuponha
que A = 1, B = 2, C = 3.
o AB + C - BA + C $ o ABC + * CBA - + *
Exercícios
• Codifique um programa para ler uma frase e
imprimi-la com as palavras invertidas. Por exemplo,
se for digitada a frase “Apenas um teste”, o
programa deve exibir a frase “sanepA mu etset”.
• Dizemos que uma frase é um palíndromo se pode
se igualmente lida da esquerda para a direita ou
da direita para a esquerda, por exemplo, “subi no
onibus”. Codifique uma rotina que use uma pilha
para verificar se uma frase é um palídromo.
Exercícios
• Codifique uma função para converter um
expressão infixa em posfixa.
• Codifique uma função para avaliar uma expressão
posfixa.