Pilha e Fila

Fila.java

package fila;

public class Fila {

	private Object[] itens = new Object[5];
	private int inicio = 0; // desenfileirar
	private int fim = 0; // enfileirar
	private int tamanho = 0;

	public void enfileirar(Object o) {
		expandir();
		itens[fim] = o;
		fim = ++fim % itens.length;
		tamanho++;
	}

	protected void expandir() {
		if (tamanho == itens.length) {
			Object[] newItens = new Object[itens.length * 2];
			for (int a = 0; a < itens.length; a++) {
				newItens[a] = itens[ (inicio + a) % itens.length];
			}
			itens = newItens;
			inicio = 0;
			fim = tamanho;
		}
	}

	public Object desenfileirar() {
		Object resultado = itens[inicio];
		tamanho--;
		inicio = ++inicio % itens.length;
		return resultado;
	}

	public int tamanho() {
		return tamanho;
	}

	public int capacidade() {
		return itens.length;
	}

}

FilaTest.java

package fila;

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 capacidade() {
		Fila fila = new Fila();
		assertEquals(5, fila.capacidade());
		
		fila.enfileirar("a");
		assertEquals(5, fila.capacidade());
		fila.enfileirar("b");
		fila.enfileirar("c");
		assertEquals(5, fila.capacidade());
		
		assertEquals("a", fila.desenfileirar());
		assertEquals(5, fila.capacidade());
		assertEquals("b", fila.desenfileirar());
		assertEquals("c", fila.desenfileirar());
		assertEquals(5, fila.capacidade());
	}
	
	@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());
		assertEquals(5, fila.capacidade());
	}
	
	@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());
		assertEquals(10, fila.capacidade());
	}
}

Pilha.java

public class Pilha {

	private Object[] items = new Object[10];
	private int cabeca = 0;
	
	public Pilha() {}
	
	public void empilhar(Object o) {
		if (cabeca >= capacidade() - 1) {
			redimensionar(capacidade() * 2);
		}
		items[cabeca++] = o;
	}
	
	private void redimensionar(int tamanho) {
		Object[] novoItems = new Object[tamanho];
		for (int i = 0; i < items.length && i < novoItems.length; i++) {
			novoItems[i] = items[i];
		}
		items = novoItems;

	}
	
	public Object desempilhar() {
		if ( capacidade() > 10 && cabeca < capacidade() / 4) {
			redimensionar(capacidade() / 2);
		}
		return items[--cabeca];
	}
	
	public int tamanho() {
		return cabeca;
	}
	
	public boolean vazia() {
		return tamanho() == 0;
	}
	
	public int capacidade() {
		return items.length;
	}
	
	public Object topo() {
		return items[cabeca-1];
	}
	
}

PilhaTest.java

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class PilhaTest {

	@Test
	public void lifo() {
		Pilha pilha = new Pilha();
		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() {
		Pilha pilha = new Pilha();
		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 capacidade() {
		Pilha pilha = new Pilha();
		assertEquals(10, pilha.capacidade());
		
		pilha.empilhar("a");
		assertEquals(10, pilha.capacidade());
		pilha.empilhar("b");
		pilha.empilhar("c");
		assertEquals(10, pilha.capacidade());
		
		assertEquals("c", pilha.desempilhar());
		assertEquals(10, pilha.capacidade());
		assertEquals("b", pilha.desempilhar());
		assertEquals("a", pilha.desempilhar());
		assertEquals(10, pilha.capacidade());
	}
	
	@Test
	public void topo() {
		Pilha pilha = new Pilha();
		
		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() {
		Pilha pilha = new Pilha();
		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(20, pilha.capacidade());

		
		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());
		assertEquals(10, pilha.capacidade());
	}
}