Estructuras Lineales

INTRODUCCIÓN

Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios subelementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:

* El desarrollo de compiladores de lenguajes de programación que están conformados por varios subprogramas con finalidades más específicas, como por ejemplo: el analizador de léxico que genera la tabla de símbolos.

* La simulación discreta de sistemas a través del computador, donde la mayoría de los paquetes de simulación digital ofrecen lenguajes de simulación que soportan las primitivas para el manejo de colas y sus diferentes versiones.

* La realización de sistemas operativos para los computadores, los cuales hacen un uso intensivo de las estructuras lineales, ya que internamente se soportan en los sistemas operativos, las colas de ejecución para los dispositivos, las pilas de llamadas a los subprogramas de cualquier programa, las listas de usuarios en los sistemas operativos multiusuarios, etc.

ESTRUCTURAS LINEALES

Una estructura lineal de datos o lista está conformada por ninguno, uno o varios elementos que tienen una relación de adyacencia ordenada donde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último. El tipo de dato de los elementos puede ser cualquiera, pero debe ser el mismo tipo para todos. El valor contenido en los elementos puede ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular. Sobre la base de la forma y el lugar de la realización de estas operaciones en la misma, las listas se clasifican en listas de acceso restringido y listas de acceso no restringido.

Las listas de acceso restringido son las pilas, colas y dipolos. En las pilas, las operaciones de acceso se realizan por un único extremo de la lista, al cual normalmente se denomina tope de la pila. En las colas, estas operaciones se realizan por ambos extremos de la lista llamados generalmente, inicio y fin de la cola. Finalmente, en los dipolos que son colas dobles, las operaciones se realizan también por ambos extremos de la lista, en este caso todas las operaciones se pueden hacer por ambos extremos, es decir se puede insertar o eliminar elementos por el tope o por el fin, a diferencia de la cola donde se inserta siempre por el fin y se elimina por el tope. Se puede entonces considerar al dipolo como una clase general de la clase cola.

Las listas de acceso no restringido, denominadas listas, son el tipo más general, al cual se considera como la superclase de las otras clases de listas, en específico de las pilas, colas y dipolos. Haciendo la jerarquía de clases adecuada para estas estructuras, se tiene que la lista es la clase raíz de la jerarquía que tiene como subclases la pila, la cola y el dipolo, este último a su vez tiene como subclases el dipolo de entrada restringida y el dipolo de salida restringida.

Esta jerarquía se observa en la siguiente figura:

Jerarquía de clases para las listas.

PILAS

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

Los elementos se insertan de uno en uno.

Los elementos se sacan en orden inverso al cual se ha insertado.

El único elemento que se puede observar es el último insertado.

Aplicaciones:

♦ Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados.

♦ Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento.

Aplicaciones:

♦ Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados.

♦ Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estado anterior del documento.

Ejemplo de uso del TAD Pila:

public

...