Videolivro 2 - pilhas com uso de vetores

1. Apresentação

Os vetores ou arranjos (autores diferentes preferem uma nomenclatura ou outra), possuem uma implementação relativamente simples, pois precisam de um espaço de memória de tamanho definido. Na linguagem de programação Java, diferentemente do que acontece em linguagens como o Pascal que permite criar seus índices, um vetor começa com a posição 0. Assim, um vetor de 10 elementos possui a posição 0 até a posição 9.

Neste livro vamos implementar pilhas com o uso de vetores.

2. Pilhas

A pilha é uma estrutura na qual o último elemento que entra é o primeiro que sai. O termo em inglês utilizado para essa situação é Last In First Out (LIFO).

A figura a seguir ilustra uma estrutura deste tipo. Nela, temos uma pilha de livros sobre uma mesa da biblioteca, que recém foram devolvidos, à espera de serem recolocados na estante. O último livro a ser colocado sobre a pilha, "Programação Java para Web" será o primeiro a sair, no momento em que a bibliotecária for colocá-los na estante novamente.

Em programação, podemos enxergar essa pilha como sendo um vetor, na qual o primeiro elemento inserido, o livro "Engenharia de Software" ocupa a posição 0, enquanto o livro "Sistemas operacionais modernos" a posição 1 e assim por diante, conforme figura a seguir:

Temos então um vetor do tipo String com 5 posições:

2.1. A classe Pilha

Como exemplo, utilizaremos a classe Pilha proposta por Puga e Risseti (2016, p. 188):

public class Pilha {
	int tamanho;
	int topo;
	Object vetor[];
	Pilha (int tam){
		topo = -1;
		tamanho = tam;
		vetor = new Object[tam];
	}

}

1) Sobre as variáveis da classe Pilha

tamanho vai ser utilizada para definir o tamanho do vetor.

topo é para controlar o último elemento do vetor.

vetor é o próprio vetor de conteúdos.

2) Sobre o construtor da classe

Observe que o construtor da classe recebe como parâmetro o tamanho do vetor. Assim, quando um objeto for instanciado ele deve informar o tamanho do vetor.

Para o nosso exemplo anterior do vetor vetLivros, com 5 livros empilhados, o objeto pode ser assim instanciado:

2.2. Os métodos (funções) pilhaVazia () e pilhaCheia ()

Se você tem dúvidas sobre como criar funções, veja o vídeo:

Como você viu no construtor da classe Pilha, fizemos o topo receber -1 (menos 1) para indicar que a pilha está vazia.  Por esse motivo, a função pilhaVazia() retornará true (verdadeiro) caso o tipo seja igual a -1 e false caso contrário. Vejamos:

public boolean pilhaVazia() {
	if (topo == -1)
		return true;
	else
		return false;	
}

Vejamos:

public boolean pilhaCheia() {
	if (topo == tamanho - 1)
		return true;
	else
		return false;
}

Essas funções serão necessárias quando quisermos empilhar elementos (testar antes se a pilha está cheia) ou desempilhar elementos (testar se a pilha já está vazia), que abordaremos na próxima seção.

2.3. Empilhar elementos

Se a pilha não estiver cheia, podemos empilhar.

Os passos para empilhar são os seguintes:

Se a pilha não estiver cheia (usaremos a função pilhaCheia() para testar)
   1) somar mais um no topo; 
   // lembra-se que o topo no construtor começa com - 1? Isso porque o primeiro elemento então passará a ser o de posição 0 
   2) armazenar na posição topo do vetor o elemento lido;
senão
             1) enviar mensagem que a pilha está cheia.
fimse;

public void empilhar (Object elemento) {
	if (!pilhaCheia()) 
	{
		topo++;
		vetor[topo]= elemento;		
	}
	else
		JOptionPane.showMessageDialog(null, "Pilha Cheia");
}

Agora que temos o método empilhar, antes de ver o método contrário, que será desempilhar, que tal implementarmos o método para mostrar a pilha?

Mas, ainda antes disso, vamos criar nosso programa Principal que utiliza a classe Pilha para podermos empilhar. 

Este é o assunto da próxima seção.

2.4. O programa Principal

No programa Principal vamos instanciar o objeto vetLivros para empilhar nossos 5 livros apresentados no início deste capítulo.

import javax.swing.JOptionPane;

public class Principal {

	public static void main(String[] args) {
		//vamos criar o vetor para nossa pilha de 5 livros
		Pilha vetLivros = new Pilha (5);
		int cont;
		String nomeLivro;
		
		for (cont=0; cont<5; cont++) {
			nomeLivro = JOptionPane.showInputDialog("Nome do livro: ");
			vetLivros.empilhar(nomeLivro);
		}
		
				
	}

}

2.5. O método mostrarPilha()

Utilizaremos o método mostrarPilha() proposto por Puga e Risseti (2016, p. 192):

Note que não há nada de novo em relação ao que já aprendemos anteriormente sobre como percorrer e imprimir um vetor.

O principal aspecto a ser observado é que percorremos do final para o início, já que se trata de uma pilha (ÚLTIMO A ENTRAR, PRIMEIRO A SAIR).

public void mostrarPilha() {
	int cont;
	String mensagem = "";
	if (!pilhaVazia()) {
		for (cont=topo; cont>=0; cont--) {
			mensagem = mensagem + vetor[cont] + " ! ";
		}
	}
	else
	{
		mensagem = "Pilha vazia";
	}
	JOptionPane.showMessageDialog(null, mensagem); 
}

import javax.swing.JOptionPane;

public class Principal {

	public static void main(String[] args) {
		//vamos criar o vetor para nossa pilha de 5 livros
		Pilha vetLivros = new Pilha (5);
		int cont;
		String nomeLivro;
		
		for (cont=0; cont<5; cont++) {
			nomeLivro = JOptionPane.showInputDialog("Nome do livro: ");
			vetLivros.empilhar(nomeLivro);
		}
		
		vetLivros.mostrarPilha();
	}

}

2.6. O método desempilhar ()

Como se trata de uma pilha, o método desempilhar() não recebe parâmetros, porque sempre será desempilhado o último elemento da pilha.

Assim, uma variável deverá receber o valor do topo, para que seja mostrado ao usuário qual o valor desempilhado e, em seguida, o topo recebe - 1 (menos 1).

Vejamos:

public void desempilhar() {
	Object valorDesempilhado = null;
	String mensagem = "Valor desempilhado = ";
	if (pilhaVazia())
		JOptionPane.showMessageDialog (null, "Pilha vazia");
	else
	{
		valorDesempilhado = vetor[topo];
		mensagem = mensagem + valorDesempilhado;
		topo--;
	}
	JOptionPane.showMessageDialog(null, valorDesempilhado);
}

2.7. O programa Principal novamente

Agora vejamos nosso programa Principal com os 5 valores e desempilhando o último:

import javax.swing.JOptionPane;

public class Principal {

	public static void main(String[] args) {
		//vamos criar o vetor para nossa pilha de 5 livros
		Pilha vetLivros = new Pilha (5);
		int cont;
		String nomeLivro;
		
		for (cont=0; cont<5; cont++) {
			nomeLivro = JOptionPane.showInputDialog("Nome do livro: ");
			vetLivros.empilhar(nomeLivro);
		}
		
		vetLivros.mostrarPilha();
		vetLivros.desempilhar();
		vetLivros.mostrarPilha();
		
	}

}

Finalizamos assim o estudo das pilhas com o uso de vetores.