De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
No confundir con el tipo de datos algebraicos .

En informática , un tipo de datos abstracto ( ADT ) es un modelo matemático para tipos de datos . Un tipo de datos 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"; [1] esto es análogo a una estructura algebraica en matemáticas. Lo que se entiende por "comportamiento" varía según el autor, siendo los dos tipos principales de especificaciones formales para el comportamiento la especificación axiomática (algebraica) y un modelo abstracto; [2] estos corresponden a la semántica axiomática y la semántica operativa de una máquina abstracta , 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 deben a la representación. Por ejemplo, los 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 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 principales 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 . [3]

Ejemplos [ editar ]

Por ejemplo, los enteros son un ADT, definido como los valores ..., −2, −1, 0, 1, 2, ..., y por las operaciones de suma, resta, multiplicación y división, junto con mayor que , menor que, etc., que se comportan de acuerdo con las matemáticas familiares (con cuidado de la división de enteros ), independientemente de cómo los números enteros sean representados por la computadora. [a] Explícitamente, "comportamiento" incluye obedecer varios axiomas (asociatividad y conmutatividad de la adición, etc.) y condiciones previas sobre las operaciones (no se puede dividir por cero). Normalmente, los enteros se representan en una estructura de datos como números binarios , la mayoría de las veces como complemento a dos , pero pueden ser decimales codificados en binario o enel complemento de unos , pero el usuario se abstrae de la elección concreta de representación, y puede simplemente utilizar los datos como tipos de datos.

Un ADT consta no solo de operaciones, sino también de valores de los datos subyacentes y de las limitaciones de las operaciones. Una "interfaz" se refiere típicamente sólo a las operaciones, y quizás a algunas de las limitaciones de las operaciones, en particular condiciones previas y posteriores, pero no otras limitaciones, 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:, pushque inserta un elemento de datos en la pila; pop, que elimina un elemento de datos de él; y peeko top, que accede a un elemento de datos en la parte superior de la pila sin quitarlo. Una cola abstracta , que es una estructura de primero en entrar enqueue, primero en salir, también tendría tres operaciones:, que inserta un elemento de datos en la cola; dequeue, que elimina el primer elemento de datos; yfront, que accede y sirve el primer elemento de datos de la cola. No habría forma de diferenciar estos dos tipos de datos, a menos que se introduzca una restricción matemática que para una pila especifique que cada elemento emergente siempre devuelve el elemento insertado más recientemente que aún no se ha publicado. Al analizar la eficiencia de los algoritmos que usan pilas, también se puede especificar que todas las operaciones toman el mismo tiempo sin importar cuántos elementos de datos se hayan introducido en la pila, y que la pila usa una cantidad constante de almacenamiento para cada elemento.

Introducción [ editar ]

Los tipos de datos abstractos son entidades puramente teóricas, utilizadas (entre otras cosas) para simplificar la descripción de algoritmos abstractos, clasificar y evaluar estructuras de datos y describir formalmente los sistemas de tipos de lenguajes de programación. Sin embargo, un ADT puede implementarse mediante tipos de datos o estructuras de datos específicos , de muchas formas 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 información escondidaLa estrategia 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 una serie de estructuras algebraicas , como retículas, grupos y anillos. [4] 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 . [5]

Definición de un tipo de datos abstracto [ editar ]

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. Puede trazarse una amplia división entre estilos de definición "imperativos" y "funcionales".

Definición de estilo imperativo [ editar ]

En la filosofí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 el que se evalúan las operaciones es importante, y la misma operación en las mismas entidades puede tener diferentes efectos si se ejecuta en diferentes momentos, al igual que las instrucciones de una computadora o los comandos y procedimientos de un lenguaje imperativo. Para subrayar este punto de vista, se acostumbra decir que las operaciones se ejecutan o aplican , en lugar de evaluarse. El estilo imperativo se usa a menudo al describir algoritmos abstractos. (Consulte El arte de la programación informática de Donald Knuth para obtener más detalles)

Variable abstracta [ editar ]

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

  • store( V , x ) donde x es un valor de naturaleza no especificada;
  • fetch( V ), que arroja un valor,

con la restricción de que

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

Como en tantos 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á implícita siempre 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 , fetch( V ) + 1).

En esta definición, se supone implícitamente que el almacenamiento de un valor en una variable T no tiene ningún efecto sobre el estado de una variable distinta V . Para hacer explícito este supuesto, se podría agregar la restricción de que

  • si U y V son variables distintas, la secuencia { store( U , x ); store( V , y )} es equivalente a { store( V , y ); store( 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 ningún efecto sobre el estado de cualquier otra instancia (incluidas otras instancias del mismo ADT), a menos que los axiomas de ADT impliquen que las dos instancias están conectadas ( alias ) en ese sentido. Por ejemplo, cuando se extiende la definición de la variable abstracta para incluir abstractos registros , la operación que selecciona un campo de una variable de registro R deben ceder una variable V que se alias a la parte de R .

La definición de una variable abstracta V también puede restringir los valores almacenados x a los miembros de un conjunto específico X , llamado el rango o tipo de V . Al igual que en los lenguajes de programación, estas restricciones pueden simplificar la descripción y el análisis de algoritmos y mejorar su legibilidad.

Tenga en cuenta que esta definición no implica nada sobre el resultado de la evaluación fetch( V ) cuando V es no inicializado , es decir, antes de realizar cualquier storeoperación en V . Un algoritmo que lo hace generalmente se considera inválido porque su efecto no está definido. (Sin embargo, hay algunos algoritmos importantes cuya eficiencia depende en gran medida de la suposición de que tal fetches legal y devuelve algún valor arbitrario en el rango de la variable. [ Cita requerida ] )

Creación de instancia [ editar ]

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

  • el resultado de create() es distinto de cualquier instancia utilizada por el algoritmo.

Este axioma puede reforzarse para excluir también el alias parcial con otros casos. Por otro lado, este axioma todavía permite que las implementaciones de create() produzcan una instancia creada previamente que se ha vuelto inaccesible para el programa.

Ejemplo: pila abstracta (imperativo) [ editar ]

Como otro ejemplo, una definición de estilo imperativo de una pila abstracta podría especificar que el estado de una pila S sólo puede ser modificado por las operaciones

  • push( S , x ), donde x es algún valor de naturaleza no especificada;
  • pop( S ), que arroja un valor como resultado,

con la restricción de que

  • Para cualquier valor x y cualquier variable abstracta V , la secuencia de operaciones { push( 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 ← 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 secuencia

{ push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S )}

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

{ U ← y ; V ← z ; W ← x }

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

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

Una definición de pila abstracta generalmente incluye también una función de valor booleanoempty ( S ) y una createoperación () que devuelve una instancia de pila, con axiomas equivalentes a

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

Estilo de instancia única [ editar ]

A veces, un ADT se define como si solo existiera una instancia de él durante la ejecución del algoritmo, y todas las operaciones se aplicaron a esa instancia, que no se anota explícitamente. Por ejemplo, la pila abstracta anterior podría haberse definido con las operaciones push( x ) y pop(), que operan en la única 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 múltiples 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 verifica si las pilas S y T contienen los mismos elementos en el mismo orden.

Definición de estilo funcional [ editar ]

Otra forma de definir un ADT, más cercano 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 nuevo estado como parte del resultado. A diferencia de las operaciones imperativas, estas funciones no tienen efectos secundarios . Por lo tanto, el orden en el 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 forma (o necesidad) de definir una "variable abstracta" con la semántica de las variables imperativas (es decir, con fetchy storeoperaciones). En lugar de almacenar valores en variables, uno los pasa como argumentos a funciones.

Ejemplo: pila abstracta (funcional) [ editar ]

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

  • push: toma un estado de pila y un valor arbitrario, devuelve un estado de pila;
  • top: 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 createoperación. De hecho, no existe la noción de "instancia de pila". Los estados de la pila se pueden considerar como estados potenciales de una estructura de pila única, y dos estados de la pila 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 listas enlazadas con contras de hash .

En lugar de create(), una definición de estilo funcional de una pila abstracta puede asumir la existencia de un estado de pila especial, la pila vacía , designada por un símbolo especial como Λ o "()"; o defina una bottomoperación () que no tome argumentos y devuelva este estado de pila especial. Tenga en cuenta que los axiomas implican que

  • push(Λ, x ) ≠ Λ.

En una definición de estilo funcional de una pila, no se necesita un emptypredicado: en su lugar, se puede probar 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 a push. Dado que pushdeja 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 ausencia de efectos secundarios) implican que push( s , x ) = push( t , y ) si y solo si x = y y s = t .

Como en algunas otras ramas de las matemáticas, se acostumbra asumir también que los estados de la pila son solo aquellos cuya existencia puede demostrarse 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 popeditar para siempre, cada vez produciendo 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 u push( s ,x ) = s para alguna x . Sin embargo, dado que no se pueden obtener tales estados de pila con las operaciones dadas, se supone que "no existen".

Ya sea para incluir complejidad [ editar ]

Aparte 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 fue 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 reemplazo un módulo con otro módulo con el mismo comportamiento funcional pero con diferentes compensaciones de complejidad, el usuario de este código se sorprenderá desagradablemente. Podría decirle todo lo que quisiera sobre la abstracción de datos, y él todavía no querría usar el código. Las afirmaciones de complejidad deben formar parte de la interfaz.

-  Alexander Stepanov [6]

Ventajas de la mecanografía de datos abstractos [ editar ]

Encapsulación [ editar ]

Abstraction ofrece la promesa de 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.

Localización del cambio [ editar ]

No será necesario editar el código que utiliza un objeto ADT si se cambia la implementación de ADT. Dado que cualquier cambio en la implementació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 requerir ningún cambio en el código donde se usa el ADT .

Flexibilidad [ editar ]

Diferentes implementaciones del ADT, que tienen todas las mismas propiedades y habilidades, son equivalentes y pueden usarse indistintamente 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 sea preferible, aumentando así la eficiencia general.

Operaciones típicas [ editar ]

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

  • compare( s , t ), que prueba si los estados de dos instancias son equivalentes en algún sentido;
  • hash( s ), que calcula alguna función hash estándar del estado de la instancia;
  • print( s ) o show( s ), que produce una representación legible por humanos del estado de la instancia.

En las definiciones de TDA de estilo imperativo, a menudo se encuentra también

  • create(), que produce una nueva instancia de ADT;
  • initialize( s ), que prepara una instancia s recién creada para operaciones posteriores, o la restablece a algún "estado inicial";
  • copy( s , t ), que pone a la instancia s en un estado equivalente al de t ;
  • clone( t ), que realiza s ← create(), copy( s , t ) y devuelve s ;
  • free( s ) o destroy( s ), que recupera la memoria y otros recursos utilizados por s .

La freeoperación normalmente no es relevante o significativa, ya que los ADT son entidades teóricas que no "usan 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 utiliza cada instancia de ADT, en función de su estado, y cuánta de ella se devuelve al grupo free.

Ejemplos [ editar ]

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

  • Envase
  • Lista
  • Colocar
  • Multiset
  • Mapa
  • Multimapa
  • Grafico
  • Árbol
  • Apilar
  • Cola
  • Cola de prioridad
  • Cola de dos extremos
  • Cola de prioridad de dos extremos

Cada uno de estos ADT puede definirse de muchas formas y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede tener o no una countoperación que indique cuántos elementos se han empujado y aún no se han desplegado. 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: [7] 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 instalaciones para construir objetos gráficos de manera estructurada.

Implementación [ editar ]

Más información: tipo de datos opaco

Implementar un ADT significa proporcionar un procedimiento o función para cada operación abstracta. Las instancias de ADT están representadas por una 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 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 un tipo de datos transparente.

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

Los lenguajes modernos orientados a objetos, como C ++ y Java , admiten una forma de tipos de datos abstractos. Cuando se usa una clase como tipo, es un tipo abstracto que se refiere a una representación oculta. En este modelo, un ADT generalmente se implementa como una clase , y cada instancia del ADT suele ser un objeto de esa clase. La interfaz del módulo normalmente declara los constructores como procedimientos ordinarios y la mayoría de las otras operaciones de ADT como métodos.de esa clase. Sin embargo, tal enfoque no encapsula fácilmente múltiples variantes representativas encontradas 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 [ editar ]

A modo de ejemplo, aquí es una implementación de la pila abstracta anteriormente en el lenguaje de programación C .

Interfaz de estilo imperativo [ editar ]

Una interfaz de estilo imperativo podría ser:

typedef  struct  stack_Rep  stack_Rep ;  // tipo: representación de instancia de pila (registro opaco) typedef  stack_Rep *  stack_T ;  // tipo: maneja a una instancia de pila (puntero opaco) typedef  void *  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ía void  stack_push ( stack_T  s ,  stack_Item  x );  // agrega un elemento en la parte superior de la pila stack_Item  stack_pop ( stack_T  s );  // elimina el elemento superior de la pila y lo devuelve bool  stack_empty ( stack_T  s );  // comprueba si la pila está vacía

Esta interfaz se puede utilizar de la siguiente manera:

#include  <stack.h>  // incluye la interfaz de la pilastack_T  s  =  stack_create ();  // crea una nueva instancia de pila vacía int  x  =  17 ; stack_push ( s ,  & x );  // agrega la dirección de x en la parte superior de la pila void *  y  =  stack_pop ( s );  // elimina la dirección de x de la pila y la devuelve if  ( stack_empty ( s ))  {  }  // hace algo si la pila está vacía

Esta interfaz se puede implementar de muchas formas. La implementación puede ser arbitrariamente ineficiente, ya que la definición formal del 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 debería especificar que el espacio es proporcional al número de elementos empujados y aún no revelados; y que cada una de las operaciones anteriores debe finalizar en un período de tiempo constante, independientemente de ese número. Para cumplir con estas especificaciones adicionales, la implementación podría utilizar una lista vinculada 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 [ editar ]

Las definiciones de ADT de estilo funcional son más apropiadas para 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:

typedef  struct  stack_Rep  stack_Rep ;  // tipo: representación del estado de la pila (registro opaco) typedef  stack_Rep *  stack_T ;  // tipo: maneja a un estado de pila (puntero opaco) typedef  void *  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ía stack_T  stack_push ( stack_T  s ,  stack_Item  x );  // agrega un elemento en la parte superior del estado de la pila y devuelve el estado de la pila resultante stack_T  stack_pop ( stack_T  s );  // elimina el elemento superior del estado de la pila y devuelve el estado de la pila resultante stack_Item  stack_top ( stack_T  s );  // devuelve el elemento superior del estado de la pila

Bibliotecas ADT [ editar ]

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 [ editar ]

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

Ver también [ editar ]

  • Concepto (programación genérica)
  • Métodos formales
  • Especificacion funcional
  • Tipo de datos algebraicos generalizados
  • Álgebra inicial
  • Principio de sustitución de Liskov
  • Teoría de tipos
  • Paredes y espejos

Notas [ editar ]

  1. ^ Compare con la caracterización de números enteros en álgebra abstracta.

Citas [ editar ]

  1. ^ Dale y Walker 1996 , p. 3.
  2. ^ Dale y Walker 1996 , p. 4.
  3. ^ Liskov y Zilles 1974 .
  4. ^ Rudolf Lidl (2004). Álgebra abstracta . Saltador. ISBN 978-81-8128-149-4., Capítulo 7, sección 40.
  5. ^ "¿Qué es la programación orientada a objetos?" . Contratación | Upwork . 2015-05-05 . Consultado el 28 de octubre de 2016 .
  6. ^ Stevens, Al (marzo de 1995). "Entrevistas de Al Stevens Alex Stepanov" . Diario del Dr. Dobb . Consultado el 31 de enero de 2015 .
  7. ^ D. Thalmann, N. Magnenat Thalmann (1979). Diseño e implementación de tipos de datos gráficos abstractos . IEEE. doi : 10.1109 / CMPSAC.1979.762551 ., Proc. Tercera Conferencia Internacional de Software y Aplicaciones de Computación (COMPSAC'79), IEEE, Chicago, EE. UU., Págs. 519-524
  8. ^ Robert Sedgewick (1998). Algoritmos en C . Addison / Wesley. ISBN 978-0-201-31452-6., definición 4.4.

Referencias [ editar ]

  • Liskov, Barbara ; Zilles, Stephen (1974). "Programación con tipos de datos abstractos". Actas del Simposio ACM SIGPLAN sobre idiomas de muy alto nivel . Avisos SIGPLAN. 9 . págs. 50–59. CiteSeerX  10.1.1.136.3043 . doi : 10.1145 / 800233.807045 .
  • Dale, Nell; Walker, Henry M. (1996). Tipos de datos abstractos: especificaciones, implementaciones y aplicaciones . Jones y Bartlett Learning. ISBN 978-0-66940000-7.

Lectura adicional [ editar ]

  • Mitchell, John C .; Plotkin, Gordon (julio de 1988). "Los tipos abstractos tienen tipo existencial" (PDF) . Transacciones ACM sobre lenguajes y sistemas de programación . 10 (3): 470–502. doi : 10.1145 / 44501.45065 . S2CID  1222153 .

Enlaces externos [ editar ]

  • Medios relacionados con tipos de datos abstractos en Wikimedia Commons
  • Tipo de datos abstractos en el Diccionario NIST de Algoritmos y Estructuras de Datos