Estructura de datos

1 Introducción a los tipos abstractos de datos
Con la aparición de los lenguajes de programación estructurados en la década de los 60, surge el concepto de tipo de datos (ing., data fype), definido como un conjunto de valores que sirve de dominio de ciertas operaciones. En estos lenguajes (C, Pascal y similares, derivados todos ellos del Algol), los tipos de datos sirven sobre todo paraclasificar los objetos de los programas (variables, parámetros y constantes) y determinar qué valores pueden tomar y qué operaciones se les pueden aplicar. Esta noción, no obstante, se reveló insuficiente en el desarrollo de software a gran escala, dado que el uso de los datos dentro de los programas no conocía más restricciones que las impuestas por el compilador, lo cual era muy inconveniente en losnuevos tipos de datos definidos por el usuario, sobre todo porque no se restringía de ninguna manera su ámbito de manipulación. Para solucionar esta carencia, resumida por J.B. Morris en "Types are not Sets" (Proceedings ACM

POPL, 1973), diversos investigadores (citemos como pioneros a S.N. Zules, a J.V.
Guttag y al grupo ADJ, formado por J.A. Goguen, J.W. Thatcher, E.G. Wagner y J.B. Wright[ADJ78]) introdujeron a mediados de la década de los 70 el concepto de tipo abstracto de datos (ing., abstract data type; abreviadamente,

TAD}, que considera un tipo de datos no sólo como el conjunto de valores que
lo caracteriza sino también como las operaciones que sobre él se pueden aplicar, las cuales cumplirán diversas propiedades que determinarán

inequívocamente su comportamiento. Todosestos autores coincidieron en la necesidad de emplear una notación formal para describir el comportamiento de las operaciones, no sólo para impedir cualquier interpretación ambigua sino para identificar claramente el modelo matemático denotado por el TAD. En realidad, el concepto de TAD ya existe en los lenguajes de programación estructurados bajo la forma de los tipos predefinidos, que se puedenconsiderar

como tipos abstractos con poco esfuerzo adicional. Por ejemplo, consideremos el tipo de datos de los enteros que ofrece el lenguaje Pascal; la definición del TAD correspondiente consiste en determinar: • cuáles son sus valores: los números enteros dentro del intervalo [minint, maxint]; • cuáles son sus operaciones: la suma, la resta, el producto, el cociente y el resto de ladivisión, y • cuáles son las propiedades que cumplen estas operaciones: hay muchas; por ejemplo:

a+b = b+a, a*O = O, etc.
Resumiendo, se puede definir un tipo abstracto de datos como un conjunto de valores sobre los que se aplica un conjunto dado de operaciones que cumplen determinadas propiedades. ¿Por qué "abstracto"? El calificativo "abstracto" no significa "surrealista" sino que proviene de"abstracción", y responde al hecho de que los valores de un tipo pueden ser manipulados mediante sus operaciones, si se saben las propiedades que éstas cumplen, sin que sea necesario ningún conocimiento ulterior sobre el tipo; en concreto, su implementación en la máquina es absolutamente irrelevante. En el caso de los enteros de Pascal, cualquier programa escrito en este lenguaje puede efectuar laoperación x+y (siendo x e y dos variables enteras) con la certeza de que siempre calculará la suma de los enteros x e y, independientemente de su representación interna en la máquina que está ejecutando el programa (complemento a 2, signo y magnitud, etc.) porque, sea ésta cual sea, la definición de los enteros de Pascal asegura que la suma se comporta de una manera determinada. En otras palabras, lamanipulación de los objetos de un tipo sólo depende del comportamiento descrito en su

especificación y es independiente de su implementación:

La especificación de un TAD consiste en establecer las propiedades que lo definen. Para que sea útil, una especificación ha de ser precisa (sólo tiene que decir aquello realmente imprescindible), general (adaptable a diferentes contextos), legible...