Stack (Pilha)

JavaBaby Membro desde: 19/03/2007 14:12:59 Mensagens: 81 Offline

Galera,
ainda não consegui fazer meu teste com a classe Stack (Pilha)..

postei o código aqui.. mais nao resolveu:

http://www.guj.com.br/posts/list/54997.java#288665

Alguem poderia me mostrar um exemplo??

é importante.. nem que seja pequeno...

This message was edited 1 time. Last update was at 02/04/2008 08:02:54

Quando for pensar na 3estrutura de dados pilha, pense em uma pilha de pratos: Quando vc quer colocar mais um prato na pilha de pratos, você coloca o novo prato no topo da pilha, e se você que tirar um prato, você o retira também do topo da pilha.
Perceba que em um pilha, seja do que for, a primiera "coisa" que você coloca na pilha, é sempre a última a sair. Daí, chamamarmos pilhas de FILO (First In, Last Out - Primiero que entra, último que sai). Isso é uma característica importante das pilhas. Não vou entrar aqui a fundo na aplicabilidade desta propriedade, mas posso te dizer que ela é muito importante na computação para, por exemplo, os computadores tratarem métodos recursivos.
Basicamente, uma pilha é como uma lista que so recebe/retira elementos a partir de sua ponta. Basta imaginar essa lista "de pé"

As operações básicas de uma pilha são:

push: Adiciona um elemento ao topo da pilha

pop: Retira o elemento que está atualmente no topo da pilha, (se houver algum elemento no topo da pilha)

size: Informa o número de elementos atualmente armazenados na pilha
Você também pode adicionar alguns métodos conforme achar conveniente. Geralmente, por exemplo, vemos pilhas por aí com um método chamado peek, que serva para "espiar" o elemento que está no topo da pilha (Como o pop, mas sem efetivamente remever o elemento da pilha), e clear, que serviria para excluir todos os elementos da pilha, para "zerar" a pilha.
Vamos a uma implementaçãozinha bem básica. Vamos fazer uma pilha de tamanho fixo, que armazena objetos do tipo String.
A capacidade da nossa pilha será indicada no momento em que ela for instanciada, via construtor. Vamos utilizar, internamente, um vetor de Strings para armazenar os elementos e um int para sabermos quantos elementos estão armazenados na nossa pilha.

/**
 * @author luciano.mantuaneli
 * @date 01/04/2008
 */
package br.com.mantu.help.guj.zagaia.stack;

/**
 * @author luciano.mantuaneli
 * @date 01/04/2008
 */
public class SimpleStack {
	/** 
	 * Vetor de String que armazenará os elementos. 
	 * Se uma posição estiver nula, esta posição será encarada como uma posição 
	 * vazia na pilha. Sendo assim, nunca poderá existir uma posição vazia  
	 * seguida de uma posição não-vazia(diferente de null), pois isso indicaria  
	 * que, de alguma forma, removemos algum elemento da pilha que não o do topo. 
	 */  
	private String[] elements;  
	/** 
	 * inteiro que indicará quantos elementos NÃO NULOS existem dentro de  
	 * elements. Note por exemplo que: 
	 * -Se size for igual a 26, o topo da pilha está na posição 25 de elements 
	 * -Se size for igual a 10, o topo da pilha está na posição 9 de elements 
	 * -Se size for igual a n, o topo da pilha está na posição (n - 1) de elements 
	 * Resumindo, podemos assumir QUASE sempre que o topo da pilha é a posição  
	 * (size - 1) de elements. 
	 * O "quase" se deve ao caso de quando nossa pilha é vazia. Nesse caso,  
	 * size é igual a 0. Se fossemos seguir a regra acima indistintamente,  
	 * acabaríamos assumindo que neste caso o topo da pilha está na posição -1  
	 * de elements, o que é um erro... Trata-se então de uma exceção, a qual  
	 * deveremos estar atentos para fazer bobagem! 
	 * Para fins didáticos, criaremos um método privado que retorna a posição  
	 * exata do topo da pilha, e sempre utilizaremos este método para termos tal 
	 * informação. 
	 */  
	private int size;  
	
	/** 
	 * Construtor que recebe um int como parâmetro, indicando qual será a  
	 * capacidade da pilha recém-instanciada 
	 */  
	public SimpleStack(int capacity) {  
		/* 
		* Utilizamos o método abs da classe Math só pra evitar que se tente  
		* criar uma pilha "devedora"... 
		*/  
		elements = new String[Math.abs(capacity)];  
		size = 0;  
	}  
	  
	/** 
	 * Método utilizado para adicionar elementos à nossa pilha. Este elemento  
	 * sempre será inserido no topo deta pilha. 
	 * -Se o elemento for null, vamos lançar uma exceção, informando que nossa  
	 * pilha não aceita null como elemento válido. 
	 * -Se a pilha estiver cheia, retornamos null para indicar que não foi  
	 * possível insirir elemento. 
	 * -Se o elemento for inserido com sucesso, retornamos o próprio elemento,  
	 * indicando assim o sucesso da operação 
	 */  
	public String push(String element) {  
		if(element == null)  
			throw new IllegalArgumentException("O elemento não pode ser nulo!");  
		 
		if(size == elements.length)  
			return null;  
		 
		size++;  
		elements[getTopPosition()] = element;  
		return element;  
	}  
	  
	/** 
	 * Método utilizado para se obter o elemento que está no topo desta pilha,  
	 * porém, sem removê-lo da mesma. 
	 * -Se a pilha estiver vazia, retornamos null para indicar que a pilha  
	 * está vazia. 
	 * -Se houver ao menos um elemento na pilha, o elemento que está no topo  
	 * será retornado, indicando o sucesso da operação 
	 */  
	public String peek() {  
		if(isEmpty())  
			return null;  
		 
		return elements[getTopPosition()];  
	}  
	  
	/** 
	 * Método utilizado para retirar("destacar") um elemento desta pilha. Este  
	 * elemento sempre será aquele que se encontra no topo desta pilha. 
	 * -Se a pilha estiver vazia, retornamos null para indicar que a pilha  
	 * está vazia. 
	 * -Se houver ao menos um elemento na pilha, o elemento que está no topo  
	 * será retornado, indicando o sucesso da operação 
	 */  
	public String pop() {
		String result = peek();  
		/*Se havia um elemento no topo da pilha...*/  
		if(result != null) {  
			elements[getTopPosition()] = null;  
			size--;  
		}  
		return result;  
	}  
	  
	/** 
	 * Método utilizado para limpar todo o conteúdo da pilha. 
	 */  
	public void clear() {  
		for(int i = 0; i < size; i++)  
			elements[i] = null;  
		size = 0;  
	}  
	  
	/**
	 * Método utilizado para se obter o tamanho (número de elementos) da pilha 
	 */  
	public int getSize() {  
		return size;  
	}  
	  
	/** 
	 * Método utilizado para se obter a capacidade da pilha 
	 */  
	public int getCapacity() {  
		return elements.length;  
	}
	
	/**
	 * Método utilizado para verificar se a pilha está vazia. Se for o caso, 
	 * será retornado true, caso contrário, será retornado false.
	 */
	public boolean isEmpty() {
		return size <= 0;
	}
	  
	/** 
	 * Este método tem uma finalidade estritamente didática, visando facilitar o  
	 * entendimento do código desta classe. 
	 * Este método retorna um inteiro que representa a posição de elements onde  
	 * se encontra o último elemento inserido nesta pilha (O topo da pilha) 
	 */  
	private int getTopPosition() {
		if (isEmpty())
			return 0;
		return size - 1;  
	}
	
	/** 
	 * Este método serve para representar textualmente esta pilha 
	 * @see java.lang.Object#toString() 
	 */  
	public String toString() {  
		StringBuilder sb = new StringBuilder("[");  
		for(int i = 0; i < size; i++) {  
			sb.append(elements[i]);  
			if(i < size - 1)  
			  sb.append(" | ");  
		}  
		sb.append(">");  
		 
		return sb.toString();  
	}  
}

Agora, rode o seguinte programa, estude o código e divirta-se!

/**
 * @author Mantu
 */
package help.guj.zagaia;

public class SimpleStackTest {
	public static void main(String[] args) {
		String[] names = {
			"Mark", "Berg", "John", "Beni", "Jebb", "June",
			"Mary", "Karl", "Fred", "Hall", "Troy", "Joan"
		};
		SimpleStack stack = new SimpleStack(10);
		
		System.out.println(
			"Pilha de " + stack.getCapacity() + " posições criada: " + stack
		);
		System.out.println();
		
		System.out.println("Preenchendo a pilha:");
		for(int i = 0; i < names.length; i++) {
			System.out.print("\tInserindo o nome \"" + names[i] + "\":\t");
			if(stack.push(names[i]) == null)
				System.out.println("PILHA CHEIA!!! impossível inserir...");
			else
				System.out.println(
					stack + ". " + (stack.getCapacity() - stack.getSize()) + 
					" posições restantes."
				);
		}
		System.out.println();
		
		System.out.println("Removendo 5 elementos da pilha:");
		for(int i = 1; i <= 5; i++) {
			System.out.print("\t" + i + "a. remoção: \"" + stack.pop() + "\".");
			System.out.println(" A pilha agora esta assim: " + stack);
		}
		System.out.println();
		
		System.out.println(
			"O atual nome no topo da pilha é \"" + stack.peek() + "\"."
		);
		System.out.println(
			"O que? Não acredita??? Veja então: " + stack
		);
		System.out.println("Ora essa...");
		System.out.println();
		
		stack.clear();
		System.out.println("Limpando a pilha: " + stack);
		System.out.println();
		
		System.out.print("Consigo tirar mais algo da pilha? ");
		System.out.println(
			stack.pop() == null ? "Não consigo..." : "Consigo sim!"
		);
	}
}

Tente criar depois, a titulo de exercício, uma pilha de tamanho dinâmico, utilizando uma classe para representar os elementos.

JavaBaby Membro desde: 19/03/2007 14:12:59 Mensagens: 81 Offline

lindoooooooo!
cara,
muito bom os comentarios no código!!
estou conseguindo entender direitinho..
agora vou praticar e praticar...
espero me tornar um Mantu daqui a pouco!

Muito Obrigado!

Não tinha percebido que a pilha não funcionava direito. Agora está consertada.
Desculpem o transtorno.

Mantu, muito bom seu exemplo!
Vc tem muita didática.
Valeu

What is classpath? Membro desde: 22/11/2007 10:06:50 Mensagens: 7 Offline

Mantu! Parabéns! Isso que é explicação! São pessoas como vc que fazem a coisa funcionar! Grande abraço!

Notícias, artigos e o maior fórum brasileiro sobre Java