Pilha Dinâmica

Prévia do material em texto

Estrutura de Dados 
Faculdade Integradas do Ceará 
Análise e Desenvolvimento de Sistemas 
Agenda 
 
 
Listas Lineares Encadeadas: 
Pilha Dinâmica 
 
 Estrutura de Dados 
 Estrutura de Dados 
 
 
 
 
 
 
 
 
Estrutura de Dados Pilha Dinâmica 
conceituar, representar, compreender e implementar as operações com pilhas 
1 
4 
3 
2 
Pilha 
1 
4 
3 
2 
 Estrutura de Dados 
O que é uma Pilha 
 
Pilha 
1 
4 
3 
2 
 Estrutura de Dados 
O que é uma Pilha 
 
• São listas nas quais o acesso 
somente pode ser feito em 
uma das extremidades, 
denominada de topo da pilha. 
• Todas as consultas, 
alterações, inclusões, 
remoções de nodos somente 
podem ser realizadas sobre 
um nodo, que é aquele que 
está no topo da pilha. 
 
Pilha 
 
 Estrutura de Dados 
• Os nodos são colocados um sobre o outro. O 
nodo inserido mais recentemente está no topo e o 
inserido menos recentemente no fundo/base. 
 
• Propriedade: o último nodo inserido é o 
primeiro nodo que pode ser retirado da lista. Isto 
faz com que os elementos da pilha sejam 
retirados na ordem inversa à ordem em que foram 
introduzidos: último a entrar será o primeiro a sair 
da pilha (LIFO – last in, first out). 
Pilha 
 
 Estrutura de Dados 
• As operação que podem ser realizadas sobre uma 
pilhar são limitadas pela forma de acesso da 
estrutura (LIFO): 
– Criar uma pilha vazia; 
– Testar se a pilha está vazia; 
– Consulta e/ou modifica o elemento do topo da pilha (sem 
eliminar); 
– Inserir um novo elemento no topo de pilha (empilhar); 
– Remover o elemento do topo de pilha(desempilhar). 
Pilha 
Operações 
 Estrutura de Dados 
• A estrutura de dados Pilha pode ser implementada 
de duas formas: 
– por meio de arranjos (vetores) e 
– por meio de apontadores (alocação 
dinâmica). 
Pilha 
Implementação 
 Estrutura de Dados 
• Não existe mais o teste de Pilha cheia. 
– Não vamos mais utilizar o descritor TamMax da Pilha; 
– Os nodos serão alocados de forma dinâmica. 
 
• Todavia, iremos continuar com o descritor TOPO, 
porém ele será um apontador para o próximo nodo 
da pilha. 
 
Pilha Dinâmica 
Implementação 
 Estrutura de Dados 
 Estrutura de Dados 
Pilha Dinâmica 
Pré e Pós Condições 
• Inicializa 
– Pre-condições: Não há 
– Pós-condições: topo aponta para NULL 
• Empilha (Elemento) 
– Pre-condições: Não há 
– Pós-condições: topo aponta para novo nodo contendo o 
elemento. Prox de topo aponta para o topo anterior 
• Desempilha 
– Pre-condições: pilha não vazia 
– Pós-condições: remove o nodo do topo. Topo aponta para 
o próximo de topo . 
Dúvidas 
 Estrutura de Dados