Estrutura de dados - pilhas e filas

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1582 palavras )
  • Download(s) : 0
  • Publicado : 8 de janeiro de 2013
Ler documento completo
Amostra do texto
Estruturas de Dados em Java Pilha e Fila
Crédito: Prof. Gilbert Azevedo Adaptações: Prof. Jailton Carlos Jailton.paiva@ifrn.edu.br
19/10/2010 1

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

19/10/2010

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çõesde 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 onú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 umaoperaçã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 estruturade 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 intsize(); 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 = newStack();

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

1
14 19/10/2010

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

o Inserindo 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();
4

Lanç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 =...
tracking img