Datos Abstractos

Que es tipo de datos abstractos (TAD)
Un Tipo Abstracto de Datos es un conjunto de valores y de operaciones definidos mediante una especificación independiente de cualquier representación.
TAD = valores + operaciones. Se puede agregar que, un tipo de dato Abstracto no sólo es el conjunto de valores que lo caracteriza; sino también como las operaciones que sobre él se pueden aplicar, conjuntamente con las diversas propiedades que determinan inequívocamente su comportamiento.
Para que se usan los TAD.
Los TADs se usan para definir un nuevo tipo, a partir del cuál se pueden crear instancias. Los TDAs permiten la creación de instancias con propiedades bien definidas y comportamiento bien definido. En orientación a objetos, nos referimos a los TDAs como clases. Por lo tanto, una clase define las propiedades de objetos instancia en un ambiente orientado a objetos.
Por ejemplo, uno puede pensar en listas de manzanas, carros o aún listas. La definición semántica de una lista siempre es la misma. Solamente el tipo de los elementos de datos cambia de acuerdo al tipo sobre el cuál debía operar la lista.
Aplicaciones en los TAD
Los TAD básicos o aplicaciones básicas son: las listas, pilas y colas.
TDA Listas: 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 elemento Ek+1. Si la lista contiene 0 elementos se denomina como lista vacía.
Las operaciones 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 en la 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 sus operaciones 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.
 avanzar(): avanza el iterador al siguiente nodo de la lista.
 obtener(): retorna el elemento del nodo en donde se encuentra el iterador.
En la implementación con listas enlazadas es necesario tener en 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 primer elemento, 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.

TDA Pilas: Una pila (stack o pushdown en inglés) es una lista de elementos de la cual sólo se puede extraer el último elemento insertado. La posición en donde se encuentra dicho elemento se denomina tope de la pila. También se conoce a las pilas como listas LIFO (LAST IN - FIRST OUT: el último que entra es el primero que sale).

La interfaz de este TDA provee las siguientes operaciones:
 apilar(x): inserta el elemento x en el tope de la pila (push en inglés).
 desapilar (): retorna el elemento que se encuentre en el tope de la pila y lo elimina de ésta (pop en inglés).
 tope(): retorna el elemento que se encuentre en el tope de la pila, pero sin eliminarlo de ésta (top en inglés).
 estaVacia(): retorna verdadero si la pila no contiene elementos, falso en caso contrario (isEmpty en inglés).

TDA Cola: Una cola (queue en inglés) es una lista de elementos en donde siempre se insertan nuevos elementos al final de la lista y se extraen elementos desde el inicio de la lista. También se conoce a las colas como listas FIFO (FIRST IN - FIRST OUT: el primero que entra es el primero que sale).

Las operaciones básicas en una cola son:
 encolar(x): inserta el elemento x al final de la cola (enqueue en inglés).
 sacar(): retorna el elemento que se ubica al inicio de la cola (dequeue en inglés).
 estaVacia(): retorna verdadero si la cola esta vacía, falso en caso contrario.