Estruturas de Dados - Pilhas (Dibio)

Prévia do material em texto

dibio@unb.br
Roteiro
● Execucão de programas (estruturas de prioridade)
● Pilhas
● Pilhas como vetor
● Pilhas como Lista Encadeada
● TAD
● Exemplo: Calculadora com lógica polonesa
dibio@unb.br
Observem um Programinha em C...
#include<stdio.h>
int main (void) {
int a, b, c, d;
scanf(“ %d %d %d\n”, &b, &c, &d);
a = b + c * d;
printf(“\n a: %d\n”, a);
return 0;
}
dibio@unb.br
● Como os valores são carregados e guardados em 
ordem?
● Como as operacões são executadas na ordem?
● Qual estrutura organiza essa sequência prioritária 
de tarefas?
● Como modelar tal estrutura?
dibio@unb.br
Pilhas
● A idéia fundamental da pilha é que todo o acesso a 
seus elementos é feito através do seu topo. Assim, 
quando um elemento novo é introduzido na pilha, 
passa a ser o elemento do topo, e o único elemento 
que pode ser removido da pilha é o do topo.
● LIFO (Last In, First Out)
dibio@unb.br
Uso/aplicacões
● Ex: O exemplo de utilização de pilha mais 
próximo é a própria pilha de execução da 
linguagem C. As variáveis locais das funções são 
dispostas numa pilha e uma função só tem acesso 
às variáveis que estão no topo (não é possível 
acessar as variáveis da função locais às outras 
funções).
● Operacões pós-fixas
● Editores de texto
● ...
dibio@unb.br
Funcionamento de uma pilha
dibio@unb.br
Exemplo (Pilha de ExecuÇão de 
funÇões)
dibio@unb.br
Exemplo (execuÇão de funÇões)
dibio@unb.br
OperaÇões básicas
● criar uma estrutura de pilha;
● inserir um elemento no topo (push);
● remover o elemento do topo (pop);
● verificar se a pilha está vazia;
● liberar a estrutura de pilha.
dibio@unb.br
TAD em C
dibio@unb.br
ImplementaÇão como um Vetor
dibio@unb.br
Criar estrutura de pilha
dibio@unb.br
InserÇão
dibio@unb.br
RemoÇão 
dibio@unb.br
Testar se pilha está vazia 
dibio@unb.br
Libera memória de pilha
dibio@unb.br
Outras funÇões (pilha com Vetor)
dibio@unb.br
ImplementaÇão de pilha com Lista 
Encadeada
dibio@unb.br
Criar pilha (com Lista)
dibio@unb.br
Inserir elemento
dibio@unb.br
Retirar elemento (desempilhar)
dibio@unb.br
Testa se pilha está vazia
dibio@unb.br
Libera memória de pilha
dibio@unb.br
Outras funcões (pilha com Lista)
dibio@unb.br
Exemplo: NotaÇão polonesa (ou 
calculadora com notaÇão pós-fixa)
dibio@unb.br
Exemplo
dibio@unb.br
Criando funÇões da TAD (Exemplo)
dibio@unb.br
Criacão a partir da pilha
dibio@unb.br
Exemplo
dibio@unb.br
Exemplo (empilhar)
dibio@unb.br
Exemplo
dibio@unb.br
Exemplo (desempilhar)
dibio@unb.br
cont...calcula
dibio@unb.br
Exemplo (programa)
dibio@unb.br
cont...programa
dibio@unb.br
Exemplo de uso
dibio@unb.br
Exercício para casa 
● Estender a funcionalidade da calculadora pós-fixa 
com operacões de: (- unário), exponenciacão, raiz 
quadrada.
dibio@unb.br
Referências
● Celes, W.; Cerqueira, R. & Rangel, J.L. 
Introducão a Estruturas de Dados, Editora 
Campus (Elsevier), RJ, 2004.
● Cormen, T.; Leiserson, C. & Rivest, R. 
Algoritmos: teoria e prática, Campus Editora, RJ, 
2002.
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
Estruturas de Dados usando C, Makron Books, 
RJ, 1995.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38