AEDS COLTEC aula3 pilhas

Prévia do material em texto

Aula 3: Pilhas
Professor(a): Virgínia Fernandes Mota
http://www.dcc.ufmg.br/∼virginiaferm
ALGORITMOS E ESTRUTURAS DE DADOS - SETOR DE INFORMÁTICA
Virgínia Fernandes Mota Aula 3: Pilhas
Pilhas
Uma das estruturas de dados mais simples é a pilha.
Sua idéia fundamental é que todo o acesso a seus elementos
seja feito a partir do topo.
LIFO - Last in First Out
Operações básicas: push (empilhar) e pop (desempilhar).
Virgínia Fernandes Mota Aula 3: Pilhas
Pilhas
Virgínia Fernandes Mota Aula 3: Pilhas
Interface do tipo Pilha
Consideraremos duas implementações de pilha: usando vetor e
usando lista encadeada.
Vamos considerar as seguintes operações:
criar uma pilha vazia;
inserir um elemento no topo (push);
remover o elemento do topo (pop);
verificar se a pilha está vazia;
liberar a estrutura de pilha;
Virgínia Fernandes Mota Aula 3: Pilhas
Interface do tipo Pilha
O arquivo pilha.h pode conter o seguinte código:
1 t yp ed e f s t r u c t p i l h a P i l h a ;
2 P i l h a ∗ p i l h a_ c r i a ( ) ;
3 vo i d p i lha_push ( P i l h a ∗p , f l o a t v ) ;
4 f l o a t p i lha_pop ( P i l h a ∗p ) ;
5 i n t p i l h a_va z i a ( P i l h a ∗p ) ;
6 vo i d p i l h a_ l i b e r a ( P i l h a ∗p ) ;
O tipo pilha criado pode ser implementado usando vetor ou
lista encadeada
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor
Em algumas aplicações computacionais é comum saber de
antemão o número máximo de elementos que podem estar
armazenados simultaneamente na pilha.
Neste caso, a implementação da pilha pode ser feita por um
vetor.
1 #d e f i n e N 50 ;
2 s t r u c t p i l h a {
3 i n t n ;
4 f l o a t v e t [N ] ;
5 } ;
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor - Criação
1 P i l h a ∗ p i l h a_ c r i a ( ) {
2 P i l h a ∗p = ( P i l h a ∗) ma l l o c ( s i z e o f ( P i l h a ) ) ;
3 p−>n = 0 ; // i n i c i a l i z a com ze ro e l ementos
4 r e t u r n p ;
5 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor - Inserção
1 vo i d p i lha_push ( P i l h a ∗p , f l o a t v ) {
2 i f ( p−>n == N) {
3 p r i n t f ( " Capac idade da p i l h a e s t ou r ou . " ) ;
4 e x i t (1 ) ;
5 }
6 // i n s e r e e lemento na próx ima po s i ç ã o l i v r e
7 p−>vet [ p−>n ] = v ;
8 p−>n++;
9 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor - Remoção
1 f l o a t p i lha_pop ( P i l h a ∗p ) {
2 f l o a t v ;
3 i f ( p i l h a_va z i a ( p ) ) {
4 p r i n t f ( " P i l h a v a z i a ! " ) ;
5 e x i t (1 ) ;
6 }
7 // R e t i r a e lemento do topo
8 v = p−>vet [ p−>n − 1 ] ;
9 p−>n−−;
10 r e t u r n v ;
11 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor - Pilha vazia
1 i n t p i l h a_va z i a ( P i l h a ∗p ) {
2 r e t u r n (p−>n == 0) ;
3 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com vetor - Liberar
1 vo i d p i l h a_ l i b e r a ( P i l h a ∗p ) {
2 f r e e ( p ) ;
3 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista
Quando o número máximo de elementos que serão
armazenados na pilha não é conhecido, devemos implementar
a pilha com uma estrutura de dados dinâmica.
Usaremos então uma lista encadeada.
1 s t r u c t l i s t a {
2 f l o a t i n f o ;
3 s t r u c t l i s t a ∗prox ;
4 } ;
5
6 t y p ed e f s t r u c t l i s t a L i s t a ;
7
8 s t r u c t p i l h a {
9 L i s t a ∗pr im ;
10 } ;
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Criação
1 P i l h a ∗ p i l h a_ c r i a ( ) {
2 P i l h a ∗p = ( P i l h a ∗) ma l l o c ( s i z e o f ( P i l h a ) ) ;
3 p−>prim = NULL ;
4 r e t u r n p ;
5 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Inserção
1 vo i d p i lha_push ( P i l h a ∗p , f l o a t v ) {
2 L i s t a ∗n = ( L i s t a ∗) ma l l o c ( s i z e o f ( L i s t a ) ) ;
3 n−>i n f o = v ;
4 n−>prox = p−>prim ;
5 p−>prim = n ;
6 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Remoção
1 f l o a t p i lha_pop ( P i l h a ∗p ) {
2 L i s t a ∗ t ;
3 f l o a t v ;
4 i f ( p i l h a_va z i a ( p ) ) {
5 p r i n t f ( " P i l h a v a z i a " ) ;
6 e x i t (1 ) ;
7 }
8 t = p−>prim ;
9 v = t−>i n f o ;
10 p−>prim = t−>prox ;
11 f r e e ( t ) ;
12 r e t u r n v ;
13 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Pilha vazia
1 i n t p i l h a_va z i a ( P i l h a ∗p ) {
2 r e t u r n (p−>prim == NULL) ;
3 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Liberar
1 vo i d p i l h a_ l i b e r a ( P i l h a ∗p ) {
2 L i s t a ∗q = p−>prim ;
3 wh i l e ( q != NULL) {
4 L i s t a ∗ t = q−>prox ;
5 f r e e ( q ) ;
6 q = t ;
7 }
8 f r e e ( p ) ;
9 }
Virgínia Fernandes Mota Aula 3: Pilhas
Implementação de pilha com lista - Impressão
1 // impr ime v e r s a o com ve t o r
2 vo i d p i lha_impr ime ( P i l h a ∗p ) {
3 i n t i ;
4 f o r ( i = p−>n−1; i >= 0 ; i−−)
5 p r i n t f ( "%f " , p−>vet [ i ] ) ;
6 }
7
8 // impr ime v e r s a o com l i s t a
9 vo i d p i lha_impr ime ( P i l h a ∗p ) {
10 L i s t a ∗q ;
11 f o r ( q = p−>prim ; q != NULL ; q = q−>prox )
12 p r i n t f ( "%f " , q−>i n f o ) ;
13 }
Virgínia Fernandes Mota Aula 3: Pilhas
Estudo de caso: Calculadora pós-fixada
Um bom exemplo de aplicação de pilha é o funcionamento das
calculadoras HP.
Elas trabalham com expressões pós-fixadas, então para avaliar
uma expressão como (1-2)*(4+5) podemos digitar
1 2 - 4 5 + *.
Virgínia Fernandes Mota Aula 3: Pilhas
Estudo de caso: Calculadora pós-fixada
1 s t r u c t c a l c {
2 cha r f [ 2 1 ] ;
3 P i l h a ∗p ; // p i l h a de operandos
4 }
5
6 t yp ed e f s t r u c t c a l c Ca lc ;
7
8 Ca lc ∗ c a l c_c r i a ( cha r ∗ fo rmato ) {
9 Ca lc ∗c = ( Ca lc ∗) ma l l o c ( s i z e o f ( Ca lc ) ) ;
10 s t r c p y ( c−>f , formato ) ;
11 c−>p = p i l h a_c r i a ( ) ; // c r i a p i l h a v a z i a
12 r e t u r n c ;
13 }
14
15 vo i d ca lc_operando ( Ca lc ∗c , f l o a t v ) {
16 p i lha_push ( c−>p , v ) ; // emp i lha operando
17 p r i n t f ( c−>f , v ) ; // impr ime topo
18 }
19
20 vo i d c a l c_ l i b e r a ( Ca lc ∗c ) {
21 p i l h a_ l i b e r a ( c−>p) ;
22 f r e e ( c ) ;
23 }
Virgínia Fernandes Mota Aula 3: Pilhas
Estudo de caso: Calculadora pós-fixada
1 vo i d ca l c_ope rado r ( Ca lc ∗c , cha r op ) {
2 f l o a t v1 , v2 , v ;
3 // de semp i l ha operandos
4 i f ( p i l h a_va z i a ( c−>p) )
5 v2 = 0 . 0 ;
6 e l s e
7 v2 = pi lha_pop ( c−>p) ;
8
9 i f ( p i l h a_va z i a ( c−>p) )
10 v1 = 0 . 0 ;
11 e l s e
12 v1 = pi lha_pop ( c−>p) ;
13
14 // f a z operacao
15 sw t i c h ( op ) {
16 ca se ’+’ : v = v1 + v2 ; b reak ;
17 ca se ’− ’ : v = v1 − v2 ; b reak ;
18 ca se ’∗ ’ : v = v1 ∗ v2 ; b reak ;
19 ca se ’ / ’ : v = v1 / v2 ; b reak ;
20 }
21
22 // emp i lha r e s u l t a d o
23 p i lha_push ( c−>p , v ) ;
24
25 // impr ime topo da p i l h a
26 p r i n t f ( c−>f , v ) ;
27 }
Virgínia Fernandes Mota Aula 3: Pilhas
Estudo de caso: Calculadora pós-fixada
1 //Programa para l e r e x p r e s s ã o e chamar f unçõe s da c a l c u l a d o r a
2 i n t main ( ) {
3 cha r c ;
4 f l o a t v ;
5 Ca lc ∗ c a l c ;
6 c a l c = c a l c_c r i a ( "%.2 f " ) ; // c r i a c a l c u l a d o r a com formato de duas
ca s a s d e c ima i s
7 do{
8 s c an f ( " %c" , &c ) ;
9 i f ( c == ’+’ | | c == ’− ’ | | c == ’∗ ’ | | c == ’ / ’ ) {
10 ca l c_ope rado r ( ca l c , c ) ;
11 }
12 e l s e {
13 ungetc ( c , s t d i n ) ;
14 i f ( s c a n f ( "%f " , &v ) == 1)
15 ca lc_operando ( ca l c , v ) ;
16 }
17 } wh i l e ( c != ’ q ’ ) ;
18 c a l c_ l i b e r a ( c a l c ) ;
19 r e t u r n 0 ;
20 }Virgínia Fernandes Mota Aula 3: Pilhas
Estudo de caso: Calculadora pós-fixada
Exemplo de saída:
3 5 8 * + digitado pelo usuário
3.00
5.00
8.00
40.00
43.00
7 / digitado pelo usuário
7.00
6.14
q digitado pelo usuário
Virgínia Fernandes Mota Aula 3: Pilhas
Exercícios
1. Implementar as funções/procedimentos apresentados em sala
para a manipulação de pilhas. Crie pilhas.c e pilhas.h para a
manipulação das pilhas (com vetor e com lista) e main.c para
testes. Crie um makefile para compilar o código.
2. Faça um programa para determinar se a sequência de parênteses
em uma expressão matemática está bem formada (ou seja,
parênteses são fechados na ordem inversa àquela em que foram
abertos).
Virgínia Fernandes Mota Aula 3: Pilhas
Na próxima aula...
Filas
Virgínia Fernandes Mota Aula 3: Pilhas