Tipos de Datos Abstractos

ESTRUCTURAS DE DATOS

TIPOS ABSTRACTOS DE DATOS 51

TEMA 2

Tipos Abstractos de Datos.
2.1. CONCEPTO
Como se vio en el apartado 1.4, se entiende por Estructura de Datos una agrupación
de datos, simples o compuestos, del mismo o diferente tipo, que constituyen una entidad en
su conjunto (por ejemplo un vector o un registro).
Evolucionando en el concepto de estructura de datos aparece elde Tipo Abstracto de
Datos (TAD) que obedece a la técnica de abstracción de datos y sienta las bases para una
adecuada compresión de la Programación Orientada a Objetos.
Una definición de TAD u Objeto sería: El conjunto constituido por la estructura de
datos y las operaciones asociadas a la misma que permite modelar el comportamiento de
una entidad real.
Se trata de construir entidades(TAD’s, Objetos, etc.) que puedan ser posteriormente
utilizadas por otros.
Sus principales características son:
•

Ocultamiento. El TAD tiene un comportamiento de “caja negra” dado que quien lo
usa sabe qué puede hacer pero no cómo lo hace.

52 TIPOS ABSTRACTOS DE DATOS

ESTRUCTURAS DE DATOS

•

Encapsulamiento (y, en consecuencia, Protección). El usuario de TAD’s no tiene
acceso y, portanto, no puede modificar sus características. No obstante, puede partir de
él para construir otros TAD’s1

•

Compilación separada: El resultado de la compilación del TAD se pone a disposición
de los usuarios en forma de unidades que pueden utilizarse como si estuvieran
predefinidas en el lenguaje de programación.

El objetivo de emplear este tipo de mecanismos obedece a criterios deproductividad
en la Ingeniería del Software. De forma simplificada se trata de clasificar a los
profesionales de la construcción de Software en dos categorías:
•

Constructores (y distribuidores) de TAD’s.

•

Utilizadores de TAD’s hechos por otros.

El usuario de un TAD sabe de su comportamiento a partir de las especificaciones
tanto semánticas como sintácticas que le habrán sidoproporcionadas por el creador del
mismo.
En los siguientes apartados veremos, a partir de unos sencillos ejemplos, la forma de
usar TAD’s a partir de su interfaz (no necesitamos saber como están construidos
internamente, se verá en temas posteriores). Se trata de dos Tipos Abstractos de Datos:
Pilas y Colas que constituyen fenómenos observables con mucha frecuencia en el mundo
real.
Los TAD’sproporcionados se han construido con pretensiones exclusivamente
didácticas para ser utilizados en el contexto de la asignatura2 de tal forma que puedan
utilizarse de manera similar a como se haría en cualquier otro lenguaje de programación.

1

Esta idea permite introducir el segundo concepto más representativo de la Programación Orientada a
Objetos: la HERENCIA
2
El lenguaje Java incluye ensu librería util (http://java.sun.com/j2se/1.5.0/docs/api/java/util/packagesummary.html) tanto la estructura de datos Pila (http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html),
así como la Cola (http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html)

ESTRUCTURAS DE DATOS

TIPOS ABSTRACTOS DE DATOS 53

2.2. TAD PILA DE NÚMEROS ENTEROS.
2.2.1. Concepto.
Una pila es unaagrupación de elementos de determinada naturaleza o tipo (datos de
personas, números, procesos informáticos, automóviles, etc.) entre los que existe definida
una relación de orden (estructura de datos). En función del tiempo, algunos elementos de
dicha naturaleza pueden llegar a la pila o salir de ella (operaciones/acciones). En
consecuencia el estado de la pila varía.
Una pila presenta elcomportamiento LIFO (Last Input First Output) y el criterio de
ordenación se establece en sentido inverso al orden de llegada. Así pues, el último elemento
que llegó al conjunto será el primero en salir del mismo, y así sucesivamente.
2.2.2. Modelo gráfico
Podríamos representar gráficamente una pila según aparece en la figura 2.1: una
estructura de datos vertical, en la que los elementos se...