Baixe o app para aproveitar ainda mais
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
Compartilhar