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.

Pilhas em Java
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. 1° entrega: Portuguesa
  2. 2° entrega: Frango com catupiry
  3. 3° entrega: Calabresa
  4. 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.