Created by Jorge Borges
about 5 years ago
|
||
>Classe Pilha Definição. Verificar quantidade de elementos na pilha. Empilhar elemento. Verificar se pilha está vazia. Espiar/ Verificar elemento topo da pilha. Desempilhar elemento da pilha. API Java Stack.
A estrura de dados pilhas tem uma mesma noção de pilhas da vida real. Pilha de pratos, pilha de livro, pilha de objetos. Pilhas estáticas - Utilização de um vetor ou array, para poder simular uma pilha. Mudança de diagrama: [ 5 ] 36 [ 4 ] 35 [ 3 ] 34 [ 2 ] 33 [ 1 ] 32 [ 0 ] 31 Quando precisamos empilhar colocamos o elemento no final da pilha. Empilhar e Desempilhar ou seja LIFO ( Last in First Out ) o último a entrar é o primeiro a sair. Vamos refatorar. ctrl + a / ctrl+i = identar o código.
LIFO - Last in First out Sempre adicionamos elementos no topo da pilha, ou seja, empilhamos. [5] 33 empinhado ( push) [4] 40 ( topo da pilha) [3] 42 [2] 41 [1] 43 [0] 32
Criamos uma nova classe base, chamada de EstruturaEstatica. Essa estrutura estática conterá todos as funções empregada na nova classe Pilha, ou seja, será uma super classe. public class EstruturaEstatica { protected T[] elementosNovos; protected T[] elementos; public int tamanho; public EstruturaEstatica ( int capacidade){ this.elementos = ( T[] ) new Object[capacidade]; this.tamanho = 0; } public boolean adiciona( T elemento) throws Exception{ this.aumenttaCapaciadade(); if( this.tamanho< this.elementos.length) { this.elementos[ this.tamanho] = elemento; this.tamanho++; return true; } else{ throw new Exception( " Espaço insuficiente.") } } public boolean adiciona( int posicao, T elemento){ this.aumentaCapacidade(); if( !( posicao>=0 && posicao throw new IllegalArgumentException( " Tamanho inválido"); } for( int i = this.tamanho-1; i< posicao; i--){ this.elementos[ i+1] = this.elementos[i]; } this.elementos[posicao] = elemento; this.tamanho++; return true; } public EstruturaEstatica() { // contrutor this(10); } public void aumentaCapacidade() { if( this.tamanho == this.elementos.length) { this.elementosNovos = (T[]) new Object[ this.telementos.length*2]; for( int i = 0; i< this.elementos.length; i++){ this.elementosNovos[i] = this.elementos[i]; } this.elementos = this.elementosNovos } } public int tamanho(){ retorn this.tamanho; } public String toString() { StringBuilder s = new StringBuilder(); s.append( " [" ); for( int j = 0 ; j< this.tamanho-1; j++){ s.append( this.elementos[ j] ); s.append( " , "); } if( this.tamanho>0){ s.append( this.elementos[ this.tamanho] -1) ; } s.append( " ]") return s.toString(); } } cod.: public class Pilha<T> extends EstruturaEstatica<T>{ public Pilha(){ super(); } public Pilha( int capacidade){ super( capacidade); } public void empilha( T elemento) throws Exception{ //this.aumentaCapacidade(); //this.elementos[tamanho++] = elemento; //this.tamanho++; super.adiciona( elemento); } } Este é o nosso refactoring, agora é mais simples de fazer modificações e refletir em outras classes. Como temos uma super classe, qualquer modificação feita nela as suas subclasses herdarão qualquer mudança nesse comportamento.
A estrutura de dados chamada pilha é muito utilizada em linguagem de programação, como C#, C++, Java, JS e etc. Todas essas linguagens utilizãm uma pilha interna quando for feita uma chamada de métodos existe uma pilha chamada de pilha de métodos, de variáveis locais... Existe uma exceção muito cohecidada a Stackoverflow, quando não existe mais capacidade e a pilha estoura. fonte: https://youtu.be/W1ii9DHFvrw?list=PLGxZ4Rq3BOBrgumpzz-l8kFMw2DLERdxi
Um Algoritmo simples de verificação de pilha: cod.: public boolean estaVazia(){ return this.tamanho == 0; } Vamos modificar a EstruturaEstatica, ao modifica-lo estaremos repassando as modificações para as subclasses. Desta forma para testa-lo temos: cod.: Pilhas pilha = new Pilhas; System.out.println (pilha.estaVazia); // true pilha.adiciona( "w"); System.out.println( pilha.estaVazia); // false fonte: https://youtu.be/LoNLVQegbC4?list=PLGxZ4Rq3BOBrgumpzz-l8kFMw2DLERdxi
Essse método é uma particularidade da classe pilha então não podemos generaliza-lo para classe base. Dica primeiro analise o problema e separe quais atributos ou variáveis chaves podemos distinguir. Para ai então codificar. cod.: public T topo(){ if(this.estaVazio){ return null; } return this.elementos[this.tamanho-1]; } Observe se pilha estiver vazia será impresso null para o usuário caso contrário será impresso do elemento que se encontra no topo da pilha. Sem ocorre adição ou remoção de elemento. Bem simples, para testarmos temos: cod.: public static void main(String[] args) throws Exception { Pilhas pilha = new Pilhas(); System.out.println(pilha.topo()); pilha.adiciona("J"); System.out.println(pilha.topo()); } fonte: https://youtu.be/1G0T4jYgz9A?list=PLGxZ4Rq3BOBrgumpzz-l8kFMw2DLERdxi
O último elemento que foi empilhado será o primeiro elemento a ser desempilhado. cod.: public T desempilha(){ /*T elemento = this.elemento[ this.tamanho-1]; this.tamanho--; return elemento; */ return this.elementos[ --this.tamanho ]; } Podemos termos mais de uma possibilidade de implementar um código, como vemos. fonte: https://youtu.be/Oo_Wq8vxMNc?list=PLGxZ4Rq3BOBrgumpzz-l8kFMw2DLERdxi
Want to create your own Notes for free with GoConqr? Learn more.