Pergunta

Como utilizar as pilhas (Stacks)?

Resposta

Uma pilha é uma estrutura de dados que permite que dados sejam colocados (operação conhecida como push) e retirados (operação conhecida como pop) de forma tal que seja sempre mantida a ordem de inserção dos dados, tal como numa pilha real, onde os elementos são colocados e retirados no topo da pilha.

Uma pilha é uma estrutura de dados conhecida como LIFO (Last In - First Out) onde o último elemento colocado é o primeiro a ser retirado. Se os valores 1, 2, 3 e 4 fossem inseridos numa pilha, sua remoção ocorreria na ordem inversa, ou seja, 4, 3, 2 e 1.

Algumas pilhas suportam uma operação adicional denominada peek que permite consultar o elemento presento no topo da pilha sem retirá-lo.

Embora não sejam estruturas comumente utilizadas, são extremamente úteis em certos casos, por exemplo uma lista de operações para desfazer (undo).

O Java provê uma implementação de pilha através da classe java.util.Stack. Sendo uma subclasse de java.util.Vector (JavaFaq 0063) existem similaridades entre os vetores e as pilhas implementadas pelo Java, pois os vetores são como filas (queues) enquanto que as pilhas são filas ordenadas segundo o critério LIFO. Tal como na classe java.util.Vector e na classe java.util.Hastable (JavaFaq0070), os valores armazenados devem ser instâncias de algum  tipo Object, ou seja, podem ser qualquer outro tipo de objeto, tal como do tipo String ou Integer. Desta forma dados de tipo primitivo não pode ser usados diretamente sendo necessário o uso de alguma das classes wrapper oferecidas pelo Java.

Abaixo temos uma aplicação que exemplifica com que facilidade podemos utilizar a classe java.util.Stack.

import java.util.Stack;

public class StackDemo {

  public static void main(String args[]) {
    // Criação de uma nova pilha vazia
    Stack lifo = new Stack();
    // Adição de alguns elementos
    for (int i = 1; i <= 10; i++) {
      lifo.push ( new Integer(i) );
      System.out.print ( i + ", " );
    }
    // Indicação de Fim
    System.out.println ( "FIM");
    // Remoção dos elementos colocados na pilha
    while ( !lifo.empty() ) {
      System.out.print ( lifo.pop() + ", " );
    }
    // Indicação de Fim
    System.out.println ("VAZIA");
  }
}

Mais detalhes podem ser obtidos através da documentação que acompanha o Java.