Aula 16: Filas de prioridades, pilhas, etc.
ADT = abstract data type = tipo abstrato de dados.
Por que abstrato
?
(Porque independe da implementação.)
Fila de prioridades (= priority queue)
-
Qualquer conjunto de objetos que aceita duas operações:
-
retira objeto mínimo,
-
insere novo objeto.
-
(Variante com
máximo
no lugar de mínimo
.)
-
Possíveis implementações: vetor sem ordem,
vetor crescente, heap, etc.
-
Queremos implementação em que ambas as operações são rápidas.
-
Trade-off:
implementação sofisticada só fica mais rápida que a simplória
quando a fila é grande.
-
Fila de prioridades: abstração
que ajuda o programador a organizar seu programa.
Pilha (= stack)
-
Qualquer conjunto de objetos que aceita duas operações:
-
retira objeto mais novo (= fresco),
-
insere novo objeto.
-
Possíveis implementações:
vetor, lista encadeada.
-
Pilha: abstração
que ajuda o programador a organizar seu programa.
-
Exemplo:
o computador usa uma
pilha de execução
para rodar um programa.
Aplicação de pilha: expressões polonesas
-
Expressão aritmética tradicional:
A + B + (C*D) - (E*F*G)
-
Expressão polonesa correspondente:
A B + C D * + E F * G * -
-
Expressão tradicional = infixa.
-
Expressão polonesa = posfixa.
-
Vantagens da polonesa:
(1) mais fácil para o computador e
(2) dispensa parênteses.
-
Exercício: Converta expressão infixa em polonesa.
(Use uma pilha para lembrar, na ordem certa,
das tarefas que não posso fazer agora
mas terei que fazer mais tarde.)
-
Exercício E16.2:
Calcular o valor de uma expressão polonesa dada.
Outras ADTs
-
Fila.
-
Tabela de símbolos.
-
etc.