Desvendando as pilhas

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Começamos esse post com a seguinte pergunta: como manter dados organizados da mesma forma que um vetor mas, acessando (inserindo e removendo) seus elementos somente pelo início ou fim dele ?

Você poderia responder que realizar essa tarefa é possível através do controle do índice do vetor visto que, os vetores oferecem acesso direto aos seus elementos. Contudo, isso seria algo muito complicado porque a cada inserção ou remoção, todos os elementos existentes teriam de ser deslocados para a esquerda, no caso da inserção, ou para a direita, no caso da remoção.

A idéia é: não queremos esse trabalho, queremos facilidade.

Para respondermos essa pergunta, é necessário ir além, entender um novo conceito. Precisamos entender  as pilhas ou, em inglês, stacks. É importante deixar claro que não estou falando das pilhas da Figura 1.

Figura 1 - Pilhas Duracell

Uma pilha, na ciência da computação, é uma estrutura de armazenamento de dados em que seu acesso só pode ser feito através de um topo. Imagine a seguinte situação: sua mãe te obrigou a lavar todos os pratos que estavam na pia. Depois de limpos, você começou a empilhá-los. Sua mãe viu você fazendo isso, te deu aquele belo esporro e mandou você secá-los. Quando você ia começar a secar, ela te deu um outro esporro, pois você tentou pegar um prato que estava no meio do pilha. Fazer isso, pode causar a quebra de todos os pratos que estão acima do que você tinha escolhido.

E aí, você apanhou.

Figura 2 - Sua mãe furiosa

É amigo ou amiga, a vida não é fácil. Mas então, como você seca os pratos ?

A resposta é simples. Para manter a integridade da sua pilha de pratos, você deve acessar somente o topo dela e assim, pegar um prato de cada vez, secá-lo e por numa nova pilha de pratos secos. Assim, você não apanha.

Figura 3 - Sua mãe feliz

Assim como é necessário manter a integridade da pilha de pratos, também é necessário manter a integridade da nossa pilha de dados. Logo, as mesmas regras devem ser seguidas. Contudo, uma pergunta ainda permanece: porque usar pilhas ?

Com elas é possível modelar soluções de uma forma simples e clara. Soluções, as quais se fossem modeladas com o uso de vetores resultariam em mais trabalho.

As pilhas são entidades mais abstratas que vetores e muitas outras estruturas de armazenamento de dados. Elas são definidas principalmente por sua interface, ou seja, as operações permitidas que podem ser executadas nelas. O mecanismo subjacente usado para implementá-las não é visível para o usuário.

Um problema que pode ser resolvido com o uso de pilhas, é o problema da palavra inversa. Esse problema consiste que dada uma determinada palavra, o resultado desejado é ela ao inverso, ou seja, para a palavra "casa", o retorno esperado é "asac".

Como resolver isso ?

Para que possamos começar, precisamos entender as duas operações básicas de uma pilha: push e pop.

Push significa empurrar logo, essa operação consiste em adicionar um item pelo topo na pilha. Pop significa remover um item pelo topo da pilha. Simples não !?

Figura 4 - As operações de uma pilha

Então, nosso problema da string reversa já pode ser resolvido. O que precisamos fazer é recuperar uma string digitada pelo usuário, empilhar letra por letra e depois, desempilhar completamente a pilha. Com isso, atingimos uma string reversa para qualquer uma fornecida pela usuário.

Já temos tudo o que precisamos para criar nossa implementação de pilha.

A classe Stack

1:  class Stack {  
2:         
3:       private char[] items;  
4:       private int counter;  
5:       private int size;  
6:    
7:       public Stack(int size){  
8:            items = new char[size];  
9:            this.size = size;  
10:            counter = 0;  
11:       }  
12:    
13:       public void push(char item) throws FullStackException{  
14:            if(isFull()){  
15:                 throw new FullStackException("Can't push. Stack is full.");  
16:            }  
17:            items[counter] = item;  
18:            counter++;  
19:       }  
20:    
21:       public char pop() throws EmptyStackException{  
22:            if(isEmpty()){  
23:                 throw new EmptyStackException("Can't remove. Stack is empty.");  
24:            }       
25:            counter--;  
26:            char item = items[counter];            
27:            return item;  
28:       }  
29:    
30:       public boolean isEmpty(){  
31:            return counter == 0;  
32:       }  
33:    
34:       public boolean isFull(){  
35:            return counter == size;  
36:       }  
37:    
38:       public char peek() throws EmptyStackException{  
39:            if(isEmpty()){  
40:                 throw new EmptyStackException("Can't remove. Stack is empty.");  
41:            }  
42:            return items[counter];  
43:       }  
44:  }  

Nossa pilha trata dados do tipo char visto que, precisamos tratar letra por letra. Os métodos push e pop fazem exatamente o que discutimos acima. Contudo, é importante ressaltar que na nossa implementação de método pop, o item removido é retornado para o usuário.

Os métodos isEmpty() e isFull() avaliam, respectivamente, se a pilha está vazia ou cheia. Essas verificações são feitas através do contador interno da pilha, a variável counter. Se esta variável for igual 0, a pilha está vazia e se for igual ao tamanho da pilha, o qual foi definido no construtor da classe, a pilha está cheia. O método peek() retorna o valor que está no topo da pilha, sem removê-lo.

Foram utilizadas exceções para todos os tratamentos de erro da pilha. Caso a pilha esteja vazia, em qualquer situação de acesso, ou seja, no uso do método pop e do método peek, uma EmptyStackException é propagada para informar ao usuário que não será possível completar a operação pois, a pilha está vazia. Uma FullStackException é propagada pelo método push, caso a pilha esteja cheia.

A classe ReverseString

1:  import java.util.Scanner;  
2:    
3:  class ReverseString {  
4:       public static void main(String[] args) {  
5:            ReverseString reverseString = new ReverseString();            
6:            String sourceString = reverseString.getSourceString();  
7:            char[] charArray = sourceString.toCharArray();  
8:            Stack stack = new Stack(sourceString.length());  
9:    
10:            for(int i=0;i<charArray.length;i++){  
11:                 try{  
12:                      stack.push(charArray[i]);  
13:                 } catch (FullStackException e) {  
14:                      e.printStackTrace();  
15:                      System.exit(1);  
16:                 }  
17:            }  
18:    
19:            System.out.print("String reversa: ");  
20:    
21:            while(!stack.isEmpty()){  
22:                 try{                      
23:                      System.out.print(stack.pop());  
24:                 } catch (EmptyStackException e) {  
25:                      e.printStackTrace();  
26:                      System.exit(1);  
27:                 }  
28:            }  
29:       }  
30:    
31:       public String getSourceString(){  
32:            Scanner input = new Scanner(System.in);  
33:            System.out.print("Informe a string: ");  
34:            return input.nextLine();  
35:       }  
36:  }  

Essa é a nossa classe cliente que utiliza nossa implementação de pilha. O método getSourceString() recupera o que foi digitado no console. No método main, utilizamos a string recuperada e realizamos a inversão, através dos métodos push e pop da pilha.

Vamos ver funcionando ?

Compile todos os arquivos .java.

Figura 5 - Compilação dos arquivos fonte

Execute e veja o resultado !!!

Figura 6 - Execução do programa

Terminamos !!

Link no dropbox:
Link no github: https://github.com/PrecisoEstudarSempre/Stacks.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Facebook: https://www.facebook.com/precisoestudarsempre/

Referências bibliográficas:
Estruturas de dados e algoritmos em Java - Lafore, Robert

Imagens:
Figura 2 - http://noticiasdatv.uol.com.br/media/_versions/tichina_arnold_free_big.jpg
Figura 3 - http://www.clickcultural.com.br/foto/45/per_ft1_145.jpg
Figura 4 - http://botbench.com/blog/wp-content/uploads/2013/01/image5.png