40094462852

ALGORITMOS E
PROGRAMAÇÃO II
Pilhas e outras estruturas de dados
Prof. Thiago S. Motta

Roteiro
• Na aula passada
• Pilhas
• Árvores
• Grafos

Arrays
• Um conjunto de elementos de um mesmo tipo
• Tamanho definido
• Alocação estática de memória

0

1

2

3

4

5

6

7

tipo[] nome = new tipo[ 8 ] tamanho Listas de Dados
• Um conjunto de elementos de um mesmo tipo
• Tamanho variável
• Alocação dinâmica de memória

nada aqui ArrayList nome = new ArrayList()

Depois adicionamos regras aos conjuntos

Filas
• FIFO: o primeiro que entra é o primeiro que sai
• Filas de processos, filas de impressão, etc.

Pilhas
• Também uma das principais estruturas de dados
• Está presente nas aplicações que utilizamos todos os

dias
• Mesmo que não nos demos conta

FILO
(first in – last out)
O primeiro elemento inserido será o último a ser retirado

LIFO
(last in – first out)
O último elemento inserido será o primeiro a ser retirado

Operações válidas
• PUSH
• insere elemento no topo da pilha
• POP
• remove elemento do topo da pilha
• Possível:
• Operação de consultar topo da pilha

Pilhas: como funcionam
• FILO

O
L
I
F

12

Pilhas: para que servem
• Desfazer (o salvador)
• Análise sintática de delimitadores
• Torres de Hanoi

Pilhas: como aplicar
• Utilizando arrays

TP

BS

0

LS

1

2

• BS (base): limite inferior do array • TP: topo da pilha
• LS: limite superior do array

3

4

5
•
•
•
•
•

6

7

TPLS: estouro da fila

Pilhas: como aplicar
• Utilizando Listas
• Inserir sempre ao final da lista
• lista.add( elemento )

• Remover sempre o último da lista
• lista.remove( lista.size() )

Tão simples!

Árvores
• Mais uma estrutura de dados extremamente utilizada
• Também presente em diversos sistemas
• Uma estrutura mais complexa e mais liberal
• Diversos tipos

Árvores: regras e operações
• Dependem do tipo da árvore
•