pilhas java
✩
´
ESTRUTURAS DE DADOS BASICAS
EM
JAVA
Jos´e de Siqueira
UFMG - ICEx - DCC
1o semestre de 2005
✫
✪
✬
✩
Estruturas de Dados B´asicas em Java
O Tipo Abstrato de Dados Pilha
• O TAD pilha tem quase as mesmas opera¸co˜es apresentadas anteriormente:
1. empilha(o): insere o objeto o no topo da pilha. Entrada: objeto. Sa´ıda: nenhuma.
2. desempilha(): retira o objeto no topo da pilha e o roetorna; ocorre erro se a pilha estiver vazia.
Entrada: nenhuma. Sa´ıda: objeto.
3. tamanho(): retorna o n´umero de objetos na pilha. Entrada: nenhuma. Sa´ıda: inteiro.
4. vazia(): Retorna um booleano indicando se a pilha est´a vazia.
Entrada: nenhuma. Sa´ıda: booleano.
5. topo(): Retorna o objeto no topo da pilha, sem retir´a-lo; ocorre um erro se a pilha estiver vazia. Entrada: nenhuma. Sa´ıda: objeto.
✫
Jos´e de Siqueira
1
✪
✬
✩
Estruturas de Dados B´asicas em Java
Uma interface para pilhas em Java
• Em Java, j´a existe a classe para o TAD pilha: java.util.Stack. • Os m´etodos dispon´ıveis nesta classe, entre outros, s˜ao: push(obj), pop(), equivalentes a empilha(o) e desempilha() e peek(), equivalente a topo(), tamanho() e vazia().
• Os m´etodos pop() e peek() lan¸cam a exce¸ca˜o
StackEmptyException se a pilha estiver vazia quando eles s˜ao chamados.
• Apesar de j´a existir esta classe em Java, aqui estamos interessados em aprender como projetar e implementar uma pilha e uma fila em Java.
• A implementa¸ca˜o de um TAD em Java envolve dois passos:
1. a defini¸ca˜o de uma API (Application
Programming Interface) que descreve os nomes dos m´etodos que o TAD oferece, como eles s˜ao declarados e como s˜ao usados.
2. uma ou mais implementa¸co˜es concretas dos m´etodos descritos na interface (API) associada com o TAD.
✫
Jos´e de Siqueira
2
✪
✬
✩
Estruturas de Dados B´asicas em Java
public interface Pilha {
/* retorna o n´ umero de itens na pilha */ public int tamanho();