TAD Pilha
ATAI
1
Teória de Tipos de Dados Abstractos
1.
Definição de TAD
 Especificar as propriedades fundamentais de um tipo de dado,
de um modo independente da sua implementação numa
linguagem.
2.
Implementação de TAD em JAVA
 Passo1: Definição da Interface
Descrição os nomes dos métodos que o TAD suporta e como
eles são declarados e usados

Passo2: Escolha da representação concreta do TAD
Decisão: Estrutura estática ou dinâmica.

Passo3: Implementação da interface
Uso do mecanismo de classes
2
Definição de TAD Pilha
3
Definição do TAD Pilha (linguagem natural)

Uma pilha é um contentor de objectos que são inseridos e removidos de
acordo com o princípio último-a-entrar-primeiro-a-sair (UEPS) ou lastin-first-out (LIFO)

Objectos podem ser inseridos na pilha a qualquer altura, mas apenas o
inserido mais recentemente (o último) pode ser removido a qualquer
altura

O nome pilha deriva de uma analogia com uma pilha de pratos

As operações fundamentais são empilhar (pushing) e desempilhar
(popping) pratos da pilha

Pilhas são fundamentais e são usadas em muitas aplicações, tais como:


Os navegadores Web que armazenam os endereços das páginas
mais recentemente visitadas numa pilha
Os editores de texto que disponibilizam mecanismo de "desfazer"
(undo), normalmente mantêm armazenadas numa pilha as mudanças
de textos ocorridas
4
Definição do TAD Pilha (linguagem formal)

Uma pilha P é um tipo abstracto de dados (TAD) que suporta os
seguintes métodos fundamentais:

empilha(o): Insere o objecto o no topo da pilha
Entrada: Objecto; Saída: Nenhuma

desempilha(): Remove e retorna o objecto do topo da pilha - um erro
ocorre se a pilha está vazia
Entrada: Nenhuma; Saída: Objecto

Adicionalmente temos os seguintes métodos:

tamanho(): Retorna o número de objectos na pilha
Entrada: Nenhuma; Saída: Inteiro

estaVazia(): Retorna um valor booleano indicando se a pilha está vazia
Entrada: Nenhuma; Saída: Booleano

topo(): Retorna o objecto do topo da pilha, sem removê-lo - um erro
ocorre se a pilha está vazia
Entrada: Nenhuma; Saída: Objecto
5
Definição do TAD Pilha (exemplo1)

Ilustração (Pilha de Livros):
Inicalmente:
Rob Roy
War & Peace
Moby Dick
Após remover
um livro:
War & Peace
Moby Dick
Após inserir”:
Misérables
War & Peace
Moby Dick
Após inserir
2001”:
2001
Misérables
War & Peace
Moby Dick
6
Definição do TAD Pilha (exemplo2)
Saída
P
empilha(5)
-
(5)
empilha(3)
-
(5,3)
Desempilha( )
3
(5)
empilha(7)
-
(5,7)
Desempilha( )
7
(5)
topo( )
5
(5)
Desempilha( )
5
()
Desempilha( )
"erro"
()
estaVazia( )
verdade
()
empilha(9)
-
(9)
empilha(7)
-
(9,7)
empilha(3)
-
(9,7,3)
empilha(5)
-
(9,7,3,5)
tamanho( )
4
(9,7,3,5)
Desempilha( )
5
(9,7,3)
Operação
7
Implementação de TAD Pilha
8
Passo1: Definição da Interface Pilha
public interface Pilha {
//Métodos selectores
public int tamanho( );
public boolean estaVazia( );
public Object topo( ) throws PilhaVaziaException;
//Métodos de actualização
public void empilha( Object elemento ) throws PilhaCheiaException;
public Object desempilha()
throws PilhaVaziaException;
}
9
Implementação de TAD Pilha
Passo 2
(com a utilização da estrutura estática)
10
Passo2: Escolha da representação concreta do
TAD (cont)

A implementação de uma pilha através de um array é simples e eficiente
porém, esta implementação tem um aspecto negativo: tem que assumir um
limite máximo definitivo N para o tamanho da pilha

Esta implementação funciona bem quando podemos prever o número de
itens a serem colocados na pilha

Existem outras implementações para pilha, que não impõem este limite

Mesmo assim, pilhas têm um papel vital em um grande número de
aplicações de computação e é sempre útil ter uma implementação rápida
do ADT pilha, baseada em array
11
Passo2: Escolha da representação concreta do
TAD Pilha
Implementação Baseada em Array:




Podemos implementar uma pilha utilizando um array para
armazenamento de seus elementos
Como o tamanho de um array deve ser determinado na sua criação,
temos que especificar o tamanho máximo N para a pilha (p.e.: N = 1.000
elementos)
A pilha consiste: um array P de N elementos mais uma variável inteira t
que dá o índice do elemento do topo da pilha no array P
Já que array de Java começam com índice 0, inicializaremos t com
-1 e lançaremos uma exceção PilhaCheiaException para sinalizar
que não existe mais espaço disponível no array para inserções
12
Passo2: Escolha da representação concreta do
TAD Pilha (algoritmos)
Algoritmo tamanho( ):
retorna t + 1
Algoritmo estaVazia( ):
Algoritmo empilha( o ):
se tamanho( ) = N então
lança PilhaCheiaException
t <- t + 1
P[ t ] <- o
retorna t < 0
Algoritmo topo( ):
se estaVazia( ) então
lança
PilhaVaziaException
retorna P[ t ]
Algoritmo desempilha( ):
se estaVazia( ) então
lança PilhaVaziaException
e <- P[ t ]
P[ t ] <- null
t <- t - 1
retorna e
13
Passo3: Implementação da interface (cont)
public class PilhaArray implements Pilha {
public static final int CAPACIDADE = 1000; // Capacidade por defeito
private int capacidade; // Capacidade máxima da pilha
private Object p[ ]; // p armazena os elementos da pilha
private int topo = -1; // O elemento do topo da pilha
public PilhaArray ( )
// Inicializa a pilha com a capacidade default
{
this( CAPACIDADE );
}
public PilhaArray( int cap ) // Inicializa a pilha com uma dada capacidade
{
capacidade = cap;
p = new Object[ capacidade ];
}
14
Passo3: Implementação da interface (cont)
public int tamanho( ) { //Retorna o tamanho atual
return( topo + 1 );
// da pilha
}
public boolean estaVazia( ) { // Retorna true se a
return( topo < 0 );
// pilha está Vazia
}
public void empilha( Object obj ) // Empilha um
throws PilhaCheiaException { // novo objeto
if( tamanho( ) == capacidade ) // na pilha
throw new PilhaCheiaException(
“Overflow da pilha.”);
p[ ++topo ] = obj;
}
public Object topo( )
// Retorna o
throws PilhaVaziaException { // elemento do
if( estaVazia( ) )
// topo da pilha
throw new PilhaVaziaException(“Pilha esta vazia.”);
return p[ topo ];
}
15
Passo3: Implementação da interface
public Object desempilha( ) // Desempilha o elemento do topo da pilha
throws PilhaVaziaException {
if( estaVazia( ) )
throw new PilhaVaziaException(“Pilha esta vazia.”);
Object elem = p[ topo ]; // Referência auxiliar
p[ topo-- ] = null; // Desfaz a referência P[topo] e decrementa topo
return elem;
}
}
16
Casting numa Pilha Genérica

Um dos pontos fortes da realização de um TAD pilha por meio de uma
classe Java que implementa a interface Pilha, é que podemos armazenar
objectos genéricos, cada um pertencendo a uma classe diferente

Temos que ter cuidado para que sejamos consistentes porque os objectos
armazenados são vistos como instâncias da classe Object - sempre que
recuperamos um objecto da pilha ele é uma instância da classe Object

Para usar o objecto recuperado como instância da classe específica a que
ele realmente pertence, temos que fazer uso de um modificador de tipo
(cast) que força que o objecto seja visto como um membro específico
daquela classe
17
Exemplo de utilização
Problema:
Solução:
Atenção:
Inverter a ordem dos elementos de um array
Utilização um objecto auxiliar tipo Pilha
Necessidade de usar modificador de tipo (cast):
public static Integer[ ] inverte( Integer[ ] a ) {
Pilha s = new PilhaArray( a.length );
Integer[] b = new Integer[ a.length ];
for( int i = 0; i < a.length; i++ ) {
s.empilha( a[ i ] );
}
for( int i = 0; i < a.length; i++ ) {
b[ i ] = ( Integer )( s.desempilha( ) );
}
return b;
}
18
Pilha em Java

Pela sua importância, a estrutura de dados pilha foi incluída como
uma classe do pacote java.util de Java (Stack)

Stack é uma estrutura de dados que armazena objectos genéricos
e inclui, entre outros, os métodos push(obj), pop(), peek()
(equivalente a top()), size() e empty()

Os métodos peek() e pop() lançam a excepção
StackEmptyException se forem chamados com a pilha vazia
19
Implementação de TAD Pilha
Passo 2
(com a utilização da estrutura dinâmica)
(lista simplesmente ligada)
20
Passo2: Escolha da representação concreta do
TAD Pilha

As inserções e remoções serão feitas na cabeça da
lista, pois assim estas operações terão o tempo O(1) - o
topo da pilha será a cabeça

Para que a operação tamanho() seja realizada no
tempo O(1), o número de elementos actuais será
mantido numa variável de instância
21
Passo3: Implementação da interface
public class PilhaLista implements Pilha {
// Referência para o no do topo
private No topo;
// Número de elementos na pilha
private int tamanho;
public PilhaLista ( ) { // Inicializa a pilha
topo = null;
tamanho = 0;
}
public int tamanho( ) { //Retorna o tamanho actual
return tamanho;
// da pilha
}
public boolean estaVazia( ) { // Retorna true se a
if( topo == null )
// pilha está vazia
return true;
return false;
}
22
Passo3: Implementação da interface
public void empilha( Object obj ) {
No n = new No( );
n.setElemento( obj );
n.setProximo( topo );
topo = n;
tamanho++;
}
// Empilha um
// novo objecto
// na pilha
public Object topo( )
// Retorna o
throws PilhaVaziaException { // elemento do topo
if( estaVazia( ) )
// da pilha
throw new PilhaVaziaException();
return topo.getElemento( );
}
23
Passo3: Implementação da interface
public Object desempilha( )
// Desempilha o
throws PilhaVaziaException { // elemento do topo
Object temp;
// da pilha
if( estaVazia( ) )
throw new PilhaVaziaException();
temp = topo.getElemento( );
topo = topo.getProximo( ); // desliga o no do topo
tamanho--;
return temp;
}
}
24
Classe PilhaVaziaExceptions
public class PilhaVaziaException extends RuntimeException
{
public PilhaVaziaException ()
{
super(“Pilha esta vazia”);
}
}
25
Exemplo de utilização
Problema:
Solução:
Atenção:
Inverter a ordem dos elementos de um array
Utilização um objecto auxiliar tipo Pilha
Necessidade de usar modificador de tipo (cast):
public static Integer[ ] inverte( Integer[ ] a ) {
Pilha s = new PilhaLista();
Integer[] b = new Integer[ a.length ];
for( int i = 0; i < a.length; i++ ) {
s.empilha( a[ i ] );
}
for( int i = 0; i < a.length; i++ ) {
b[ i ] = ( Integer )( s.desempilha( ) );
}
return b;
}
26
Exemplo de utilização
Avaliação de Expressões
Na notação polaca invertida (NPI) os operandos aparecem antes do operador
(postfix.)
Regras:
1) Operandos aparecem da esquerda-para-diretira tal como na notação infix
2) Operações seguem em seguida dos operandos.
Exemplos
Infix
NPI
7-3
7, 3, -
8*4+5
8, 4, *, 5, +
1 + (2*3) - 4
1, 2, 3, *, +, 4, -
((9+8)*7)-(6*(5+(4/3)))
9,8,+,7,*,6,5,4,3,/,+,*,27
Exemplo de utilização
Avaliação de Expressões
Percorre a expressão da esqueda para direita, e para…
Para cada operando - push
Para cada operador – susbtituiu os dois últimos operando pelo resultado da
operação
(Nota: topo do stack é o operando direito, o segundo é esquerdo.)
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
StackOper
28
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
9
StackOper
29
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 8
9
StackOper
30
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
17
StackOper
31
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 7
17
StackOper
32
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
119
StackOper
33
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 6
119
StackOper
34
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 5
6
119
StackOper
35
Exemplo de utilização
Avaliação de Expressões
Exemplo
4
5
6
119
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
StackOper
36
Exemplo de utilização
Avaliação de Expressões
Exemplo
3 9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 4
5
6
119
StackOper
37
Exemplo de utilização
Avaliação de Expressões
Exemplo
1
5
6
119
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
StackOper
38
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 6
6
119
StackOper
39
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, 36
119
StackOper
40
Exemplo de utilização
Avaliação de Expressões
Exemplo
9, 8, +, 7, *, 6, 5, 4, 3, /, +, *, -
83
StackOper
41