Tipo de datos abstractos

En informática, un tipo de datos abstracto (ADT) es un modelo matemático para tipos de datos. Un tipo de dato abstracto se define por su comportamiento (semántica) desde el punto de vista de un usuario, de los datos, específicamente en términos de posibles valores, posibles operaciones sobre datos de este tipo, y el comportamiento de estas operaciones. Este modelo matemático contrasta con las estructuras de datos, que son representaciones concretas de datos y son el punto de vista de un implementador, no de un usuario.

Formalmente, un ADT puede definirse como una "clase de objetos cuyo comportamiento lógico está definido por un conjunto de valores y un conjunto de operaciones"; esto es análogo a una estructura algebraica en matemáticas. ¿Qué se entiende por "comportamiento" varía según el autor, siendo los dos tipos principales de especificaciones formales para el comportamiento especificación axiomática (algebraica) y un modelo abstracto; estos corresponden a la semántica axiomática y la semántica operativa de un modelo abstracto. máquina, respectivamente. Algunos autores también incluyen la complejidad computacional ("costo"), tanto en términos de tiempo (para operaciones de cálculo) como de espacio (para representar valores). En la práctica, muchos tipos de datos comunes no son ADT, ya que la abstracción no es perfecta y los usuarios deben ser conscientes de problemas como el desbordamiento aritmético que se debe a la representación. Por ejemplo, los números enteros a menudo se almacenan como valores de ancho fijo (números binarios de 32 o 64 bits) y, por lo tanto, experimentan un desbordamiento de números enteros si se excede el valor máximo.

Los ADT son un concepto teórico, en informática, que se utiliza en el diseño y análisis de algoritmos, estructuras de datos y sistemas de software, y no corresponden a características específicas de los lenguajes informáticos; los lenguajes informáticos convencionales no admiten directamente los ADT especificados formalmente.. Sin embargo, varias características del lenguaje corresponden a ciertos aspectos de los ADT y se confunden fácilmente con los ADT propiamente dichos; estos incluyen tipos abstractos, tipos de datos opacos, protocolos y diseño por contrato. Los ADT fueron propuestos por primera vez por Barbara Liskov y Stephen N. Zilles en 1974, como parte del desarrollo del lenguaje CLU.

Tipos de datos abstractos

Por ejemplo, los números enteros son un ADT, definidos como los valores..., −2, −1, 0, 1, 2,..., y por las operaciones de suma, resta, multiplicación y división, juntos con mayor que, menor que, etc., que se comportan de acuerdo con las matemáticas familiares (con atención a la división de enteros), independientemente de cómo la computadora represente los enteros. Explícitamente, "comportamiento" incluye obedecer varios axiomas (asociatividad y conmutatividad de la suma, etc.), y condiciones previas en las operaciones (no se puede dividir por cero). Por lo general, los números enteros se representan en una estructura de datos como números binarios, con mayor frecuencia como complemento a dos, pero pueden ser decimales codificados en binario o en unidades. complemento, pero para la mayoría de los propósitos, el usuario puede trabajar con la abstracción en lugar de la elección concreta de representación, y simplemente puede usar los datos como si el tipo fuera verdaderamente abstracto.

Un ADT consta no solo de operaciones, sino también de un dominio de valores y de restricciones en las operaciones definidas. Una "interfaz" generalmente se refiere solo a las operaciones, y quizás a algunas de las restricciones sobre las operaciones, como las condiciones previas y posteriores; pero no a otras restricciones como las relaciones entre las operaciones.

Por ejemplo, una pila abstracta, que es una estructura de último en entrar, primero en salir, podría definirse mediante tres operaciones: push, que inserta un elemento de datos en la pila; pop, que elimina un elemento de datos; y peek o top, que accede a un elemento de datos en la parte superior de la pila sin eliminarlo. Una cola abstracta, que es una estructura de primero en entrar, primero en salir, también tendría tres operaciones: enqueue, que inserta un elemento de datos en la cola; dequeue, que elimina el primer elemento de datos; y front, que accede y sirve el primer elemento de datos en la cola. Si estas fueran las definiciones completas, no habría forma de diferenciar estos dos tipos de datos y su muy diferente comportamiento de orden esperado. Por lo tanto, se introduce una restricción que para una pila especifica que cada pop siempre devuelve (y elimina) el elemento empujado más recientemente que aún no se ha sacado, y para una cola (en contraste) especifica que pop opera en el elemento empujado menos recientemente.

Al analizar la eficiencia de los algoritmos, también se puede especificar que todas las operaciones toman el mismo tiempo sin importar cuántos elementos de datos se hayan insertado en la pila, y que la pila usa una cantidad constante de almacenamiento para cada elemento. Sin embargo, los límites de tiempo no siempre se consideran parte de la definición de un ADT.

Introducción

Los tipos de datos abstractos son entidades puramente teóricas que se utilizan (entre otras cosas) para simplificar la descripción de algoritmos abstractos, para clasificar y evaluar estructuras de datos y para describir formalmente los sistemas de tipos de los lenguajes de programación. Sin embargo, un ADT puede implementarse mediante tipos de datos o estructuras de datos específicos, de muchas maneras y en muchos lenguajes de programación; o descrito en un lenguaje de especificación formal. Los ADT a menudo se implementan como módulos: la interfaz del módulo declara procedimientos que corresponden a las operaciones de ADT, a veces con comentarios que describen las restricciones. Esta estrategia de ocultación de información permite cambiar la implementación del módulo sin perturbar los programas del cliente.

El término tipo de datos abstractos también se puede considerar como un enfoque generalizado de varias estructuras algebraicas, como redes, grupos y anillos. La noción de tipos de datos abstractos está relacionada con el concepto de abstracción de datos, importante en la programación orientada a objetos y el diseño por metodologías de contrato para el desarrollo de software.

Definir un tipo de datos abstracto

Un tipo de datos abstracto se define como un modelo matemático de los objetos de datos que componen un tipo de datos, así como las funciones que operan en estos objetos. No existen convenciones estándar para definirlos. Se puede trazar una amplia división entre "imperativo" (u "operativo") y "funcional" (o "axiomático") estilos de definición.

Definición de estilo imperativo

En la teoría de los lenguajes de programación imperativos, una estructura de datos abstracta se concibe como una entidad que es mutable, lo que significa que puede estar en diferentes estados en diferentes momentos. Algunas operaciones pueden cambiar el estado del ADT; por lo tanto, el orden en que se evalúan las operaciones es importante y la misma operación en las mismas entidades puede tener efectos diferentes si se ejecuta en momentos diferentes. Esto es análogo a las instrucciones de una computadora, oa los comandos y procedimientos de un lenguaje imperativo. Para subrayar este punto de vista, se acostumbra decir que las operaciones son ejecutadas o aplicadas, en lugar de evaluadas, similar al estilo imperativo que se usa a menudo cuando describir algoritmos abstractos. (Consulte El arte de la programación informática de Donald Knuth para obtener más detalles).

Variable abstracta

Las definiciones de ADT de estilo imperativo a menudo dependen del concepto de una variable abstracta, que puede considerarse como el ADT no trivial más simple. Una variable abstracta V es una entidad mutable que admite dos operaciones:

• tienda()V, xDonde x es un valor de naturaleza no especificada;
• .()V), que da un valor,

con la restricción de que

• .()V) siempre devuelve el valor x usado en el más reciente tienda()V, x) operación en la misma variable V.

Se puede prohibir la obtención antes de almacenar, definir para que tenga un resultado determinado o (menos deseable), dejar el comportamiento sin especificar.

Como en muchos lenguajes de programación, la operación store(V, x) a menudo se escribe V ← x (o alguna notación similar), y fetch(V) están implícitos cada vez que se usa una variable V en un contexto donde se requiere un valor. Así, por ejemplo, V ← V + 1 se entiende comúnmente como una abreviatura de store(V, buscar(V) + 1).

En esta definición, se supone implícitamente que los nombres siempre son distintos: almacenar un valor en una variable U no tiene ningún efecto sobre el estado de una variable distinta V. Para hacer explícita esta suposición, se podría agregar la restricción de que

• si U y V son variables distintas, la secuencia { tienda()U, x); tienda()V, Sí.} es equivalente a { tienda()V, Sí.); tienda()U, x}.

De manera más general, las definiciones de ADT a menudo asumen que cualquier operación que cambie el estado de una instancia de ADT no tiene efecto en el estado de ninguna otra instancia del mismo ADT, a menos que los axiomas de ADT definan ciertas instancias como conectadas (ver alias) en una manera específica. Las conexiones más comunes incluyen:

• Aliasing, en el que dos o más nombres se refieren al mismo objeto de datos exacto.
• Composición, en la que se define un ADT para contener casos de (el mismo u otros) TDA.
• Referencia, en la que se define un ADT para referirse a instancias (el mismo u otros) ADTs.

Por ejemplo, cuando se amplía la definición de una variable abstracta para incluir registros abstractos, las operaciones sobre un campo F de una variable de registro R implican claramente F , que es distinto de, pero también parte de, R.

La definición de un ADT puede restringir los valores almacenados para sus instancias, a miembros de un conjunto específico X denominado rango de esas variables. Por ejemplo, un ADT para un agregado, como una Pila o una Cola, puede restringir todos los elementos de la cola para que sean enteros, o al menos para que todos sean de un solo tipo (ver homogeneidad). Al igual que en los lenguajes de programación, tales restricciones pueden simplificar la descripción y el análisis de los algoritmos y mejorar su legibilidad.

Tenga en cuenta que esta definición no implica nada sobre el resultado de evaluar fetch(V) cuando V está sin inicializar , es decir, antes de realizar cualquier operación almacenar en V. Un algoritmo que lo haga puede considerarse inválido, ya sea (a) porque el ADT prohíbe tal operación, o (b) simplemente porque su efecto no está definido por el ADT. Sin embargo, hay algunos algoritmos importantes cuya eficiencia depende en gran medida de la suposición de que tal fetch es legal y devuelve algún valor arbitrario en el rango de la variable).

Creación de instancia

Algunos algoritmos necesitan crear nuevas instancias de algunos ADT (como nuevas variables o nuevas pilas). Para describir dichos algoritmos, generalmente se incluye en la definición de ADT una operación crear() que produce una instancia de ADT, generalmente con axiomas equivalentes a

• el resultado de crear() es distinto de cualquier caso ya utilizado por el algoritmo.

Este axioma puede fortalecerse para excluir también el alias parcial con otras instancias. Para uso práctico, como axiom, aún puede permitir implementaciones de create() para generar una instancia creada previamente que se ha vuelto inaccesible para el programa; sin embargo, definir que tal instancia incluso es "lo mismo" es difícil, especialmente en abstracto (aunque incluso un bloque de memoria reutilizado es solo "el mismo objeto" en ciertos sentidos).

Ejemplo: pila abstracta (imperativo)

Como otro ejemplo, una definición de estilo imperativo de una pila abstracta podría especificar que el estado de una pila S solo puede modificarse mediante las operaciones

• empujar()S, x), donde x es algo valor de naturaleza no especificada;
• pop()S), que produce un valor como resultado,

con la restricción de que

• Para cualquier valor x y cualquier variable abstracta V, la secuencia de operaciones { empujar()S, x); V ← pop()S} es equivalente a V ← x.

Dado que la asignación V ← x, por definición, no puede cambiar el estado de S, esta condición implica que V< /i> ← pop(S) restaura S al estado que tenía antes de push( S, x). De esta condición y de las propiedades de las variables abstractas, se sigue, por ejemplo, que la sucesión

{} empujar()S, x); empujar()S, Sí.); U ← pop()S); empujar()S, z); V ← pop()S); W ← pop()S)

donde x, y y z son valores cualesquiera, y U, V< /i>, W son variables distintas por pares, es equivalente a

{} U ← Sí.; V ← z; W ← x }

Aquí se supone implícitamente que las operaciones en una instancia de pila no modifican el estado de ninguna otra instancia de ADT, incluidas otras pilas; es decir,

• Para cualquier valor x, Sí., y cualquier pila distinta S y T, la secuencia { empujar()S, x); empujar()T, Sí.} es equivalente a { empujar()T, Sí.); empujar()S, x}.

Una definición de pila abstracta generalmente incluye también una función con valor booleano empty(S) y una operación create() que devuelve una pila ejemplo, con axiomas equivalentes a

• crear() ل S para cualquier pila anterior S (una pila recién creada es distinta de todas las pilas anteriores);
• vacío()crear()) (una pila creada recientemente está vacía);
• no vacío()empujar()S, x)) (pujar algo en una pila hace que no vacía).

Estilo de instancia única

A veces, un ADT se define como si solo existiera una instancia durante la ejecución del algoritmo, y todas las operaciones se aplicaron a esa instancia, lo que no se indica explícitamente. Por ejemplo, la pila abstracta anterior podría haberse definido con las operaciones push(x) y pop(), que operan en la solo la pila existente. Las definiciones de ADT en este estilo se pueden reescribir fácilmente para admitir múltiples instancias coexistentes de ADT, agregando un parámetro de instancia explícito (como S en el ejemplo anterior) a cada operación que usa o modifica la instancia implícita.

Por otro lado, algunos ADT no se pueden definir de manera significativa sin asumir varias instancias. Este es el caso cuando una sola operación toma dos instancias distintas del ADT como parámetros. Por ejemplo, considere aumentar la definición de la pila abstracta con una operación compare(S, T) que comprueba si las pilas S y T contienen los mismos elementos en el mismo orden.

Definición de estilo funcional

Otra forma de definir un ADT, más cercana al espíritu de la programación funcional, es considerar cada estado de la estructura como una entidad separada. En esta vista, cualquier operación que modifique el ADT se modela como una función matemática que toma el estado anterior como argumento y devuelve el estado nuevo como parte del resultado. A diferencia de las operaciones imperativas, estas funciones no tienen efectos secundarios. Por lo tanto, el orden en que se evalúan es irrelevante y la misma operación aplicada a los mismos argumentos (incluidos los mismos estados de entrada) siempre devolverá los mismos resultados (y estados de salida).

En la vista funcional, en particular, no hay manera (o necesidad) de definir una "variable abstracta" con la semántica de las variables imperativas (es decir, con las operaciones fetch y store). En lugar de almacenar valores en variables, uno los pasa como argumentos a funciones.

Ejemplo: pila abstracta (funcional)

Por ejemplo, una definición completa de estilo funcional de una pila abstracta podría usar las tres operaciones:

• empujar: toma un estado de pila y un valor arbitrario, devuelve un estado de pila;
• arriba: toma un estado de pila, devuelve un valor;
• pop: toma un estado de pila, devuelve un estado de pila.

En una definición de estilo funcional no hay necesidad de una operación crear. De hecho, no existe la noción de "instancia de pila". Los estados de pila se pueden considerar como estados potenciales de una estructura de pila única, y los estados de dos pilas que contienen los mismos valores en el mismo orden se consideran estados idénticos. Esta vista en realidad refleja el comportamiento de algunas implementaciones concretas, como las listas vinculadas con contras de hash.

En lugar de crear(), una definición de estilo funcional de una pila abstracta puede suponer la existencia de un estado de pila especial, la pila vacía, designada por un especial símbolo como Λ o "()"; o defina una operación bottom() que no tome argumentos y devuelva este estado de pila especial. Nótese que los axiomas implican que

• empujar(XXI) x) ل י.

En una definición de estilo funcional de una pila no se necesita un predicado vacío: en su lugar, se puede comprobar si una pila está vacía probando si es igual a Λ.

Tenga en cuenta que estos axiomas no definen el efecto de top(s) o pop(s), a menos que s sea un estado de pila devuelto por push. Dado que push deja la pila no vacía, esas dos operaciones no están definidas (por lo tanto, no son válidas) cuando s = Λ. Por otro lado, los axiomas (y la falta de efectos secundarios) implican que empujar(s, x) = empujar< /kbd>(t, y) si y solo si x = y y s = t.

Al igual que en otras ramas de las matemáticas, también se suele suponer que los estados de la pila son solo aquellos cuya existencia puede probarse a partir de los axiomas en un número finito de pasos. En el ejemplo de pila abstracta anterior, esta regla significa que cada pila es una secuencia finita de valores, que se convierte en la pila vacía (Λ) después de un número finito de pops. Por sí mismos, los axiomas anteriores no excluyen la existencia de pilas infinitas (que se pueden hacer estallarpara siempre, cada vez que producen un estado diferente) o pilas circulares (que vuelven al mismo estado después de un número finito de pops). En particular, no excluyen los estados s tales que pop(s) = s o push (s, x) = s para alguna x. Sin embargo, dado que no se pueden obtener dichos estados de pila con las operaciones dadas, se supone que "no existen".

Si incluir complejidad

Además del comportamiento en términos de axiomas, también es posible incluir, en la definición de una operación ADT, su complejidad algorítmica. Alexander Stepanov, diseñador de la biblioteca de plantillas estándar de C++, incluyó garantías de complejidad en la especificación STL, argumentando:

La razón para introducir la noción de tipos de datos abstractos era permitir módulos de software intercambiables. No puede tener módulos intercambiables a menos que estos módulos compartan un comportamiento de complejidad similar. Si sustituyo un módulo con otro módulo con el mismo comportamiento funcional, pero con diferentes oficios de complejidad, el usuario de este código se sorprenderá desagradablemente. Podría decirle todo lo que me gusta de la abstracción de datos, y él todavía no querría usar el código. Las afirmaciones de complejidad tienen que ser parte de la interfaz.

—Alexander Stepanov

Ventajas de escribir datos abstractos

Encapsulación

La abstracción promete que cualquier implementación del ADT tiene ciertas propiedades y habilidades; saber esto es todo lo que se requiere para hacer uso de un objeto ADT. Se usa con el tipo de datos en el lenguaje de programación Tipo de datos perimitivo y no perimitivo.

Localización del cambio

No será necesario editar el código que usa un objeto ADT si se cambia la implementación del ADT. Dado que cualquier cambio en la implementación aún debe cumplir con la interfaz, y dado que el código que usa un objeto ADT solo puede hacer referencia a las propiedades y capacidades especificadas en la interfaz, se pueden realizar cambios en la implementación sin necesidad de cambios en el código donde se usa el ADT..

Flexibilidad

Diferentes implementaciones del ADT, que tienen todas las mismas propiedades y habilidades, son equivalentes y pueden usarse de manera intercambiable en el código que usa el ADT. Esto brinda una gran flexibilidad al usar objetos ADT en diferentes situaciones. Por ejemplo, diferentes implementaciones del ADT pueden ser más eficientes en diferentes situaciones; es posible utilizar cada uno en la situación en la que son preferibles, aumentando así la eficiencia general.

Operaciones típicas

Algunas operaciones que a menudo se especifican para ADT (posiblemente con otros nombres) son

• comparar()s, t), que prueba si dos estados de instancias son equivalentes en algún sentido;
• hash()s), que computa alguna función de hash estándar del estado de la instancia;
• impresión()s) o show()s), que produce una representación legible humana del estado de la instancia.

En las definiciones ADT de estilo imperativo, a menudo se encuentran también

• crear(), que produce una nueva instancia del ADT;
• inicialización()s), que prepara una instancia recién creada s para otras operaciones, o lo reasienta a algún "estado inicial";
• Copia()s, t), que pone ejemplo s en un estado equivalente al de t;
• clone()t), que realiza s ← crear(), Copia()s, t), y regresa s;
• gratis()s) o destruir()s), que reclama la memoria y otros recursos utilizados por s.

La operación free normalmente no es relevante ni significativa, ya que los ADT son entidades teóricas que no "utilizan memoria". Sin embargo, puede ser necesario cuando se necesita analizar el almacenamiento utilizado por un algoritmo que utiliza el ADT. En ese caso, se necesitan axiomas adicionales que especifiquen cuánta memoria usa cada instancia de ADT, como una función de su estado, y qué cantidad se devuelve al grupo mediante gratis.

Ejemplos

Algunos ADT comunes, que han resultado útiles en una gran variedad de aplicaciones, son

Cada uno de estos ADT se puede definir de muchas maneras y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede o no tener una operación count que indica cuántos elementos se han empujado y aún no se han extraído. Esta elección marca la diferencia no solo para sus clientes sino también para la implementación.

Tipo de datos gráficos abstractos

En 1979 se propuso una extensión de ADT para gráficos por computadora: un tipo de datos gráficos abstractos (AGDT). Fue presentado por Nadia Magnenat Thalmann y Daniel Thalmann. Los AGDT brindan las ventajas de los ADT con facilidades para construir objetos gráficos de forma estructurada.

Implementación

Implementar un ADT significa proporcionar un procedimiento o función para cada operación abstracta. Las instancias de ADT están representadas por alguna estructura de datos concreta que es manipulada por esos procedimientos, de acuerdo con las especificaciones de ADT.

Por lo general, hay muchas formas de implementar el mismo ADT, utilizando varias estructuras de datos concretas diferentes. Así, por ejemplo, una pila abstracta puede implementarse mediante una lista enlazada o mediante una matriz.

Para evitar que los clientes dependan de la implementación, un ADT a menudo se empaqueta como un tipo de datos opaco en uno o más módulos, cuya interfaz contiene solo la firma (número y tipos de los parámetros y resultados) de las operaciones. La implementación del módulo, es decir, los cuerpos de los procedimientos y la estructura de datos concreta utilizada, se puede ocultar a la mayoría de los clientes del módulo. Esto hace posible cambiar la implementación sin afectar a los clientes. Si la implementación está expuesta, se conoce como tipo de datos transparente.

Al implementar un ADT, cada instancia (en las definiciones de estilo imperativo) o cada estado (en las definiciones de estilo funcional) generalmente se representa mediante algún tipo de identificador.

Los lenguajes modernos orientados a objetos, como C++ y Java, admiten una forma de tipos de datos abstractos. Cuando una clase se usa como tipo, es un tipo abstracto que se refiere a una representación oculta. En este modelo, un ADT normalmente se implementa como una clase y cada instancia del ADT suele ser un objeto de esa clase. La interfaz del módulo generalmente declara los constructores como procedimientos ordinarios y la mayoría de las otras operaciones ADT como métodos de esa clase. Sin embargo, tal enfoque no encapsula fácilmente las múltiples variantes de representación que se encuentran en un ADT. También puede socavar la extensibilidad de los programas orientados a objetos. En un programa puro orientado a objetos que usa interfaces como tipos, los tipos se refieren a comportamientos, no a representaciones.

Ejemplo: implementación de la pila abstracta

Como ejemplo, aquí hay una implementación de la pila abstracta anterior en el lenguaje de programación C.

Interfaz de estilo imperativo

Una interfaz de estilo imperativo podría ser:

Tipodef struct stack_Rep stack_Rep; // tipo: representación de instancia de pila (grabación opaca)Tipodef stack_Rep* stack_T; // tipo: mango a una instancia de pila (puntero opaco)Tipodef vacío* stack_Item; // tipo: valor almacenado en la instancia de la pila (dirección arbitraria)stack_T stack_create()vacío); // crea una nueva instancia de pila vacíavacío stack_push()stack_T s, stack_Item x); // añade un elemento en la parte superior de la pilastack_Item stack_pop()stack_T s); // elimina el elemento superior de la pila y lo devuelvebool stack_empty()stack_T s); // comprobar si la pila está vacía

Esta interfaz podría usarse de la siguiente manera:

#include - No. // incluye la interfaz de pilastack_T s = stack_create(); // crea una nueva instancia de pila vacíaint x = 17;stack_push()s, "x); // añade la dirección de x en la parte superior de la pilavacío* Sí. = stack_pop()s); // elimina la dirección de x de la pila y la devuelvesi ()stack_empty()s) {} } // hace algo si la pila está vacía

Esta interfaz se puede implementar de muchas maneras. La implementación puede ser arbitrariamente ineficiente, ya que la definición formal de ADT, arriba, no especifica cuánto espacio puede usar la pila, ni cuánto tiempo debe tomar cada operación. Tampoco especifica si el estado de la pila s continúa existiendo después de una llamada x ← pop(s).

En la práctica, la definición formal debe especificar que el espacio es proporcional al número de elementos empujados y aún no reventados; y que cada una de las operaciones anteriores debe terminar en un tiempo constante, independientemente de ese número. Para cumplir con estas especificaciones adicionales, la implementación podría usar una lista enlazada o una matriz (con cambio de tamaño dinámico) junto con dos números enteros (un recuento de elementos y el tamaño de la matriz).

Interfaz de estilo funcional

Las definiciones ADT de estilo funcional son más apropiadas para los lenguajes de programación funcionales y viceversa. Sin embargo, se puede proporcionar una interfaz de estilo funcional incluso en un lenguaje imperativo como C. Por ejemplo:

Tipodef struct stack_Rep stack_Rep; // tipo: representación del estado de pila (grabación opaca)Tipodef stack_Rep* stack_T; // tipo: mango a un estado de pila (puntero opaco)Tipodef vacío* stack_Item; // tipo: valor de un estado de pila (dirección arbitraria)stack_T stack_empty()vacío); // devuelve el estado de la pila vacíastack_T stack_push()stack_T s, stack_Item x); // añade un elemento en la parte superior del estado de la pila y devuelve el estado de la pila resultantestack_T stack_pop()stack_T s); // elimina el elemento superior del estado de la pila y devuelve el estado de la pila resultantestack_Item stack_top()stack_T s); // devuelve el elemento superior del estado de la pila

Bibliotecas ADT

Muchos lenguajes de programación modernos, como C++ y Java, vienen con bibliotecas estándar que implementan varios ADT comunes, como los enumerados anteriormente.

Tipos de datos abstractos integrados

La especificación de algunos lenguajes de programación es intencionalmente vaga sobre la representación de ciertos tipos de datos incorporados, definiendo solo las operaciones que se pueden realizar en ellos. Por lo tanto, esos tipos se pueden ver como "ADT integrados". Los ejemplos son las matrices en muchos lenguajes de secuencias de comandos, como Awk, Lua y Perl, que pueden considerarse como una implementación de la lista abstracta.