Pilhas

Livro de Sedgewick e Wayne: sec.1.3, p.120.  Website do livro: resumo sec.1.3, slides.  Veja também a página algs4.cs.​princeton.edu/​code/, que tem o código fonte, a documentação, e dados de teste de todos os programas do livro.

O conceito de pilha já é bem conhecido do leitor.  Esta página examina o conceito como exemplo de ADT (e aproveita para introduzir alguns recursos da linguagem Java).

Pilha (= stack) e sua API

• Uma pilha (= stack) é um ADT que consiste em uma coleção de coisas munida de duas operações:  push, que insere uma coisa na coleção, e pop, que remove a coisa mais recente da coleção.  (Portanto, a última coisa a entrar é a primeira a sair.)
• As coisas de que uma pilha é feita serão chamadas itens. Os itens podem ser números, strings, structs, etc., etc.
• Exemplos de clientes de pilhas:  botão voltar de um browser, cálculo do valor de uma expressão aritmética.
• Eis a API (= interface) de uma pilha de itens  (além das operações fundamentais push e pop, temos algumas operações auxiliares):

  public class Stack<Item>
  	Stack()	construtor: cria uma pilha de Items vazia
  void	push(Item item)	insere item nesta pilha
  Item	pop()	remove o Item mais recente desta pilha
  boolean	isEmpty()	esta pilha está vazia?
  int	size()	número de Items nesta pilha

• Item é uma tipo genérico, ou parâmetro de tipo, que deve ser substituído por um tipo concreto quando uma instância da pilha é criada.

Exemplo de cliente

• Exemplo de cliente de pilha:  lê strings da entrada padrão e insere-as numa pilha, a menos que a string lida seja "-", caso em que remove uma string da pilha:

  public class ClienteDePilha {
  
     public static void main(String[] args) {
        Stack<String> pilha;
        pilha = new Stack<String>();
  
        while (!StdIn.isEmpty()) {
           String str = StdIn.readString();
           if (!str.equals("-"))
              pilha.push(str);
           else if (!pilha.isEmpty()) 
                   StdOut.print(pilha.pop() + " ");
        }
        StdOut.println("(" + pilha.size() + " left on stack)");
     }
  }
  

• Observação 1:  new Stack<String>() cria uma instância da classe Stack, com tipo concreto String no lugar do parâmetro Item.  Assim, a variável pilha passa a ser uma pilha de Strings.
• Observação 2:  str é uma instância da classe String de Java. O método equals() compara str com outra string.  (A propósito, a expressão if (str != "-") é sintaticamente errada. A expressão if (!equals(str, "-") também está errada.)
• Observação 3:  StdIn e StdOut são bibliotecas de métodos estáticos que cuidam da entrada padrão e saída padrão respectivamente.
• Observação 4:  O método main() é declarado como static porque ele faz parte da classe ClienteDePilha toda e não de instâncias particulares da classe.  É bem verdade, entretanto, que ninguém vai pensar em construir uma instância desse programa cliente (dizendo new ClienteDePilha(), por exemplo)!
• Teste:

  % javac ClienteDePilha.java
   
  % more tobe.txt
  to be or not to - be - - that - - - is
  
  % java ClienteDePilha < tobe.txt
  to be not that or be (2 left on stack)
  

• Rastreamento:

                 StdIn  StdOut          
                 push   pop       0  1  2  3   4
                                                
                 to               to
                 be               to be
                 or               to be or
                 not              to be or not
                 to               to be or not to
                 -      to        to be or not
                 be               to be or not be
                 -      be        to be or not
                 -      not       to be or 
                 that             to be or that
                 -      that      to be or 
                 -      or        to be 
                 -      be        to 
                 is               to is
  

Pilha implementada em vetor com redimensionamento

• A seguinte classe StackRA implementa a interface Stack. (O sufixo RA serve apenas para distinguir essa implementação de outra que faremos adiante.)
• Classe StackRA: pilha implementada em vetor com redimensionamento (resizing array):

  public class StackRA<Item> {
  
     private Item[] a;
     private int N;
  
     // construtor
     public StackRA() {
        a = (Item[]) new Object[2];
        N = 0;
     }
  
     // a pilha mora em a[0..N-1]
     
     public boolean isEmpty() {
        return N == 0;
     }
     
     public void push(Item item) { 
        if (N == a.length)
           resize(2 * a.length);
        a[N++] = item;
     }
  
     public Item pop() {
        Item item = a[--N];
        if (N > 0 && N == a.length/4)
           resize(a.length/2);
        return item;
     }
  
     private void resize(int max) {
        Item[] temp;
        temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++)
           temp[i] = a[i];
        a = temp;
     }
  }
  

• O método StackRA() da classe StackRA é um construtor. Ele é invocado por um new no cliente e cria uma instância da classe StackRA.
• O prefixo public indica os métodos (e variáveis) que são acessíveis a todos os cliente. Esses são os métodos especificados na API.
• O prefixo private indica os métodos e variáveis auxiliares aos quais clientes não têm acesso. É claro que esses métodos não constam da API.
• Nenhum dos métodos e variáveis dessa classe StackRA tem o modificador static.  Assim, todos os métodos e variáveis são de instância: cada instância da classe tem sua própria cópia dos métodos e variáveis.
• O método privado resize() faz um redimensionamento: aumenta ou diminui o vetor que abriga a pilha.  (Depois do redimensionamento, não é necessário liberar o espaço ocupado pelo antigo vetor pois o mecanismo de coleta de lixo do Java cuida disso automaticamente.)
• Graças à maneira como o redimensionamento é invocado por pop() e push(), o vetor a[] sempre está pelo menos 25% cheio.
• O código exibido acima é simplificado. O website do livro tem uma versão mais completa de StackRA: veja a classe ResizingArrayStack e a correspondente API, um pouco mais rica que a API exibida acima.

Exercícios 1

1. Implemente o método size().
2. Prove que o vetor a[] está sempre 25% cheio. (Antes, é preciso formular essa afirmação de maneira mais precisa.)
3. Redimensionamento.  Antes de cada push e cada pop, é verdade que a.length é potência de 2?  É verdade que a.length ≥ 2?  É verdade que a.length/4 ≤ N ≤ a.length?  Pode acontecer a.length/4 == N? Que acontece se N for 0 no começo de um pop?
4. Escreva um programa que leia linhas de texto da entrada padrão (ignore as linhas vazias) e coloque as linhas em ordem alfabética.  As linhas de texto têm comprimento arbitrário e o número de linhas é arbitrário.  Sugestões: Use o método readLine da classe StdIn de SW.  Use redirecionamento da entrada para ler os dados de um arquivo (= file) e não do teclado.  Construa um vetor de strings usando redimensionamento.  Use o método java.util.Arrays.sort() para colocar o vetor em ordem lexicográfica. Depois, repita os testes usando Insertion.sort(), Merge.sort(), e Quick.sort().

Pilha implementada em lista ligada

• Inserção na pilha (push):

  

• Remoção da pilha (pop):

  

• Classe StackL: pilha implementada em lista ligada:

  public class StackL<Item> {
  
      private Node first; 
  
      private class Node {
          Item item;
          Node next;
      }
  
      public boolean isEmpty() {
          return first == null;
      }
  
      public void push(Item item) {
          Node oldfirst = first;
          first = new Node();
          first.item = item;
          first.next = oldfirst;
      }
  
      public Item pop() {
          Item item = first.item;
          first = first.next;
          return item;
      }
  
      public static void main(String[] args) {
          StackL<String> s = new StackL<String>();
          while (!StdIn.isEmpty()) {
              String item = StdIn.readString();
              if (!item.equals("-")) s.push(item);
              else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
          }
          StdOut.println("(" + s.size() + " left on stack)");
      }
  }
  

• A classe Node define os nós da lista ligada. Note que ela é privada e não-estática.
• A classe StackL não tem um construtor pois sua única tarefa seria fazer first = null, e essa atribuição é redundante porque todas as variáveis são inicializadas com null ou 0.
• Para simplificar, a variável N e o método size() foram omitidos no código acima.
• O cliente de teste main() embutido na classe StackL permite fazer um teste simples da classe.
• O código de StackL exibido acima é simplificado. O website do livro tem implementações mais completas. Veja a classe LinkedStack e a correspondente API.  A classe Stack é uma implementação mais profissional e também usa uma lista ligada; veja a API correspondente.

Exercícios 2

1. Escreva um método size() para a classe StackL. Há duas maneiras de fazer isso, uma ansiosa (eager) e outra preguiçosa (lazy).  A maneira ansiosa consiste em manter uma variável de instância N e atualizar o seu valor a cada push() e cada pop(). A maneira preguiçosa consiste em calcular o tamanho da lista diretamente.  Escreva uma versão preguiçosa em estilo recursivo.
2. O método main() da classe StackL imprime o número de elementos que sobraram na pilha no fim do teste. Modifique o método de modo a imprimir o conteúdo da pilha no fim do teste. Teste o código modificado.
3. (SW 1.3.19, p.164)  Exercício sobre listas ligadas, sem relação direta com pilhas.  Escreva um método recursivo que remova último nó de uma lista ligada cujo primeiro nó é first. Que coisa o método deveria devolver? Pense!