Estructuras Logicas

Estructuras lógicas

Al pensar en un "contenedor" de información la idea más simple es la de un saco que lo contenga todo, pero es fácil intuir que esta forma no es demasiado adecuada para recuperar la información. El cajón de sastre puede ser cómodo para almacenar, no para recuperar.

Desechada la anterior, la segunda idea sería tratar de almacenar juntos datos homogéneos (aunque no hay inconveniente teórico para que los tales datos sean todo lo complejos que se desee). Por ejemplo, en una aplicación real se almacenarían separadamente los datos de clientes; de proveedores, de artículos, etc. A su vez cada uno de estos almacenamientos tendrían información compleja aunque relacionada. Por ejemplo, el fichero o tabla de clientes contendría nombre, domicilio, teléfono, dirección, e-mail, web, etc de cada cliente. Lo mismo con los proveedores, artículos, etc.

A estos conjuntos de datos que se almacenan juntos, los denominamos unidades de almacenamiento (generalmente este es el enfoque utilizado). Por ejemplo, siguiendo con el supuesto anterior, almacenamos juntos los datos de clientes, y cada cliente es una unidad de almacenamiento. Aunque pueda estar constituido a su vez por un conjunto muy grande de datos, se graban o borran los datos de un cliente cada vez, esta unidad no es divisible (no puede existir medio cliente, aunque algunos de sus registros si pueden estar vacíos).

Nota: La unidad de almacenamiento corresponde con el concepto tradicional de registro, o con el de fila, si se utiliza la terminología de las bases de datos relacionales.

Respecto como están relacionadas entre sí estas unidades de almacenamiento, las estructuras de datos comúnmente utilizadas son cuatro: Colas; Pilas; Listas enlazadas y Árboles [4] que comentamos en este capítulo, y que con variaciones más o menos sofisticadas dan origen a todas las demás.

Nota: Se considera que las tres primeras pertenecen a un grupo denominado estructuras lineales, en el que existen otros tipos, por ejemplo matrices ( 4.3), tablas hash y deques ( 5.1.1). Los árboles pertenecen al grupo de los grafos en el que existen varios subtipos.

§4.1 Colas:

Las colas ("Queues") son sucesiones de registros [2] contiguos dispuestos de forma que es fácil añadir un nuevo elemento (que se coloca después del último) y/o acceder o eliminar el primero. La forma en que están construidas las hace parecerse a una tubería, el primer agua que entra es la primera que sale. Esta forma de acceder a la información se denomina FIFO ("First In First Out") primero en entrar primero en salir.

Estas entidades corresponden a lo que en matemáticas se conoce como líneas de espera, y su estudio teórico, conocido como teoría de colas, es muy importante en transporte y telecomunicación (una modalidad de transporte). A título de curiosidad podemos citar que incluso existe un lenguaje de programación denominado Oroogu, cuyo único tipo de datos es una cola.

Sus características básicas pueden sintetizarse cuatro palabras: datos contiguos, ordenación FIFO.

§4.2 Pilas:

Las pilas ("Stacks") son igualmente sucesiones de registros contiguos. Podemos imaginar que se van "apilando" sucesivamente uno sobre el otro (de ahí su nombre). Esta disposición hace que sea fácil añadir un nuevo elemento al final, accederlo o eliminarlo. Esta forma de acceso a la información se denomina LIFO ("Last In First Out") último en entrar primero en salir.

Podemos imaginar que tanto en las colas como en las pilas, insertar o eliminar un elemento intermedio, es un proceso complicado si no imposible.

Sus características se resumirían en: datos contiguos, ordenación LIFO.

§4.3 Listas enlazadas

Las listas enlazadas ("Linked list") son

...