tipos de datos abstractos

520003888105688657500770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000770005238115914400000Tipos de datos abstractos
Un Tipo de dato abstracto (en adelante TDA) es un conjunto de datos u objetos al cual se le asocian operaciones. El TDA provee de una interfaz con la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera en como estén implementadas dichas operaciones. Esto quiere decir que un mismoTDA puede ser implementado utilizando distintas estructuras de datos y proveer la misma funcionalidad.
El paradigma de orientación a objetos permite el encapsulamiento de los datos y las operaciones mediante la definición de clases e interfaces, lo cual permite ocultar la manera en cómo ha sido implementado el TDA y solo permite el acceso a los datos a través de las operaciones provistas por lainterfaz.
En este capítulo se estudiarán TDA básicos como lo son las listas, pilas y colas, y se mostrarán algunos usos prácticos de estos TDA.
Una lista se define como una serie de N elementos E1, E2, ..., EN, ordenados de manera consecutiva, es decir, el elemento Ek (que se denomina elemento k-ésimo) es previo al elementoEk+1. Si la lista contiene 0 elementos se denomina como lista vacía.
Lasoperaciones que se pueden realizar en la lista son: insertar un elemento en la posición k, borrar el k-ésimo elemento, buscar un elemento dentro de la lista y preguntar si la lista esta vacía.
Una manera simple de implementar una lista es utilizando un arreglo. Sin embargo, las operaciones de inserción y borrado de elementos en arreglos son ineficientes, puesto que para insertar un elemento enla parte media del arreglo es necesario mover todos los elementos que se encuentren delante de él, para hacer espacio, y al borrar un elemento es necesario mover todos los elementos para ocupar el espacio desocupado. Una implementación más eficiente del TDA se logra utilizando listas enlazadas.
A continuación se presenta una implementación en Java del TDA utilizando listas enlazadas y susoperaciones asociadas:
estaVacia(): devuelve verdadero si la lista esta vacía, falso en caso contrario.
insertar(x, k): inserta el elemento x en la k-ésima posición de la lista.
buscar(x): devuelve la posición en la lista del elemento x.
buscarK(k): devuelve el k-ésimo elemento de la lista.
eliminar(x): elimina de la lista el elemento x.
En la implementación con listas enlazadas es necesario teneren cuenta algunos detalles importantes: si solamente se dispone de la referencia al primer elemento, el añadir o remover en la primera posición es un caso especial, puesto que la referencia a la lista enlazada debe modificarse según la operación realizada. Además, para eliminar un elemento en particular es necesario conocer el elemento que lo antecede, y en este caso, ¿qué pasa con el primerelemento, que no tiene un predecesor?
Para solucionar estos inconvenientes se utiliza la implementación de lista enlazada con nodo cabecera. Con esto, todos los elementos de la lista tendrán un elemento previo, puesto que el previo del primer elemento es la cabecera. Una lista vacía corresponde, en este caso, a una cabecera cuya referencia siguiente es null.

Losarchivos NodoLista.java, IteradorLista.java y Lista.java contienen una implementación completa del TDA lista. La clase NodoLista implementa los nodos de la lista enlazada, la claseLista implementa las operaciones de la lista propiamente tal, y la clase IteradorLista implementa objetos que permiten recorrer la lista y posee la siguiente interfaz:
avanzar(): avanza el iterador al siguiente nodo de la lista.
obtener(): retorna el...