TEMA 2. ESTRUCTURAS LINEALES


OBJETIVOS
En este tema se definen varios tipos abstractos de datos que tienen una propiedad común, disponer de una estructura lineal.Para cada uno de estos TAD se realiza su especificación y se dan implementaciones alternativas. Para ilustrar la utilidad de losmismos se presentan ejemplos de aplicación para su realización en Java.

INTRODUCCION


♦ Las estructuras lineales son importantes porque aparecen con mucha frecuencia en situaciones de la vida: Una cola de clientes
de un banco, las instrucciones de un programa, los caracteres de una cadena o las páginas de un libro.
♦ Características: existe un único elemento, llamado primero, existe un único elemento, llamado último, cada elemento, excepto el
primero, tiene un único predecesor y cada elemento, excepto el último, tiene un único sucesor.


♦ Operaciones: crear la estructura vacía, insertar un elemento, borrar y obtener un elemento. Para definir claramente el
comportamiento de la estructura es necesario determinar en qué posición se inserta un elemento nuevo y qué elemento se borra o se obtiene.
♦ Principales estructuras lineales: pilas,
colas y listas.

Una pila es un contenedor de objetos que son insertados y eliminados de acuerdo con el principio de que el último en entrar es el primero en salir.
♦ También se les denomina estructuras LIFO
(Last In First Out).

TAD PILA

Las pilas pueden representarse mediante el uso de:
• Arreglos.
• Listas enlazadas.
Al utilizar arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Una vez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos.
La variable cima contiene el número de elementos actualmente e la pila y puede ser utilizada como un subíndice o como un puntero al elemento superior de la pila. Si una pila no tiene elementos, se dice que es una pila vacía. La variable o puntero cima se incrementa en uno al poner un elemento en la pila y se decrementa en uno al quitar el elemento.