njhg

PILHAS (STACK)
Professora Angela Lima Peres
Adaptado de Diego Cedrim e de http://www.ime.usp.br/~pf/algoritmos/aulas/ pilha.html http://www.ime.usp.br/~pf/algoritmos/aulas/ aloca.html#mallocc

PILHAS
¢ Como

funciona o sistema de empilhamento de pratos em um restaurante?

¢ Suponha

que você esteja lavando pratos e que alguém os empilhe para você

¢ Sempre

que um novo prato chega, vai pro topo da

¢ Sempre

o prato a ser lavado é o que está no topo

pilha

PILHAS
¢ Na

computação, existe uma estrutura de dados de se comporta de maneira semelhante

¢ Uma
—

pilha implementa uma política LIFO

Last in, first out (o último que entra é o primeiro que sai) ¢ O

funcionamento de uma pilha se baseia em inserir e remover elementos

¢ A

ordem que os elementos são removidos é o que define a pilha

EXEMPLOS
5

push(5)

5

2

5

2

5

2

5
5

push(2)

4

push(4) pop() pop()

8

push(8)

APLICAÇÃO: PARÊNTESES E COLCHETES
¢ Suponha

que queremos decidir se uma dada sequência de parênteses e colchetes está bemformada (ou seja, parênteses e colchetes são fechados na ordem inversa àquela em que forma abertos). Por exemplo, a primeira das sequências abaixo está bem-formada enquanto a segunda não está.
¢ ( ( ) [ ( ) ] )
¢ ( [ ) )
¢ Como usar pilhas para resolver o problema?

APLICAÇÕES
¢ Chamadas

recursivas de funções usam pilhas para saber onde as chamadas se encontram

¢ Gerenciamento

de memória em tempo de

execução
¢ Avaliação
¢ Parsing

de expressões matemática

AVALIAÇÃO DE EXPRESSÕES
¢ Na

notação usual de expressões aritméticas, os operadores são escritos entre os operandos; por isso, a notação é chamada infixa. Na notação polonesa, ou posfixa, os operadores são escritos depois dos operandos.

¢ Como

Infixa

Posfixa

(4+2)*3+5

42+3*5+

usar pilhas para avaliar uma expressão na
notação