Estrutura de dados

OBJETIVO DA AULA DE HOJE
Compreender e aplicar os conceitos de Pilha e Fila em Java

2

Boxing e Unboxing
• Ao inserir um inteiro num ArrayList, é executado um boxing • Da mesma forma, quando este valor é lido, um unboxing é necessário.
ArrayList Lista = new ArrayList(); int i = 1; Lista.Add(i); int j = (int)Lista[0];

Todo esse procedimento gera um overhead, que degrada a performance dos aplicativos

3

19/10/2010

4

Pilha
• Contêiner onde objetos são inseridos e retirados de acordo com o princípio:
– “o último que entra é o primeiro que sai” – LIFO – Last In, First Out

19/10/2010

5

Aplicações de Pilha
• Aplicações diretas
– Histórico de páginas visitadas em um navegador – Seqüência de desfazer em um editor de textos – Cadeia de chamada de métodos em um programa

• Aplicações indiretas
– Estrutura de dados auxiliares para algoritmos

Pilhas e Filas

6

Tipo Abstrato de Dados (TAD)
• Um TAD é uma abstração de uma estrutura de dados • Um TAD especifica:
– Dados armazenados – Operações realizadas sobre os dados – Condições de erros associadas às operações

• O TAD Pilha armazena objetos genéricos

Pilhas e Filas

7

Pilha - Operações
• Principais
– push(object): insere um elemento na pilha – object pop(): remove e retorna o último elemento inserido

• Auxiliares
– object top(): retorna o último elemento inserido sem removê-lo – integer size(): retorna o número de elementos armazenados – boolean isEmpty(): indica se há ou não elementos na pilha

Pilhas e Filas

8

Pilha de Inteiros
Operação Saída Início – Pilha – Fim

push(5) push(3) 5
5, 3

pop() push(7) 3 2
7

5
5, 7

size() pop() 5, 7
5

top() pop() 5
5

5
-

pop() isEmpty() Erro
True
Pilhas e Filas

9

Pilha - Exceções
• Ao executar uma operação em um TAD, podemos causar uma condição de erro, que chamamos exceção • Exceções podem ser levantadas (thrown) por uma operação que não pode ser executada