Pilhas: Fundamentos e implementa��o da estrutura em Java

Uma quest�o importante no estudo da computaç�o � o entendimento das estruturas de dados, dentre as quais temos filas, pilhas, listas ligadas, entre outras. Vamos entender aqui o funcionamento das pilhas e como implementar uma pilha simples em Java.

O que � uma estrutura de dados?

A estrutura de dados � o coraç�o de diversos programas bem elaborados, saber qual tipo de estrutura utilizar � essencial para construir um aplicativo de qualidade. A estrutura de dados � na verdade a forma de organizar e armazenar informaç�es para que estas possam posteriormente ser utilizadas de modo eficiente.

O que � uma pilha?

A pilha � uma das estruturas de dados e trabalha com o formato LIFO (o �ltimo a entrar � o primeiro a sair, �Last In, First Out�, em ingl�s). Lembre-se da pilha como uma pilha de livros, em que o primeiro livro que foi inserido na pilha, normalmente � o �ltimo que sai dela, enquanto o �ltimo adicionado � o primeiro a ser retirado, como vemos na Figura 1.

Figura 1. Pilhas em Java

A estrutura da pilha, segundo Farias �s�o estruturas de dados do tipo LIFO (last-in first-out), onde o �ltimo elemento a ser inserido, ser� o primeiro a ser retirado. Assim, uma pilha permite acesso a apenas um item de dados - o �ltimo inserido. Para processar o pen�ltimo item inserido, deve-se remover o �ltimo�.

A pilha � considerada uma estrutura de dados simples, sendo f�cil de implementar. Em uma an�lise simples, poderia ser utilizada, por exemplo, em um carregamento de um caminh�o, pois se o caminh�o tiver 4 entregas, a �ltima entrega colocada dentro do caminh�o deve ser a primeira a sair, caso contr�rio, pode dar mais trabalho para descarregar.

Um outro caso de pilha simples de se entender � o caso do entregador de pizza.

O entregador deve entregar tr�s pizzas em locais diferentes, se ele colocar na ordem de entrega, o que vai ocorrer � que a primeira pizza colocada no ba� � a primeira pizza a ser entregue, de forma que todas as outras pizzas est�o sobre a primeira pizza, ent�o qual a melhor l�gica?

Mudar a ordem: a primeira pizza no ba� deve ser a �ltima a ser entregue e a �ltima pizza do ba�, a primeira a ser entregue. Neste caso, ao chegar na casa do cliente, o entregador apenas pega a primeira pizza que est� no ba� e entrega ao cliente.

Este exemplo foi proposto inicialmente por Takai, apresentando uma rota de entrega de quatro pizzas, sendo a seguinte ordem:

1� entrega: Portuguesa
2� entrega: Frango com catupiry
3� entrega: Calabresa
4� entrega: Quatro queijos

Assim, para armazenar no ba�, a ordem deve ser invertida, ficando da seguinte forma:

Portuguesa (topo do ba�)
Frango com catupiry
Calabresa
Quatro queijos

Para as tarefas temos: a criaç�o da pilha, o empilhamento - push (ato de colocar uma caixa de pizza sobre a outra), o ato de desempilhar - pop (na hora que o entregador tira a caixa de pilha para entregar ao cliente), al�m de uma verificaç�o se a pilha est� cheia ou vazia (ato que o entregador faz ao verificar o ba�).

Implementando nossa pilha em Java

Primeiramente, vamos criar um array para armazenar nossa pilha. Imaginando o ba�, temos uma capacidade de 10 pizzas, por exemplo, j� um caminh�o, dependendo do tamanho dele e da quantidade de produtos a serem entregues, pode armazenar de 1 a centenas de entregas, e assim por diante. Em nosso caso, primeiro vamos criar o array, depois vamos definir um tamanho de teste para 10 itens em nossa pilha, como mostra a Listagem 1.

public Object[] pilha;

Listagem 1. Declarando o array

Foi utilizado o tipo Object para armazenar textos ou n�meros, uma forma mais gen�rica, apenas como teste de pilha, como mostra a Listagem 2.

public int posicaoPilha;

Listagem 2. Vari�vel para armazenar a posiç�o atual na pilha

Aqui foi criado uma vari�vel que exibe a posiç�o atual na pilha, se a posiç�o for 10, ent�o chegamos ao topo da pilha e n�o poder�o ser inseridos mais itens.

Agora na Listagem 3 o construtor ser� definido o tamanho da pilha e inicializado a posiç�o.

public Pilha() {
  this. posicaoPilha = -1;
// indica que esta nula, vazia, pois a posiç�o zero
//do array j� armazena informaç�o 
        this.pilha = new Object[10]; // criando uma pilha com 10 posiç�es
}

Listagem 3. Inicializando a pilha

Agora vamos criar uma funç�o que verifique se a pilha est� vazia (isEmpty). Observe a Listagem 4.

public boolean pilhaVazia() {
        if (this. posicaoPilha == -1) {
            return true; 
  // Verifica que o atributo posicaoPilha � igual a -1,
  //se for, a pilha � nula, ou seja, ainda esta vazia,
  //retornando verdadeiro.
        }
        return false;
}

Listagem 4. Funç�o para verificar se a pilha est� vazia

Agora � necess�rio verificarmos qual o tamanho da pilha atual, ou seja, o entregador olha quantas pizzas ainda tem dentro do ba� para entregar, como mostra a Listagem 5.

public int tamanho() {
        if (this.pilhaVazia()) {
            return 0; // aqui indica que n�o tem nenhum conte�do dentro da pilha
        }
        return this. posicaoPilha + 1;
  // aqui indica quantos itens tem dentro da pilha, somando-se 1, 
  //pois a pilha inicia no zero. Logo, se tivermos 3 itens na pilha,
  // o atributo posicaoPilha vai exibir 2.
  //Para sabermos quantos itens h�, precisamos somar um.
}

Listagem 5. Funç�o que retorna a quantidade de itens na pilha

Agora � necess�rio um m�todo para empilhar itens dentro da pilha, ou seja, a forma que o entregador pega a pizza e insere sobre a �ltima pizza que est� no ba�, como vemos na Listagem 6.

public void empilhar(Object valor) {
        // push
        if (this. posicaoPilha < this.pilha.length - 1) { 
  // verifica se a posicaoPilha � menor do que o tamanho da pilha,
  //se for, ent�o � inserido o valor na pilha e ao mesmo tempo � feito
  //o incremento do atributo posicaoPilha
            this.pilha[++posicaoPilha] = valor;
        }
}

Listagem 6. Funç�o para empilhar itens

Depois de criada uma forma de empilhar, temos de desempilhar, ou seja, hora de o entregador retirar a pizza do ba� e entregar ao cliente, como mostra a Listagem 7./p>

public Object desempilhar() {
        //pop
        if (pilhaVazia()) {
            return null;
  // primeiro verificamos se a pilha esta vazia,
  //se estiver, nada ser� realizado
        }
        return this.pilha[this. posicaoPilha --];
  // aqui retorna o que tem na �ltima posiç�o da pilha
  //e decrementa o atributo posicaoPilha
}

Listagem 7. Funç�o para remover itens da lista

Na Listagem 8 vamos ver o resultado da pilha completa em funcionamento.

public class Pilha {
    
    public Object[] pilha;
    public int posicaoPilha;

    public Pilha() {
        this.posicaoPilha = -1;
// indica que esta nula, vazia, pois posiç�o um indica que cont�m informaç�o
        this.pilha = new Object[1000];
// criando uma pilha com 1000 posiç�es
    }

    public boolean pilhaVazia() {
        //isEmpty
        if (this.posicaoPilha == -1) {
            return true;
        }
        return false;
    }

    public int tamanho() {
        //is
        if (this.pilhaVazia()) {
            return 0;
        }
        return this.posicaoPilha + 1;
    }

    public Object exibeUltimoValor() {
        //top
        if (this.pilhaVazia()) {
            return null;
        }
        return this.pilha[this.posicaoPilha];
    }

    public Object desempilhar() {
        //pop
        if (pilhaVazia()) {
            return null;
        }
        return this.pilha[this.posicaoPilha--];
    }

    public void empilhar(Object valor) {
        // push
        if (this.posicaoPilha < this.pilha.length - 1) {
            this.pilha[++posicaoPilha] = valor;
        }
    }

    public static void main(String args[]) {
        Pilha p = new Pilha();
        p.empilhar("Portuguesa ");
        p.empilhar("Frango com catupiry ");
        p.empilhar("Calabresa ");
        p.empilhar("Quatro queijos ");
        p.empilhar(10);
                while (p.pilhaVazia() == false) {
            System.out.println(p.desempilhar());
        }
    }
}

Listagem 8. Pilha completa em funcionamento

Pronto, a pilha est� funcionando. Nosso entregador pode empilhar e desempilhar as pilhas sem maiores problemas.

Conclus�o

A pilha � uma estrutura simples de ser implementada. Apesar de algumas limitaç�es, pode ser utilizado para diversos fins, como sistemas de log�sticas, por exemplo.

Pilhas: Fundamentos e implementa��o da estrutura em Java

Veja neste artigo os fundamentos da estrutura de dados pilha (LIFO), bem como a implementação de uma pilha simples em Java.

O que � uma estrutura de dados?

O que � uma pilha?

Implementando nossa pilha em Java

Conclus�o

Artigos relacionados