PDF de programación - Tema 2 - Tipos Abstractos de Datos

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 el de 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, por tanto, 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 de productividad
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 sido proporcionadas 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’s proporcionados 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 en su librería util (http://java.sun.com/j2se/1.5.0/docs/api/java/util/package-
summary.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 una agrupació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 el comportamiento 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 insertan y extraen por la parte
superior.



desapilar



apilar



5 cima
4
1
7
2



fondo



Figura 2.1. Modelo gráfico de Pila

2.2.3. Especificaciones

A continuación se describen las operaciones que vamos a poder realizar sobre el TAD

pila de enteros. Para ello, utilizaremos dos tipos de especificaciones:

o Especificaciones sintácticas. Hacen referencia a los aspectos sintácticos de las
distintas operaciones asociadas al TAD: nombre de la operación, parámetros,
resultado devuelto por la operación, tipo de dicho resultado, etc.

o Especificaciones semánticas. Indican el efecto producido por la operación, es

decir, la definen desde el punto de vista de lo que hace.

En la Tabla 2.1., se definen las especificaciones semánticas y sintácticas del TAD pila
de enteros, que se ha cronstruido dentro del paquete (package) tadPila. Cuando se desee
utilizar el tad pila en un programa, habrá que poner la siguiente sentencia en la primera
línea del programa, después de la cabecera (o bien utilizarlo dentro del mismo paquete –
package–):

import tadPila.*;

54 TIPOS ABSTRACTOS DE DATOS

ESTRUCTURAS DE DATOS



Operación

Especificación semántica

Especificación sintáctica

inicializarPila

apilar 3

desapilar 4

pilaVacia

leerPila

imprimirPila

numElemPila

cima

decapitar

eliminarPila 5

Método que deja a disposición del programa
un TAD pila sobre el que se podrá operar
posteriormente.
(Equivalente a crear o
construir un objeto/instancia.).
Método que entrega un elemento (x) para
que quede incorporado en la cima de la
pila.
Método que elimina el elemento que ocupa
la cima de
la pila y devuelve como
resultado dicho elemento.
Método que al ejecutarse devuelve true si la
pila está vacía (no tiene elementos), y false
en caso contrario.
Método que se utiliza para realizar la carga
inicial de elementos de la pila.
Método que muestra en la pantalla el
contenido de la pila.
Método que devuelve el número de
elementos de la pila.
Método que devuelve la cima de la pila (sin
alterarla).
Método que elimina el elemento de la cima
de la pila.
Método que recibe una pila (que puede
tener elementos o no) y la devuelve vacía.

void inicializarPila ()

void apilar (int x)

int desapilar ()

boolean pilaVacia ()

void leerPila () throws NumberFormatException,
IOException
void imprimirPila ()

int numElemPila ()

int cima ()

void decapitar ()

void eliminarPila ()

Tabla 2.1. Especificaciones semánticas y sintácticas del TAD Pila de enteros.

2.2.4. Interfaz del TAD Pila.

El interfaz Pila define los métodos de objeto que utilizaremos con la clase TadPila:

package tadPila;
import java.io.*;



public interface Pila {
void inicializarPila ();
boolean pilaVacia ();
void eliminarPila ();
int cima ();
void apilar (int x);
int desapilar ();
void decapitar ();
void imprimirPila ();
void leerPila () throws NumberFormatException, IOException;
int numElemPila ();
}



3 Se puede producir una situación de excepción cuando el número de elementos de la pila supere determinado
valor (lógicamente no podrán ser infinitos). Dicha situación se manifestará al intentar ejecutar la operación de
apilar sobre una pila en dicho estado.
4 Se produce un mensaje de error si se intenta desapilar de una pila vacía. Lo mismo ocurre con las
operaciones cima y decapitar.
5 Puede resultar innecesario y forzado en Java, pero queremos transmitir la idea de la obligación de crear y
destruir los objetos cuando se trabaje en Programación Orientada a Objetos.

ESTRUCTURAS DE DATOS

TIPOS ABSTRACTOS DE DATOS 55

2.2.5. Prueba del TAD pila.

2.2.5.1. Condiciones normales.

En el siguiente algoritmo se va a realizar una verificación del funcionamiento
elemental (sin situaciones de excepción) del TAD Pila. Primero se inicializa la pila, a
continuación se introducen varios elementos en la misma, y por último se sacan dos de los
datos, escribiendo los elementos desapilados en la pantalla.



package tadPila;
import java.io.*;



public class PruebaPila1 {
public static void main (String[] args) {
Pila p = new TadPila ();
int x;



p.inicializarPila ();
p.apilar (1);
p.apilar (2);
p.apilar (3);
p.apilar (11);
p.apilar (15);
x = p.desapilar ();
System.out.println ("x = " + x);
x = p.desapilar ();
System.out.println ("x = " + x);
p.eliminarPila ();
}
}

2.2.5.2. Situaciones de excepción.

A continuación se muestra un ejemplo mediante el cual podemos verificar el
funcionamiento del TAD frente a situaciones de excepción: introducimos una serie de
elementos en la pila, y luego intentamos desapilar uno más de los que tenía la pila
originalmente.

package tadPila;
public class PruebaPila2 {



public static void main(String[] args) {
Pila pila1 = new TadPila ();
int i, j;



System.out.println();
pila1.inicializarPila ();
for (i= 1; i< 10; i++)
pila1.apilar (i);
j = pila1.desapilar ();
for (i= 1; i< 10; i++)
j = pila1.desapilar ();
pila1.eliminarPila ();
}
}

56 TIPOS ABSTRACTOS DE DATOS

ESTRUCTURAS DE DATOS

2.2.6. Algoritmos básicos con pilas.

En los siguientes apartados se desarrollan algunos ejemplos elementales que hacen
uso del TAD pila siguiendo las especificacio