Estrutura de dados - Pilhas (Stacks)

Pilhas

>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.  

Empilhar elementos

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

Verificar se pilha está vazia.

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  

Espiar topo da pia

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        

Empilhar elementos em uma pilha.

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