Aula Pil Has

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.