a03-pilha

Prévia do material em texto

Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Pilha
Estrutura de Dados
6 de marc¸o de 2014
Estrutura de Dados 1
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
To´picos
1 Introduc¸a˜o
2 TAD: Pilha
3 Implementac¸a˜o
Esta´tica: vetor
Dinaˆmica
4 Resumo TAD
Estrutura de Dados 2
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
O TIPO ABSTRATO PILHA
Estrutura de Dados 3
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Pilha (Stack)
tipo abstrato Pilha
Uma pilha e´ uma colec¸a˜o de itens que sa˜o acessados segundo a
disciplina LIFO (Last In, First Out). Isto e´, itens sa˜o acrescentados
a` e retirados da colec¸a˜o, de forma que o u´ltimo elemento
acrescentado (topo da pilha) e´ o primeiro a ser retirado. Uma pilha
sem itens e´ denominada pilha vazia.
func¸a˜o cria pilha(): Pilha
po´s-condic¸a˜o: cria uma pilha vazia.
func¸a˜o empty (P: Pilha): Booleano
po´s-condic¸a˜o: retorna verdadeiro se P esta´ vazia; falso, caso
contra´rio.
Estrutura de Dados 4
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
TAD Pilha (cont)
procedimento push(P: Pilha, I: Item)
po´s-condic¸a˜o: o item I e´ acrescentado ao topo da pilha.
func¸a˜o pop(P: Pilha): Item
pre´-condic¸a˜o: not empty(P)
po´s-condic¸a˜o: retira e retorna o elemento do topo da pilha. O
item inserido imediatamente anterior ao topo, torna-se o novo topo
da pilha.
Mas, o que e´ um Item???
... Pratos, colheres, nu´meros inteiros, abo´boras, strings,....
Estrutura de Dados 5
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Exercicio
Calculadora Polonesa Reversa
Usando uma pilha, seria poss´ıvel terminar de escrever o algoritmo
para calcular o valor de uma expressa˜o usando notac¸a˜o polonesa
reversa?
Estrutura de Dados 6
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
A IMPLEMENTAC¸A˜O DO TAD PILHA COM ALOCAC¸A˜O
ESTA´TICA
Estrutura de Dados 7
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Pilha (push)
Estrutura de Dados 8
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Pilha (pop)
26 na pilha e´ lixo!
LEMBRE-SE: topo indica a primeira posic¸a˜o NA˜O usada.
Estrutura de Dados 9
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Exerc´ıcio
Exerc´ıcio
Na pa´gina da disciplina esta˜o os arquivos com uma implementac¸a˜o
parcial da pilha. Terminar de implementar as operac¸o˜es. Modificar
a implementac¸a˜o para pilhas de float, string, structs.
Estrutura de Dados 10
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Pilha Gene´rica
tipo abstrato <<Item>> Pilha
Colec¸a˜o de itens que sa˜o acessados segundo a disciplina LIFO, . . .
func¸a˜o cria pilha(): Pilha<<Item>>
po´s-condic¸a˜o: cria uma pilha vazia.
procedimento push(P: Pilha, I: Item)
po´s-condic¸a˜o: o item I e´ acrescentado ao topo da pilha.
func¸a˜o pop(P: Pilha): Item
pre´-condic¸a˜o: not empty(P)
po´s-condic¸a˜o: retira e retorna o elemento do topo da pilha . . . .
Estrutura de Dados 11
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Pilha Gene´rica (cont)
Uso
var p1: Pilha<<int>>
var p2: Pilha<<float>>
var i: int;
var f: float;
p1 := cria pilha();
p2 := cria pilha();
push(p1,10);
push(p2,3.14);
Estrutura de Dados 12
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
A IMPLEMENTAC¸A˜O DO TAD PILHA COM ALOCAC¸A˜O
DINAˆMICA
Estrutura de Dados 13
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esta´tica: vetor
Dinaˆmica
Pilha (Implementac¸a˜o com Alocac¸a˜o Dinaˆmica)
Estrutura de Dados 14
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
UM RESUMO ESQUEMA´TICO (TAD)
Estrutura de Dados 15
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esquema TAD
tipo abstrato <<T>> TpAb
Descrever conceitualmente. Utilizar conceitos matema´ticos, tais
como, conjunto, sequeˆncia, produto cartesiano, etc.
func¸a˜o cria Ab(....): TpAb
Provavelmente, o TAD tera´ uma operac¸a˜o que cria uma instaˆncia.
procedimento nome(ta: TpAb,....)
pre´-condic¸a˜o: so´ pode ser invocado se for verdadeira
po´s-condic¸a˜o: consequeˆncia da execuc¸a˜o da operac¸a˜o.
func¸a˜o nome (ta: TpAb,....): TpRet
pre´-condic¸a˜o: .... po´s-condic¸a˜o: ....
Estrutura de Dados 16
Introduc¸a˜o
TAD: Pilha
Implementac¸a˜o
Resumo TAD
Esquema resumido de TADs ba´sicos
.
Ver na pa´gina da disciplina um esquema resumido de tipos
abstratos ba´sicos que voceˆs podem usar para descrever seus tipos
abstratos. Note que a notac¸a˜o e´ resumida para caber em uma
pa´gina.
Estrutura de Dados 17
	Introdução
	TAD: Pilha
	Implementação
	Estática: vetor
	Dinâmica
	Resumo TAD