pilhas filas deques
TRANSCRIPT
-
8/12/2019 Pilhas Filas Deques
1/23
Estruturas de Dados
Pilhas, Filas e Deques
Prof. Eduardo Alchieri
-
8/12/2019 Pilhas Filas Deques
2/23
Estruturas de Dados
Pilhas
-
8/12/2019 Pilhas Filas Deques
3/23
Pilhas
Lista LIFO (Last In, First Out) Os elementos so colocados na estrutura (pilha) e retirados em
ordem inversa a de sua chegada Insero apenas no topo da pilha
!emoo apenas no topo da pilha
-
8/12/2019 Pilhas Filas Deques
4/23
Pilhas
Operaoes poss"veis# Esva$iar a pilha
%erificar se a pilha est& va$ia
'olocar um dado no topo da pilha (empilhar)
!etirar o dado do topo da pilha (desempilhar)
Etc.
-
8/12/2019 Pilhas Filas Deques
5/23
Pilhas
Implementao de pilhas sando vetores
Podese implementar uma pilha de tamanho fi*o usandovetores. Este tamanho determinar& o n+mero m&*imo de
elementos ue podero estar na pilha ao mesmo tempo - necess&rio um inteiro para arma$enar o valor da posio do
vetor aonde encontrase o topo da pilha sando uma lista ligada
A implementao de uma pilha ue usa como estrutura &sica
uma lista ligada / mais simples, pois a lista no / umaestrutura de tamanho fi*o
0asicamente, os dados devem ser colocados (empilhados)em alguma das e*tremidades da lista e retirados(desempilhados) a partir desta mesma e*tremidade
-
8/12/2019 Pilhas Filas Deques
6/23
Pilhas
- ideal para processamento de estruturas aninhadas deprofundidade imprevis"vel
ma pilha cont/m uma seu1ncia de origa2es adiadas. Aordem de remoo garante ue os dados mais internos sero
processados depois dos mais e*ternos 3uando / necess&rio percorrer um con4unto de dados e
guardar uma lista de coisas a fa$er posteriormente
O controle de seu1ncias de chamadas de suprogramas
A sinta*e de e*press2es aritm/ticas
-
8/12/2019 Pilhas Filas Deques
7/23
Pilhas
Aplica2es
'ontrole de delimitadores em uma euao (rastrearescopo)# 5(A 6 0) 7 ' 6 (8 6 E)9:F 6 ;< 6 => 9 I
Algoritmo# Percorrer a euao da seguinte forma#
? @ se um iniciali$ador de escopo for encontrado, o mesmo/ empilhado
@ se um finali$ar de escopo for encontrado, a pilha /
verificada Be estiver va$ia, ento a euao / incorreta Be no, desempilhar e comparar com o finali$ador
Ao final, a pilha deve estar va$ia
-
8/12/2019 Pilhas Filas Deques
8/23
Pilhas
Aplica2es
!ecursividade
A soluo de um prolema depende da soluo deinstCncias menores do mesmo prolema
-
8/12/2019 Pilhas Filas Deques
9/23
Pilhas
Aplica2es
3uanto / fatorial(D)
-
8/12/2019 Pilhas Filas Deques
10/23
Pilhas
Aplica2es
Avaliao de e*press2es posfi*as (raalho ?)
Gotao infi*a (/ a usual)# (H 6 ) 7 6 J 7 H
Os operadores in&rios aparecem entre os operandos A ordem das opera2es so determinadas pela
preced1ncia dos operadores ou pelos par1nteses KK(KK KK)KK Gotao prefi*a (notao polonesa)# 6 7 6 H 7 J H
Gotao posfi*a (notao polonesa reversa)# H 6 7 J H 7 6
Go fa$ uso de par1nteses e no reuer rela2es depreced1ncia
-
8/12/2019 Pilhas Filas Deques
11/23
Pilhas
Aplica2es
Algoritmo para avaliao de e*press2es posfi*as Os componentes da e*presso so processados da esuerda
para a direita como a seguir# Be o pr*imo componente da e*presso / um operando, o
valor do componente / colocado na pilha Be o pr*imo componente da e*presso / um operador, ento
os seus operandos esto na pilha. O n+mero reuerido deoperandos / retirado da pilha, a operao espec"fica /
reali$ada, e o resultado / arma$enado de volta na pilha. Ao final, a pilha conter& um +nico dado ue / o valor final da
e*presso
Bimule a e*ecuo do algoritmo com a e*presso a seguir#
H 6 7 J H 7 6
-
8/12/2019 Pilhas Filas Deques
12/23
Estruturas de Dados
Filas
-
8/12/2019 Pilhas Filas Deques
13/23
Filas
Lista FIFO (First In, First Out) Os elementos so colocados e retirados por ordem de chegada
Insero apenas no final da fila
!emoo apenas no in"cio da fila
-
8/12/2019 Pilhas Filas Deques
14/23
Filas
ma fila permite v&rias opera2es 'riar uma fila va$ia
Inserir um novo item (no final)
!emover um item (do in"cio)
Esva$iar a fila
Etc.
-
8/12/2019 Pilhas Filas Deques
15/23
Filas
Implementao de filas sando vetores
Podese implementar uma fila de tamanho fi*o usandovetores. Este tamanho determinar& o n+mero m&*imo deelementos ue podero estar na fila ao mesmo tempo
- necess&rio dois inteiros para arma$enar o valor dasposi2es do vetor aonde se encontram o in"cio e o final da fila
sando uma lista ligada
A implementao de uma fila ue usa como estrutura &sica
uma lista ligada / mais simples, pois a lista no / umaestrutura de tamanho fi*o 0asicamente, os dados devem ser colocados (enfileirados) no
final da lista e retirados (desenfileirados) do in"cio da lista.
-
8/12/2019 Pilhas Filas Deques
16/23
Filas
Aplica2es As filas so utili$adas uando dese4amos processar itens de
acordo com a ordem de chegada (o primeiro a chegar ser&o primeiro a ser processado).
Bistemas operacionais, por e*emplo, usam filas para regulara ordem em ue as tarefas devem receer processamento erecursos devem ser alocados a processos.
Fila de prioridade (insero ordenada)
Outras aplica2es Boma de inteiros (super) longos Manipulao de uma seu1ncia de caracteres
-
8/12/2019 Pilhas Filas Deques
17/23
Filas
Aplica2es tili$ada na implementao de percurso em largura em
&rvores
m percurso em largura percorre (visita) os ns da
&rvore segundo a ordem de seus n"veis ma maneira de implementar um percurso em largura de
uma &rvore / atrav/s do uso de uma fila#
Para comear o percurso, o n rai$ / posto na fila
Aps, repetir os seguintes passos at/ ue a fila este4ava$ia# !etire e visite (percorra) o primeiro n da fila 'oloue, da esuerda para a direita, seus filhos
na fila
-
8/12/2019 Pilhas Filas Deques
18/23
Filas
0 '
E ; = I
N L M
A
8
F
Bimule o algoritmo paraa seguinte arvore#
-
8/12/2019 Pilhas Filas Deques
19/23
Pilhas e Filas
E*erc"cio 8ada uma lista de caracteres formada por uma se1ncia
alternada de letras e d"gitos, construa um m/todo ueretorne uma lista na ual as letras so mantidas na
se1ncia original e os d"gitos so colocados na ordeminversa
E*emplo#
A ? E H Q R ;SA R E H Q ? ;
T ' = D 3 JSJ ' D = 3 T Buponha a e*ist1ncia de um m/todo eh8igito(ch caractere)
ue retorna true caso o caracterese4a um digito e false casocontr&rio.
-
8/12/2019 Pilhas Filas Deques
20/23
Estruturas de Dados
Deques
-
8/12/2019 Pilhas Filas Deques
21/23
Deques
Double-ended queue E*tenso de filas ue permite inserir e remover dados em
amas as e*tremidades
-
8/12/2019 Pilhas Filas Deques
22/23
Deques
ma deue permite v&rias opera2es 'riar uma deue
Inserir um novo item no in"cio
Inserir um novo item no final
!emover o item do in"cio
!emover o item do final
Esva$iar
Etc.
-
8/12/2019 Pilhas Filas Deques
23/23
Deques
A implementao de deues tam/m poder ser por meio devetores ou listas ligadas
Ga implementao atrav/s de listas ligadas, a utili$ao deuma lista duplamente encadeada torna a implementao maiseficiente !emover o n do final / mais eficiente em uma lista
duplamente encadeada do ue em uma lista simplesmenteencadeada