aulaPilhas

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Pilhas
Valéria de Carvalho Santos
valeriac@icmc.usp.br
Departamento de Estatística, Matemática Aplicada e Computação
Instituto de Geociências e Ciências Exatas
Universidade Estadual Paulista “Júlio de Mesquita”
05 de abril de 2013
Definição
• Pilhas: são listas lineares nas quais as operações são realizadas 
na mesma extremidade, denominada topo
7
2
4topo
Definição
• As operações em pilhas seguem a ordem: último a entrar –
primeiro a sair
• Last in/ First out (LIFO)
Operações
• Existem duas operações básicas que devem ser implementadas 
numa estrutura de pilha:
• empilhar: insere um novo elemento no topo
• desempilhar: remove um elemento do topo
Operações
1 2 3 4 5
1 1 1 1 1
2 2 2 2
3 3 3
4 4
5
1
2
3
4
5
1
2
3
4
1
2
3
1
2
1
5 4 3 2 1
Empilhar
Desempilhar
Operações
• Operações auxiliares:
• criar(P): criar uma pilha P vazia
• topo(P): retorna o elemento do topo de P, sem remover
• contar(P): retorna o número de elementos em P
• vazia(P): verifica se a pilha P está vazia
• cheia(P): indica se a pilha P está cheia (implementações 
estáticas)
Implementação Estática
• Inserções e remoções realizadas no fim da estrutura (posição do 
topo)
• Uma variável mantém o controle da posição do topo
• Informar o número de elementos na pilha
1 2 3 topo
Definição de Tipos
Implementação Estática
Implementação Estática
Implementação Estática
• Usando uma pilha auxiliar, implemente o imprimir para exibir a 
pilha na ordem correta.
1 2 3 topo
Exercício
• Fazer um método para verificar se um elemento existe na 
pilha
• Fazer um programa principal para:
• Empilhar N elementos
• Desempilhar 2 elementos
• Consultar se um elemento existe na pilha
Implementação Dinâmica
• Não há necessidade de percorrer a lista
• Pode-se implementar as operações utilizando lista ligada simples
a b c d
topo
Definição de Tipos
Implementação Dinâmica
Implementação Dinâmica
Implementação Dinâmica
Exercício
• Fazer um método para verificar se um elemento existe na 
pilha
• Fazer um programa principal para:
• Empilhar N elementos
• Desempilhar 2 elementos
• Consultar se um elemento existe na pilha
Aplicações de Pilha
• Avaliação de Expressões Aritméticas
• Notação infixa é ambígua
• A+B*C
• Necessidade de precedência de operadores ou uso de 
parênteses
• Notação prefixa (polonesa)
• Operadores precedem operandos
• Dispensa o uso de parênteses
• -*AB/CD = (A*B) – (C/D)
• Notação posfixa (polonesa reversa)
• Operandos antecedem operadores
• Dispensa o uso de parênteses
• AB*CD/- = (A*B) – (C/D)
Aplicações de Pilha
• Expressões na notação posfixa podem ser avaliadas utilizando 
uma pilha
• A expressão é avaliada da esquerda para a direita
• Os operandos são empilhados
• Os operadores fazem com que dois operandos sejam 
desempilhados, o cálculo seja realizado e o resultado 
empilhados
Aplicações de Pilha
• Exemplo
• 6 2 / 3 4 * + 3 - = 6 / 2 + 3 * 4 - 3
Aplicações de Pilha
• Conversão da notação infixa para posfixa
• Precedência dos operadores:
• * /
• + -
• Operando: saída
• Operador:
• Precedência menor que o topo
• Empilha
• Precedência maior ou igual ao topo
• Desempilha e empilha o novo operador
• Parênteses aberto: empilha
• Parênteses fechado: desempilha até encontrar o aberto
• Exemplo: A*(B+C)/D