Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1555 palavras )
  • Download(s) : 0
  • Publicado : 3 de junho de 2013
Ler documento completo
Amostra do texto
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 aperformance 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 emum 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• No TAD Pilha, as operações pop e top não podem ser realizadas se a pilha estiver vazia • Executar pop ou top em uma pilha vazia causa a exceção StackEmptyException
Pilhas e Filas 10

Pilha em Java
• Por sua importância, a estrutura de dados Pilha é uma classe “embutida” no pacote java.util • A classe java.util.Stack é uma estrutura de dados que armazena objetos Java genéricos e inclui,entre outros, os métodos:
– push(obj), pop(), peek(), size() e empty()

• Contudo, é importante, aprender como implementar uma pilha desde o início

Pilhas e Filas

11

Interface Pilha em Java
public interface Stack {
public int size(); public boolean isEmpty(); public Object top() throws StackEmptyException; public void push(Object o); public Object pop() throws StackEmptyException;

}Pilhas e Filas

12

Classe Stack
o Declarando
• Stack pilha = new Stack();

o Inserindo elementos
• pilha.push(1);
Inserção ocorre no topo da pilha

1

13

19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack();

o Inserindo elementos
• pilha.push(1); • pilha.push(2);
2

1
14 19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack();

oInserindo elementos
• pilha.push(1); • pilha.push(2); • pilha.push(3);
3

2
1
15 19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack();

o Inserindo elementos
• • • • pilha.push(1); pilha.push(2); pilha.push(3); pilha.push(4);
4

3

2
1
16 19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack();

o Removendo elementos
• int item = pilha.pop();
4Lança a exceção StackEmptyException, se a pilha estiver vazia

4
3

Remoção ocorre no topo da pilha

2
1
17 19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack ();

o Removendo elementos
• int item = pilha.pop(); • int item = pilha.pop();
3

3

2
1
18 19/10/2010

Classe Stack
o Declarando
• Stack pilha = new Stack();

o Recuperando elementos sem...
tracking img