Aula 03

Pilha

Pilha
Prof. MSc. Rafael Matsuyama [e-mail] Pilha

Pilha
• Conjunto ordenado de itens no qual somente em uma das extremidades novos itens podem ser inseridos, ou itens podem ser removidos.
• FILO – First In, Last Out  O primeiro a entrar será o último a sair.
• A extremidade onde os itens são inseridos ou removidos chama-se Topo da pilha.
• Analogia à pilha de pratos (ou livros ou outros objetos), de forma que somente os objetos que estão no topo podem ser removidos.

Aplicação

Aplicação

Aplicação

Aplicação - Chamada de Sub-rotinas
• A cada comando “call”:
– empilha (guarda para depois) o endereço para retornar a execução:
PUSH;
– passa a executar a nova sub-rotina.

• A cada comando “return”:
– desempilha o último endereço armazenado: POP;
– passa a executar a partir do endereço desempilhado. Aplicação - Chamada de Sub-rotinas

Operações
Pilha  Stack
•
•
•
•
•
•

Inserir um elemento  push
Remover um elemento  pop
Retornar o elemento de saída  top (peek)
Quantidade de elementos  size
Pilha vazia  isEmpty
Pilha cheia  isFull

Demonstração

http://www2.latech.edu/~box/ds/Stack/Stack.html

Dúvidas

Exercícios
1. Modifique o TAD Pilha para armazenar caracteres ao invés de números.
2. Escreva um programa (main) que utilize uma Pilha para inverter uma frase escrita pelo usuário.
Exemplo de string de entrada: testando saída: odnatset

Exercícios
3. Escreva um programa que leia uma expressão contendo parênteses ( ), colchetes [ ] e chaves { }, e verifique se a quantidade e ordem dos parênteses e chaves estão corretos na frase.
Exemplos:
( a ) b ( [ c ] d )  correto
(a(b)
 incorreto, falta parênteses
(a [c)d]
 incorreto, ordem errada