Implementação de Pilha baseada em Lista encadeada

FilaTest.java

import static org.junit.Assert.*;

import org.junit.Test;

public class FilaTest {


	@Test
	public void fifo() {
		Fila fila = new Fila();
		fila.enfileirar("a");
		fila.enfileirar("b");
		fila.enfileirar("c");
		
		assertEquals("a", fila.desenfileirar());
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
	}

	@Test
	public void misturado() {
		Fila fila = new Fila();
		fila.enfileirar("a");
		fila.enfileirar("b");
		
		assertEquals("a", fila.desenfileirar());

		fila.enfileirar("c");
		
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
	}
	
	@Test
	public void tamanho() {
		Fila fila = new Fila();
		assertEquals(0, fila.tamanho());
		
		fila.enfileirar("a");
		assertEquals(1, fila.tamanho());
		fila.enfileirar("b");
		fila.enfileirar("c");
		assertEquals(3, fila.tamanho());
		
		assertEquals("a", fila.desenfileirar());
		assertEquals(2, fila.tamanho());
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
		assertEquals(0, fila.tamanho());
	}
	
	@Test
	public void circular() {
		Fila fila = new Fila();
		fila.enfileirar("a");
		fila.enfileirar("b");
		
		assertEquals("a", fila.desenfileirar());

		fila.enfileirar("c");
		fila.enfileirar("d");
		fila.enfileirar("e");
		fila.enfileirar("f");
		
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
		
		assertEquals(3, fila.tamanho());
	}
	
	@Test
	public void estouro() {
		Fila fila = new Fila();
		fila.enfileirar("a");
		fila.enfileirar("b");
		
		assertEquals("a", fila.desenfileirar());

		fila.enfileirar("c");
		fila.enfileirar("d");
		fila.enfileirar("e");
		fila.enfileirar("f");
		fila.enfileirar("g");
		fila.enfileirar("h");
		
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
		
		assertEquals(5, fila.tamanho());
	}
}

PilhaListaEncadeada.java

/**
 * Implementação do Tipo Abstrato de Dados Pilha, baseado em Lista encadeada
 */
public class PilhaListaEncadeada {
	
	/**
	 * A pilha mantem uma referência para base, o início da lista encadeada.
	 */
	private Node base;
	
	/**
	 * Cria um novo nó no topo da pilha (ou final da lista) para armazenar
	 * o Objeto o 
	 */
	public void empilhar(Object o) {
		Node novo = new Node();
		novo.setValor(o);
		novo.setProximo(null);
		
		if (base == null) { //Pilha vazia, a base apontará para o novo nó
			base = novo;
			
		} else { //A pilha já tem um topo sobre o qual ficará o novo nó
			Node topo = encontrarUltimo();
			topo.setProximo(novo);
		}
	}

	private Node encontrarUltimo() {
		Node auxiliar = base;
		while (auxiliar.getProximo() != null) {
			auxiliar = auxiliar.getProximo();
		}
		return auxiliar;
	}

	/**
	 * Remove e retorna o elemento no topo da pilha, ou seja, no final da fila.
	 * Se a pilha estiver vazia, lança exceção.
	 * Se a pilha só tiver um elemento, ficará vazia após o desempilhar, portanto 
	 * a base será null.
	 * Caso contrário, transforma o penúltimo nó em último, removendo o último original. 
	 */
	public Object desempilhar() {
		
		if (base == null) {
			throw new NullPointerException("Pilha vazia");
		}
			
		Object valor;
		
		// Contém apenas um nó. A lista ficará vazia após o desempilhar.
		if (base.getProximo() == null) { 
			valor = base.getValor();
			base = null;
		
		} else { 
			// Caminha até o penúltimo nó, guarda o valor do último nó e
			// transforma o penúltimo em último
			Node penultimo = encontrarPenultimo();
			valor = penultimo.getProximo().getValor();
			penultimo.setProximo(null); // Quebra o link com o último nó original
		}
		
		return valor;
	}

	protected Node encontrarPenultimo() {
		Node auxiliar = base;
		while (auxiliar.getProximo().getProximo() != null) {
			auxiliar = auxiliar.getProximo();
		}
		return auxiliar;
	}

	/**
	 * Percorre a lista, usando um contador para calcular o tamanha da pilha.
	 */
	public int tamanho() {
		
		if (base == null) {
			return 0;
		}
		
		int tamanho = 1;
		Node auxiliar = base;
		while (auxiliar.getProximo() != null) {
			auxiliar = auxiliar.getProximo();
			tamanho++;
		}

		return tamanho;
	}

	/**
	 * Retorna o elemento no topo da pilha, ou seja, no final da fila.
	 * Não altera os dados nem a estrutura da pilha.
	 */
	public Object topo() {
		Node topo = encontrarUltimo();
		return topo.getValor();
	}

}

/**
 * Estrutura para representar um nó de uma lista encadeada.
 * Possui uma referência para o valor que armazena e outra para 
 * o próximo nó da lista encadeada.
 *
 */
class Node {

	private Object valor;
	private Node proximo;

	public Object getValor() {
		return valor;
	}

	public void setValor(Object valor) {
		this.valor = valor;
	}

	public Node getProximo() {
		return proximo;
	}

	public void setProximo(Node proximo) {
		this.proximo = proximo;
	}

}

PilhaTest.java

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class PilhaTest {

	@Test
	public void lifo() {
		PilhaListaEncadeada pilha = new PilhaListaEncadeada();
		pilha.empilhar("a");
		pilha.empilhar("b");
		pilha.empilhar("c");
		
		assertEquals("c", pilha.desempilhar());
		assertEquals("b", pilha.desempilhar());
		assertEquals("a", pilha.desempilhar());
	}

	@Test
	public void tamanho() {
		PilhaListaEncadeada pilha = new PilhaListaEncadeada();
		assertEquals(0, pilha.tamanho());
		
		pilha.empilhar("a");
		assertEquals(1, pilha.tamanho());
		pilha.empilhar("b");
		pilha.empilhar("c");
		assertEquals(3, pilha.tamanho());
		
		assertEquals("c", pilha.desempilhar());
		assertEquals(2, pilha.tamanho());
		assertEquals("b", pilha.desempilhar());
		assertEquals("a", pilha.desempilhar());
		assertEquals(0, pilha.tamanho());
	}
	
	
	@Test
	public void topo() {
		PilhaListaEncadeada pilha = new PilhaListaEncadeada();
		
		pilha.empilhar("a");
		assertEquals("a", pilha.topo());
		pilha.empilhar("b");
		assertEquals("b", pilha.topo());
		pilha.empilhar("c");
		assertEquals("c", pilha.topo());
		
		assertEquals("c", pilha.desempilhar());
		assertEquals("b", pilha.topo());
		assertEquals("b", pilha.desempilhar());
		assertEquals("a", pilha.topo());
		assertEquals("a", pilha.desempilhar());
	}
	
	@Test
	public void limiteCapacidade() {
		PilhaListaEncadeada pilha = new PilhaListaEncadeada();
		pilha.empilhar("a");
		pilha.empilhar("b");
		pilha.empilhar("c");
		pilha.empilhar("d");
		pilha.empilhar("e");
		pilha.empilhar("f");
		pilha.empilhar("g");
		pilha.empilhar("h");
		pilha.empilhar("i");
		pilha.empilhar("j");
		pilha.empilhar("k");
		
		assertEquals(11, pilha.tamanho());

		
		assertEquals("k", pilha.desempilhar());
		assertEquals("j", pilha.desempilhar());
		assertEquals("i", pilha.desempilhar());
		assertEquals("h", pilha.desempilhar());
		assertEquals("g", pilha.desempilhar());
		assertEquals("f", pilha.desempilhar());
		assertEquals("e", pilha.desempilhar());
		assertEquals("d", pilha.desempilhar());

		assertEquals(3, pilha.tamanho());
	}
}