Estrutura de Dados Parte 1 - Pilha

Este será o primeiro de uma série de post's relacionados à estrutura de dados.

Nessa sequência vou explicar o que é cada uma das estruturas, seus respectivos funcionamentos e aplicações através de exemplos práticos em Java.

Neste primeiro post vou falar sobre a estrutura que eu acredito ser a mais simples, a Pilha.

Antes de definirmos tecnicamente, vamos tentar imaginar exemplos de pilhas no dia-a-dia.
Olhando em volta do quarto onde estou escrevendo, vejo uma pilha de caixas e sei que em alguma delas existe uma pilha de livros. De onde estou sentado consigo ver a pia da cozinha, e adivinhem, existe uma pilha de pratos para serem lavados (irei lavá-los assim que terminar esse post :-P ).

Como o exemplo da pilha de pratos já é bem discutido em outras literaturas, vou aproveitar as caixas e tentar diversificar um pouco.

Recentemente me mudei para um local mais próximo do meu trabalho e na hora de encaixotar os meus livros lembrei que lá não teria uma estante para colocá-los. Me dei conta de que os livros permaneceriam encaixotados por muito tempo, então tentei organizá-los conforme a minha necessidade. Sabia que os livros com menor probabilidade de leitura deveriam ficar no fundo, isso porque se eu precisasse de algum deles o acesso seria mais fácil.

Para pegar um dos primeiros livros colocados na caixa, terei que remover cada um dos que estão no topo.

Com isso, já conseguimos extrair algumas características de uma pilha, como por exemplo, os primeiros livros colocados serão os últimos a serem retirados da caixa. Esse conceito é mais conhecido como LIFO (Last In First Out).

Então tecnicamente falando, pilhas são estruturas de dados que servem para guardar vários elementos, onde os últimos elementos armazenados serão os primeiros a sair.

As pilhas possuem algumas operações básicas de manipulação: PUSH e POP.

PUSH: operação para adicionar um novo elemento no topo da pilha.
POP: operação para remover o elemento que está no topo da pilha.

Outras operações adicionar que podem ser úteis:

first: operação que informa qual é o elemento no topo da pilha.
last: operação que infroma qual é o elemento na base da pilha.
isEmpty: operação que informa se a pilha está vazia.
isFull: operação que informa se a pilha está cheia.

Uma implementação simples de Pilha em Java seria:

public class Pilha {

 private int[] elementos;
 private int posicao = -1;

 public Pilha(int tamanho) {
  this.elementos = new int[tamanho];
 }

 public void push(int i) {
  verificaSeAListaEstaCheia();
  elementos[++posicao] = i;
 }

 public int pop() {
  verificaSeAListaEstaVazia();
  return elementos[posicao--];
 }
 
 public final boolean isEmpty() {
  return posicao < 0;
 }
 
 public final boolean isFull() {
  return posicao==elementos.length-1;
 }
 
 public int size() {
  return posicao < 0 ? 0 : posicao+1;
 }

 private void verificaSeAListaEstaVazia() {
  if(isEmpty())
   throw new IllegalStateException("A Pilha esta vazia");
 }
 
 private void verificaSeAListaEstaCheia() {
  if(isFull())
   throw new IllegalStateException("A Pilha esta cheia");
 }

 public static void main(String[] args) {
  Pilha pilha = new Pilha(5);
  int numero = 1;
  while(!pilha.isFull()){
   pilha.push(numero++);
  }
  
  while(!pilha.isEmpty()){
   System.out.println(pilha.pop());
  }
 }

}

Reparem que ao executar o método main dessa classe, a saída na console será 5 4 3 2 1, nessa ordem, justamente por que o 5 foi  o último elemento inserido.

Fugindo um pouco do escopo do post, não foi tão simples chegar ao resultado final da class Pilha, nem à estrutura da classe, nem saber quais seriam os métodos, os nomes e a interação entre eles.
Fiz muitas modificações até chegar nesse resultado, e por várias vezes acabei gerando bugs em trechos de códigos que já estavam funcionando. O que fazer em um momento como esse?! Simples: Testes de Unidade. Não vou entrar em detalhes do que são Testes de Unidade, vou deixar isso para um post mais adiante. Abordei esse assunto apenas para colocar a minha classe de teste:

public class PilhaTest {

 private Pilha pilha;
 
 @Before
 public void before(){
  pilha = new Pilha(5);
 }

 @Test
 public void quandoIniciarUmPilhaDeveTerTamanhoZero() {
  assertEquals(0, pilha.size());
 }

 @Test
 public void quandoAdicionarUmElementoNaListaDeveModificarOTamanho() {
  pilha.push(1);
  assertEquals(1, pilha.size());
 }
 
 @Test
 public void quandoAdicionarDoisElementoNaListaDeveModificarOTamanho() {
  pilha.push(1);
  pilha.push(2);
  assertEquals(2, pilha.size());
 }
 
 @Test
 public void aPilhaDeveRetornarOUltimoElementoParte1() {
  pilha.push(3);
  assertEquals(3, pilha.pop());
 }
 
 @Test
 public void aPilhaDeveRetornarOUltimoElementoParte2() {
  pilha.push(3);
  pilha.push(9);
  assertEquals(9, pilha.pop());
 }
 
 @Test
 public void aPilhaDeveRetornarOUltimoElementoParte3() {
  pilha.push(3);
  pilha.push(9);
  assertEquals(9, pilha.pop());
  pilha.push(10);
  pilha.push(11);
  assertEquals(11, pilha.pop());
  assertEquals(10, pilha.pop());
  assertEquals(3, pilha.pop());
 }
 
 @Test
 public void oPopDeveRemoverOElementoDaLista() {
  pilha.push(3);
  pilha.push(9);
  assertEquals(9, pilha.pop());
  assertEquals(3, pilha.pop());
 }
 
 @Test
 public void oPopDeveAlterarOTamanhoDaLista() {
  assertEquals(0, pilha.size());
  
  pilha.push(3);
  pilha.push(9);
  assertEquals(2, pilha.size());
  
  assertEquals(9, pilha.pop());
  assertEquals(1, pilha.size());
  
  assertEquals(3, pilha.pop());
  assertEquals(0, pilha.size());
 }
 
 @Test
 public void perguntarParaUmaPilhaVaziaSeEleaEstaVazia(){
  assertTrue(pilha.isEmpty());
 }
 
 @Test
 public void perguntarParaUmaPilhaCheiaSeEleaEstaVazia(){
  pilha.push(10);
  assertFalse(pilha.isEmpty());
 }
 
 @Test
 public void perguntarParaUmaPilhaQueJaFoiBemManipuladaSeElaEstaVaziaParte1(){
  pilha.push(10);
  pilha.pop();
  assertTrue(pilha.isEmpty());
 }
 
 @Test
 public void perguntarParaUmaPilhaQueJaFoiBemManipuladaSeElaEstaVaziaParte2(){
  pilha.push(10);
  pilha.pop();
  pilha.push(10);
  pilha.pop();
  assertTrue(pilha.isEmpty());
 }
 
 @Test
 public void perguntarParaUmaPilhaQueJaFoiBemManipuladaSeElaEstaVaziaParte3(){
  pilha.push(10);
  pilha.pop();
  pilha.push(10);
  assertFalse(pilha.isEmpty());
 }
 
 @Test(expected=IllegalStateException.class)
 public void quandoChamarOPopEmUmaPilhaVaziaParte1() {
  pilha.pop();
 }
 
 @Test(expected=IllegalStateException.class)
 public void quandoChamarOPopEmUmaPilhaVaziaParte2() {
  pilha.push(1);
  assertEquals(1, pilha.pop());
  pilha.pop();
  
 }
 
 @Test(expected=IllegalStateException.class)
 public void quandoChamarOPushEmUmaListaQueEstaCheia() {
  pilha.push(1);
  pilha.push(2);
  pilha.push(3);
  pilha.push(4);
  pilha.push(5);
  
  pilha.push(6);
 }
 
 @Test
 public void perguntarParaUmaPilhaCheiaSeEleaEstaCheia(){
  pilha.push(1);
  pilha.push(2);
  pilha.push(3);
  pilha.push(4);
  pilha.push(5);
  assertTrue(pilha.isFull());
 }
 
 @Test
 public void perguntarParaUmaPilhaVaziaSeEleaEstaCheia(){
  assertFalse(pilha.isFull());
 }
 @Test
 public void perguntarParaUmaPilhaSemiVaziaSeEleaEstaCheia(){
  pilha.push(1);
  pilha.push(2);
  assertFalse(pilha.isFull());
 }
 
 @Test
 public void perguntarParaUmaPilhaQueJaFoiBemManipuladaSeElaEstaCheia(){
  pilha.push(1);
  pilha.push(2);
  pilha.push(3);
  pilha.push(4);
  pilha.push(5);
  assertTrue(pilha.isFull());
  pilha.pop();
  assertFalse(pilha.isFull());
 }
}

Pilhas podem ser usadas para várias situações, exemplos clássicos são os de uma linguagem de programação que usa a pilha para guardar a chamada de métodos (veja mais neste post sobre recursividade) ou uma calculadora que faz o empilhamento das operações para depois executá-las na ordem em que foram inseridas.
Aguardem o próximo post sobre Filas.