Tipo de dados abstrato

Na ciência da computação, um tipo de dado abstrato (ADT) é um modelo matemático para tipos de dados. Um tipo de dado abstrato é definido pelo seu comportamento (semântica) do ponto de vista de um usuário, dos dados, especificamente em termos de possíveis valores, possíveis operações sobre dados desse tipo e o comportamento destas operações. Esse modelo matemático contrasta com estruturas de dados, que são representações concretas de dados e são o ponto de vista de um implementador, não de um usuário.

Formalmente, um ADT pode ser definido como uma "classe de objetos cujo comportamento lógico é definido por um conjunto de valores e um conjunto de operações"; isso é análogo a uma estrutura algébrica em matemática. O que significa "comportamento" varia de acordo com o autor, com os dois principais tipos de especificações formais para o comportamento sendo especificação axiomática (algébrica) e um modelo abstrato; estes correspondem à semântica axiomática e à semântica operacional de um resumo máquina, respectivamente. Alguns autores também incluem a complexidade computacional ("custo"), tanto em termos de tempo (para operações de computação) quanto de espaço (para representar valores). Na prática, muitos tipos de dados comuns não são ADTs, pois a abstração não é perfeita e os usuários devem estar cientes de problemas como estouro aritmético devido à representação. Por exemplo, os números inteiros geralmente são armazenados como valores de largura fixa (números binários de 32 ou 64 bits) e, portanto, apresentam estouro de número inteiro se o valor máximo for excedido.

ADTs são um conceito teórico, em ciência da computação, usado no projeto e análise de algoritmos, estruturas de dados e sistemas de software, e não correspondem a recursos específicos de linguagens de computador - linguagens de computador convencionais não suportam diretamente ADTs formalmente especificadas. No entanto, vários recursos de linguagem correspondem a certos aspectos dos ADTs e são facilmente confundidos com os ADTs propriamente ditos; isso inclui tipos abstratos, tipos de dados opacos, protocolos e design por contrato. Os ADTs foram propostos pela primeira vez por Barbara Liskov e Stephen N. Zilles em 1974, como parte do desenvolvimento da linguagem CLU.

Tipos de dados abstratos

Por exemplo, números inteiros são um ADT, definido como os valores..., −2, −1, 0, 1, 2,..., e pelas operações de adição, subtração, multiplicação e divisão, juntas com maior que, menor que, etc., que se comportam de acordo com a matemática familiar (com cuidado com a divisão inteira), independentemente de como os inteiros são representados pelo computador. Explicitamente, "comportamento" inclui obedecer a vários axiomas (associatividade e comutatividade da adição, etc.) e pré-condições nas operações (não pode dividir por zero). Normalmente, os números inteiros são representados em uma estrutura de dados como números binários, na maioria das vezes como complemento de dois, mas podem ser decimais codificados em binário ou em unidades. complementam, mas para a maioria dos propósitos o usuário pode trabalhar com a abstração ao invés da escolha concreta de representação, e pode simplesmente usar os dados como se o tipo fosse verdadeiramente abstrato.

Um ADT consiste não apenas em operações, mas também em um domínio de valores e de restrições nas operações definidas. Uma "interface" normalmente refere-se apenas às operações e talvez algumas das restrições nas operações, como pré-condições e pós-condições; mas não a outras restrições, como relações entre as operações.

Por exemplo, uma pilha abstrata, que é uma estrutura de último a entrar, primeiro a sair, pode ser definida por três operações: push, que insere um item de dados na pilha; pop, que remove um item de dados dele; e peek ou top, que acessa um item de dados no topo da pilha sem remoção. Uma fila abstrata, que é uma estrutura primeiro a entrar, primeiro a sair, também teria três operações: enfileirar, que insere um item de dados na fila; dequeue, que remove o primeiro item de dados dele; e front, que acessa e atende o primeiro item de dados na fila. Se essas fossem todas as definições, não haveria como diferenciar esses dois tipos de dados e seu comportamento de ordenação esperado muito diferente. Assim, é introduzida uma restrição que para uma pilha especifica que cada pop sempre retorna (e remove) o item enviado mais recentemente que ainda não foi enviado, e para uma fila (em contraste) especifica que pop opera no item enviado menos recentemente.

Ao analisar a eficiência dos algoritmos, pode-se também especificar que todas as operações levam o mesmo tempo, independentemente de quantos itens de dados foram inseridos na pilha, e que a pilha usa uma quantidade constante de armazenamento para cada elemento. No entanto, os limites de tempo nem sempre são considerados parte da definição de um ADT.

Introdução

Tipos de dados abstratos são entidades puramente teóricas, usadas (entre outras coisas) para simplificar a descrição de algoritmos abstratos, para classificar e avaliar estruturas de dados e para descrever formalmente os sistemas de tipos de linguagens de programação. No entanto, um ADT pode ser implementado por tipos de dados específicos ou estruturas de dados, de várias maneiras e em muitas linguagens de programação; ou descrito em uma linguagem de especificação formal. ADTs são frequentemente implementados como módulos: a interface do módulo declara procedimentos que correspondem às operações ADT, às vezes com comentários que descrevem as restrições. Essa estratégia de ocultação de informações permite que a implementação do módulo seja alterada sem atrapalhar os programas clientes.

O termo tipo de dado abstrato também pode ser considerado como uma abordagem generalizada de várias estruturas algébricas, como redes, grupos e anéis. A noção de tipos de dados abstratos está relacionada ao conceito de abstração de dados, importante em programação orientada a objetos e design por metodologias de contrato para desenvolvimento de software.

Definindo um tipo de dado abstrato

Um tipo de dados abstrato é definido como um modelo matemático dos objetos de dados que compõem um tipo de dados, bem como as funções que operam nesses objetos. Não há convenções padrão para defini-los. Uma ampla divisão pode ser traçada entre "imperativo" (ou "operacional") e "funcional" (ou "axiomático") estilos de definição.

Definição de estilo imperativo

Na teoria das linguagens de programação imperativas, uma estrutura de dados abstrata é concebida como uma entidade que é mutável—o que significa que ela pode estar em diferentes estados em momentos diferentes. Algumas operações podem alterar o estado do ADT; portanto, a ordem em que as operações são avaliadas é importante, e uma mesma operação nas mesmas entidades pode ter efeitos diferentes se executada em momentos diferentes. Isso é análogo às instruções de um computador ou aos comandos e procedimentos de uma linguagem imperativa. Para enfatizar essa visão, costuma-se dizer que as operações são executadas ou aplicadas, em vez de avaliadas, semelhante ao estilo imperativo frequentemente usado quando descrevendo algoritmos abstratos. (Veja The Art of Computer Programming por Donald Knuth para mais detalhes).

Variável abstrata

Definições de estilo imperativo de ADT geralmente dependem do conceito de uma variável abstrata, que pode ser considerada como a ADT não trivial mais simples. Uma variável abstrata V é uma entidade mutável que admite duas operações:

• loja(V, x) onde x é um valor de natureza não especificada;
• Vamos.(V), que produz um valor,

com a restrição que

• Vamos.(V) sempre retorna o valor x usado no mais recente loja(V, x) operação na mesma variável V.

A busca antes do armazenamento pode ser proibida, definida para ter um determinado resultado ou (menos desejável), deixar o comportamento não especificado.

Como em muitas linguagens de programação, a operação store(V, x) geralmente é escrita como V ← x (ou alguma notação semelhante) e fetch(V) está implícito sempre que uma variável V é usada em um contexto onde um valor é necessário. Assim, por exemplo, V ← V + 1 é comumente entendido como uma abreviação de loja(V, obter(V) + 1).

Nesta definição, assume-se implicitamente que os nomes são sempre distintos: armazenar um valor em uma variável U não tem efeito sobre o estado de uma variável distinta V. Para tornar essa suposição explícita, pode-se adicionar a restrição de que

• se U e V são variáveis distintas, a sequência { loja(U, x); loja(V, Sim.) } é equivalente a { loja(V, Sim.); loja(U, x) }.

Em geral, as definições de ADT geralmente assumem que qualquer operação que altere o estado de uma instância de ADT não tem efeito sobre o estado de qualquer outra instância da mesma ADT, a menos que os axiomas de ADT definam certas instâncias como conectadas (consulte alias) em uma maneira específica. As conexões mais comuns incluem:

• Aliasing, em que dois ou mais nomes se referem ao mesmo objeto de dados.
• Composição, em que um ADT é definido para conter instâncias de (o mesmo ou outro) ADTs.
• Referência, em que um ADT é definido para se referir a instância de (o mesmo ou outro) ADTs.

Por exemplo, ao estender a definição de uma variável abstrata para incluir registros abstratos, as operações sobre um campo F de uma variável de registro R, envolvem claramente F , que é distinto, mas também parte de, R.

A definição de um ADT pode restringir o(s) valor(es) armazenado(s) para suas instâncias, a membros de um conjunto específico X chamado intervalo dessas variáveis. Por exemplo, um ADT para um agregado, como uma Pilha ou Fila, pode restringir todos os itens na fila a serem inteiros ou, pelo menos, a serem todos de um único tipo (consulte homogeneidade). Como nas linguagens de programação, tais restrições podem simplificar a descrição e análise de algoritmos e melhorar sua legibilidade.

Observe que esta definição não implica nada sobre o resultado da avaliação de fetch(V) quando V é não inicializado , ou seja, antes de realizar qualquer operação store no V. Um algoritmo que faz isso pode ser considerado inválido, seja (a) porque o ADT proíbe tal operação ou (b) simplesmente porque seu efeito não é definido pelo ADT. No entanto, existem alguns algoritmos importantes cuja eficiência depende fortemente da suposição de que tal fetch é legal e retorna algum valor arbitrário no intervalo da variável.)

Criação de instância

Alguns algoritmos precisam criar novas instâncias de algum ADT (como novas variáveis ou novas pilhas). Para descrever tais algoritmos, geralmente se inclui na definição do ADT uma operação create() que produz uma instância do ADT, geralmente com axiomas equivalentes a

• o resultado de criar() é distinta de qualquer instância já em uso pelo algoritmo.

Este axioma pode ser reforçado para excluir também aliasing parcial com outras instâncias. Para uso prático, como axiom ainda pode permitir implementações de create() para produzir uma instância criada anteriormente que se tornou inacessível ao programa; no entanto, definir que tal instância ainda é "o mesmo" é difícil, especialmente no abstrato (embora mesmo um bloco de memória reutilizado seja apenas "o mesmo objeto" em certos sentidos).

Exemplo: pilha abstrata (imperativo)

Como outro exemplo, uma definição de estilo imperativo de uma pilha abstrata poderia especificar que o estado de uma pilha S pode ser modificado apenas pelas operações

• Empurre.(S, x), onde x alguns valor de natureza não especificada;
• Pop(S), que produz um valor como resultado,

com a restrição que

• Para qualquer valor x e qualquer variável abstrata V, a sequência de operações { Empurre.(S, x); V ← Pop(S) } é equivalente a V ← x.

Como a atribuição V ← x, por definição, não pode mudar o estado de S, essa condição implica que V ← pop(S) restaura S ao estado que tinha antes do push( S, x). Desta condição e das propriedades das variáveis abstratas segue-se, por exemplo, que a sequência

(Empurre.(S, x); Empurre.(S, Sim.); U ← Pop(S); Empurre.(S, zangão.); V ← Pop(S); W ← Pop(S?

onde x, y e z são quaisquer valores, e U, V, W são variáveis distintas emparelhadas, é equivalente a

(U ← Sim.; V ← zangão.; W ← x ?

Aqui é assumido implicitamente que as operações em uma instância de pilha não modificam o estado de qualquer outra instância ADT, incluindo outras pilhas; aquilo é,

• Para quaisquer valores x, Sim., e quaisquer pilhas distintas S e T, a sequência { Empurre.(S, x); Empurre.(T, Sim.) } é equivalente a { Empurre.(T, Sim.); Empurre.(S, x) }.

Uma definição de pilha abstrata geralmente inclui também uma função de valor booleano empty(S) e uma operação create() que retorna uma pilha exemplo, com axiomas equivalentes a

• criar() ≠ S para qualquer pilha anterior S (uma pilha recém-criada é distinta de todas as pilhas anteriores);
• vazio(criar()) (uma pilha recém-criada está vazia);
• não vazio(Empurre.(S, x)) (empurrar algo em uma pilha torna-o não vazio).

Estilo de instância única

Às vezes, um ADT é definido como se apenas uma instância dele existisse durante a execução do algoritmo e todas as operações fossem aplicadas a essa instância, que não é notada explicitamente. Por exemplo, a pilha abstrata acima poderia ter sido definida com as operações push(x) e pop(), que operam no the apenas pilha existente. As definições de ADT neste estilo podem ser facilmente reescritas para admitir várias instâncias coexistentes do ADT, adicionando um parâmetro de instância explícito (como S no exemplo anterior) a cada operação que usa ou modifica a instância implícita.

Por outro lado, alguns ADTs não podem ser definidos significativamente sem assumir várias instâncias. Este é o caso quando uma única operação usa duas instâncias distintas do ADT como parâmetros. Por exemplo, considere aumentar a definição da pilha abstrata com uma operação comparar(S, T) que verifica se as pilhas S e T contêm os mesmos itens na mesma ordem.

Definição de estilo funcional

Outra forma de definir um ADT, mais próxima do espírito da programação funcional, é considerar cada estado da estrutura como uma entidade separada. Nessa visão, qualquer operação que modifique o ADT é modelada como uma função matemática que usa o estado antigo como argumento e retorna o novo estado como parte do resultado. Ao contrário das operações imperativas, essas funções não têm efeitos colaterais. Portanto, a ordem em que são avaliados é irrelevante, e a mesma operação aplicada aos mesmos argumentos (incluindo os mesmos estados de entrada) sempre retornará os mesmos resultados (e estados de saída).

Na visão funcional, em particular, não há nenhuma maneira (ou necessidade) de definir uma "variável abstrata" com a semântica de variáveis imperativas (ou seja, com operações fetch e store). Em vez de armazenar valores em variáveis, eles são passados como argumentos para funções.

Exemplo: pilha abstrata (funcional)

Por exemplo, uma definição de estilo funcional completa de uma pilha abstrata poderia usar as três operações:

• Empurre.: leva um estado de pilha e um valor arbitrário, retorna um estado de pilha;
• topo: leva um estado de pilha, retorna um valor;
• Pop: leva um estado de pilha, retorna um estado de pilha.

Em uma definição de estilo funcional, não há necessidade de uma operação criar. De fato, não há noção de "instância de pilha". Os estados da pilha podem ser considerados estados potenciais de uma única estrutura de pilha, e os estados de duas pilhas que contêm os mesmos valores na mesma ordem são considerados estados idênticos. Na verdade, essa exibição espelha o comportamento de algumas implementações concretas, como listas encadeadas com contras de hash.

Em vez de create(), uma definição de estilo funcional de uma pilha abstrata pode assumir a existência de um estado de pilha especial, a pilha vazia, designada por um especial símbolo como Λ ou "()"; ou defina uma operação bottom() que não receba argumentos e retorne esse estado de pilha especial. Note que os axiomas implicam que

• Empurre.(A) x) ≠ Λ.

Em uma definição de estilo funcional de uma pilha, não é necessário um predicado vazio: em vez disso, pode-se testar se uma pilha está vazia testando se ela é igual a Λ.

Observe que esses axiomas não definem o efeito de top(s) ou pop(s), a menos que s seja um estado de pilha retornado por um push. Como push deixa a pilha não vazia, essas duas operações são indefinidas (portanto, inválidas) quando s = Λ. Por outro lado, os axiomas (e a falta de efeitos colaterais) implicam que push(s, x) = push(t, y) se e somente se x = y e s = t.

Como em alguns outros ramos da matemática, costuma-se assumir também que os estados da pilha são apenas aqueles cuja existência pode ser provada a partir dos axiomas em um número finito de etapas. No exemplo de pilha abstrata acima, esta regra significa que cada pilha é uma sequência finita de valores, que se torna a pilha vazia (Λ) após um número finito de pops. Por si só, os axiomas acima não excluem a existência de pilhas infinitas (que podem ser poppara sempre, cada vez produzindo um estado diferente) ou pilhas circulares (que retornam ao mesmo estado após um número finito de pops). Em particular, eles não excluem estados s como pop(s) = s ou push (s, x) = s para algum x. No entanto, uma vez que não é possível obter tais estados de pilha com as operações dadas, eles são considerados "não existem".

Se deve incluir complexidade

Além do comportamento em termos de axiomas, também é possível incluir, na definição de uma operação ADT, sua complexidade algorítmica. Alexander Stepanov, designer da C++ Standard Template Library, incluiu garantias de complexidade na especificação STL, argumentando:

A razão para introduzir a noção de tipos de dados abstratos foi permitir módulos de software intercambiáveis. Você não pode ter módulos intercambiáveis a menos que esses módulos compartilhem comportamento de complexidade semelhante. Se eu substituir um módulo com outro módulo com o mesmo comportamento funcional, mas com diferentes tradeoffs de complexidade, o usuário deste código será desagradávelmente surpreendido. Eu poderia dizer-lhe tudo o que eu gosto sobre a abstração de dados, e ele ainda não iria querer usar o código. As afirmações de complexidade têm de fazer parte da interface.

—Alexander Stepanov

Vantagens da digitação abstrata de dados

Encapsulação

A abstração fornece uma promessa de que qualquer implementação do ADT tem certas propriedades e habilidades; saber disso é tudo o que é necessário para fazer uso de um objeto ADT. Tipo de dados perimitivo e não perimitivo.

Localização da mudança

O código que usa um objeto ADT não precisará ser editado se a implementação do ADT for alterada. Como qualquer alteração na implementação ainda deve estar em conformidade com a interface e como o código que usa um objeto ADT pode se referir apenas a propriedades e habilidades especificadas na interface, as alterações podem ser feitas na implementação sem exigir nenhuma alteração no código em que o ADT é usado.

Flexibilidade

Diferentes implementações do ADT, tendo todas as mesmas propriedades e habilidades, são equivalentes e podem ser usadas de forma intercambiável no código que usa o ADT. Isso dá uma grande flexibilidade ao usar objetos ADT em diferentes situações. Por exemplo, diferentes implementações do ADT podem ser mais eficientes em diferentes situações; é possível usar cada um na situação em que são preferíveis, aumentando assim a eficiência geral.

Operações típicas

Algumas operações frequentemente especificadas para ADTs (possivelmente sob outros nomes) são

• Comparar(S, )), que testa se os estados de duas instâncias são equivalentes em algum sentido;
• Hah!(S), que computa alguma função hash padrão do estado da instância;
• impressão(S) ou mostrar(S), que produz uma representação legível humana do estado da instância.

Nas definições de ADT de estilo imperativo, muitas vezes também encontramos

• criar(), que produz uma nova instância do ADT;
• inicializar(S), que prepara uma instância recém-criada S para outras operações, ou redefini-la para algum "estado inicial";
• cópia(S, )), que coloca instância S em um estado equivalente ao de );
• clone()), que executa S ← criar(cópia(S, )), e retorna S;
• grátis(S) ou destruir(S), que recupera a memória e outros recursos usados por S.

A operação livre normalmente não é relevante ou significativa, já que os ADTs são entidades teóricas que não "usam memória". No entanto, pode ser necessário quando se precisa analisar o armazenamento utilizado por um algoritmo que utiliza o ADT. Nesse caso, são necessários axiomas adicionais que especifiquem quanta memória cada instância do ADT usa, em função de seu estado, e quanto dela é retornado ao pool livre.

Exemplos

Alguns ADTs comuns, que se mostraram úteis em uma grande variedade de aplicações, são

Cada um desses ADTs pode ser definido de várias maneiras e variantes, não necessariamente equivalentes. Por exemplo, uma pilha abstrata pode ou não ter uma operação count que informa quantos itens foram enviados e ainda não foram exibidos. Esta escolha faz a diferença não só para os seus clientes como também para a implementação.

Tipo de dados gráfico abstrato

Uma extensão do ADT para computação gráfica foi proposta em 1979: um tipo abstrato de dados gráficos (AGDT). Foi apresentado por Nadia Magnenat Thalmann e Daniel Thalmann. Os AGDTs fornecem as vantagens dos ADTs com facilidades para construir objetos gráficos de forma estruturada.

Implementação

Implementar um ADT significa fornecer um procedimento ou função para cada operação abstrata. As instâncias do ADT são representadas por alguma estrutura de dados concreta que é manipulada por esses procedimentos, de acordo com as especificações do ADT.

Normalmente, existem muitas maneiras de implementar o mesmo ADT, usando várias estruturas de dados concretas diferentes. Assim, por exemplo, uma pilha abstrata pode ser implementada por uma lista encadeada ou por um array.

Para evitar que os clientes dependam da implementação, um ADT geralmente é empacotado como um tipo de dados opaco em um ou mais módulos, cuja interface contém apenas a assinatura (número e tipos dos parâmetros e resultados) das operações. A implementação do módulo - ou seja, os corpos dos procedimentos e a estrutura de dados concreta usada - pode ser ocultada da maioria dos clientes do módulo. Isso torna possível alterar a implementação sem afetar os clientes. Se a implementação for exposta, ela é conhecida como um tipo de dados transparente.

Ao implementar um ADT, cada instância (em definições de estilo imperativo) ou cada estado (em definições de estilo funcional) geralmente é representado por um identificador de algum tipo.

Linguagens modernas orientadas a objetos, como C++ e Java, suportam uma forma de tipos de dados abstratos. Quando uma classe é usada como um tipo, é um tipo abstrato que se refere a uma representação oculta. Nesse modelo, um ADT é normalmente implementado como uma classe e cada instância do ADT é geralmente um objeto dessa classe. A interface do módulo normalmente declara os construtores como procedimentos comuns e a maioria das outras operações ADT como métodos dessa classe. No entanto, tal abordagem não encapsula facilmente múltiplas variantes representacionais encontradas em um ADT. Também pode minar a extensibilidade de programas orientados a objetos. Em um programa puramente orientado a objetos que usa interfaces como tipos, os tipos referem-se a comportamentos, não representações.

Exemplo: implementação da pilha abstrata

Como exemplo, aqui está uma implementação da pilha abstrata acima na linguagem de programação C.

Interface de estilo imperativo

Uma interface de estilo imperativo pode ser:

tipo de defesa Estranho pilha_Rep pilha_Rep; // tipo: representação da instância da pilha (gravação opaca)tipo de defesa pilha_Rep* Empilhadeiras; // tipo: lidar com uma instância de pilha (ponteiro opaco)tipo de defesa vazio* Empilhadeiras; // tipo: valor armazenado na instância da pilha (endereço arbitrário)Empilhadeiras stack_create(vazio); // cria uma nova instância de pilha vaziavazio O que se passa?(Empilhadeiras S, Empilhadeiras x); // adiciona um item no topo da pilhaEmpilhadeiras O que é?(Empilhadeiras S); // remove o item superior da pilha e devolve-o- Sim. O que é isso?(Empilhadeiras S); // verifica se a pilha está vazia

Esta interface pode ser usada da seguinte maneira:

#include #  // inclui a interface da pilhaEmpilhadeiras S = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = stack_create(); // cria uma nova instância de pilha vazia- Não. x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 17.;O que se passa?(S, >x); // adiciona o endereço de x na parte superior da pilhavazio* Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = O que é?(S); // remove o endereço de x da pilha e devolve-ose (O que é isso?(S) ( ? // faz algo se a pilha estiver vazia

Essa interface pode ser implementada de várias maneiras. A implementação pode ser arbitrariamente ineficiente, pois a definição formal do ADT, acima, não especifica quanto espaço a pilha pode ocupar, nem quanto tempo cada operação deve levar. Também não especifica se o estado da pilha s continua a existir após uma chamada x ← pop(s).

Na prática, a definição formal deve especificar que o espaço é proporcional ao número de itens enviados e ainda não exibidos; e que cada uma das operações acima deve terminar em um tempo constante, independentemente desse número. Para atender a essas especificações adicionais, a implementação pode usar uma lista encadeada ou um array (com redimensionamento dinâmico) juntamente com dois inteiros (uma contagem de itens e o tamanho do array).

Interface de estilo funcional

As definições de ADT de estilo funcional são mais apropriadas para linguagens de programação funcionais e vice-versa. No entanto, pode-se fornecer uma interface de estilo funcional mesmo em uma linguagem imperativa como C. Por exemplo:

tipo de defesa Estranho pilha_Rep pilha_Rep; // tipo: representação do estado da pilha (gravação opaca)tipo de defesa pilha_Rep* Empilhadeiras; // tipo: lidar com um estado de pilha (ponteiro opaco)tipo de defesa vazio* Empilhadeiras; // tipo: valor de um estado de pilha (endereço arbitrário)Empilhadeiras O que é isso?(vazio); // retorna o estado da pilha vaziaEmpilhadeiras O que se passa?(Empilhadeiras S, Empilhadeiras x); // adiciona um item no topo do estado da pilha e retorna o estado da pilha resultanteEmpilhadeiras O que é?(Empilhadeiras S); // remove o item superior do estado da pilha e retorna o estado da pilha resultanteEmpilhadeiras Empilhadeiras(Empilhadeiras S); // retorna o item superior do estado da pilha

Bibliotecas ADT

Muitas linguagens de programação modernas, como C++ e Java, vêm com bibliotecas padrão que implementam vários ADTs comuns, como os listados acima.

Tipos de dados abstratos integrados

A especificação de algumas linguagens de programação é intencionalmente vaga sobre a representação de certos tipos de dados embutidos, definindo apenas as operações que podem ser feitas neles. Portanto, esses tipos podem ser vistos como "ADTs integrados". Exemplos são os arrays em muitas linguagens de script, como Awk, Lua e Perl, que podem ser considerados como uma implementação da lista abstrata.