Tipos abstratos de dados (ADTs)

Livro de Sedgewick e Wayne: sec.1.2, p.64.  Website do livro: resumo sec.1.2.

(Sugiro que o leitor pule esta página quando vier aqui pela primeira vez. Volte para cá mais tarde, quando sentir a necessidade de esclarecer conceitos e terminologia.)

Tipos abstratos de dados (ADTs)

• TAD = tipo abstrato de dados = ADT = abstract data type.
• Um ADT é um conjunto de coisas, que chamaremos itens, e um conjunto operações sobre essas coisas.
• As operações são especificadas em uma interface que chamamos API (applications programming interface).  A interface diz o que cada operação faz, sem dizer como faz o que faz.
• Exemplo de ADT:  pilha.  As operações são:  inserção de um item e remoção de um item (de acordo com certas regras).
• Outros exemplos de ADTs:  fila, string, fila priorizada, tabela de símbolos, grafo, etc.
• Um ADT pode ser implementado (ou seja, concretamente realizado) de diversas maneiras.  (Uma pilha, por exemplo, pode ser implementada em um vetor ou em uma lista ligada.)  Cada implementação tem suas vantagens e desvantagens (por exemplo, algumas operações ficam mais rápidas enquanto outras ficam mais lentas).  É praticamente impossível fazer uma implementação universal, boa para todos os usuários.
• Um usuário do ADT é chamado cliente.  Um cliente só deve usar as operações especificadas na API e não deve ter acesso aos detalhes da implementação da ADT.
• Nesse esquema cliente / interface / implementação, a interface funciona como um contrato entre o cliente e a implementação.

Implementações de ADTs

• Em Java, cada ADT é implementado por uma classe.  (Veja Class (computer programming) na Wikipedia.)  As operações do ADT são implementadas como métodos da classe. 
• Cada instância (ou seja, cada caso particular) de uma classe é um objeto.  Para criar uma instância de uma classe use o comando  new  de Java.
• (Nem toda classe Java é implementação de um ADT. Uma classe Java também pode ser uma biblioteca de métodos, como StdOut, ou um programa cliente. Mas não se fazem instâncias de bibliotecas nem de programas cliente.)
• Um método de uma implementação de um ADT pode ser
  • de classe, ou estático, se vale para todas as instâncias da classe;
  • de instância, ou não-estático, se cada instância da classe tem sua própria cópia do método.

  Métodos estáticos são indicados pela palavra-chave static.

• Exemplo: Cria uma instância s da classe Out (que implementa fluxos de saída dirigidos a arquivos) e invoca o método println() da instância:

       Out s;
       s = new Out(nomedoarquivo);
       s.println("blablabla");
  

  As duas primeiras linhas poderiam ser juntadas:  Out s = new Out(nomedoarquivo);.

• Mais um exemplo: Cria uma instância x da classe String e invoca o método equals() da instância:

       String x = StdIn.readString();
       if (x.equals("-"))
          StdOut.println(pilha.pop());
       else pilha.push(x);
  

• Mais um exemplo: Cria uma instância de uma classe Stopwatch e invoca o método elapsedTime() da instância:

       Stopwatch t = new Stopwatch();
       return t.elapsedTime();