Listas y colas

I. INTRODUCCIÓN

Para poder entender un poco de las listas olas y pilas, mencionaremos un poco de los arrays o arreglos, ya que están ligados a este tema.

Un array es una estructura de datos caracterizada por un acceso muy rápido a cualquiera de sus posiciones, así como por un uso óptimo de espacio en memoria (suponiendo que todas sus posiciones estén ocupadas). Sin embargo, no resultaadecuado en una gama amplia de problemas debido especialmente a limitaciones como las siguientes:
• Es una estructura de datos estática, en el sentido de que no puede crecer o decrecer para adaptarse a las necesidades de uso, su tamaño debe ser conocido en el momento en que se crea. Esta limitación puede dar lugar al desperdicio de memoria debido a que su tamaño sea superior al realmente necesarioo, por el contrario, a la finalización abrupta del programa debido a que sobrepase su tamaño máximo. Una posible solución a este problema consiste en, cada vez que sea necesario redimensionar el array, crear uno nuevo y copiar los datos al mismo desde el array original.
• Algunas operaciones útiles para el manejo de datos en estructuras lineales tienen coste lineal en un array, lo cual puedesuponer una limitación cuando el tamaño del array es grande. A continuación se muestran algunos ejemplos de estas operaciones:
• Inserción en cualquier posición, sin sobre escribir ningún dato ya existente.
• Extracción de un dato, compactando el resto de datos existentes.
• Concatenación de dos estructuras de datos lineales.
• Partición de la estructura de datos lineal en dos o másestructuras.

El array necesita un espacio contiguo en memoria. Esto puede ser una limitación en el caso de arrays grandes.
Sin embargo los arreglos es una herramienta maravillosa, le permite asociar un solo nombre de variable a una colección completa de datos puede mover el arreglo completo en memoria, copiarlo y además solo haciendo referencia a un solo nombre de variable un arreglo es un conjuntofinito ordenado de elementos homogéneos, la propiedad de ordenación significa que es posible identificar el primero, segundo, tercero... y el enésimo elemento del arreglo, un arreglo puede ser un conjunto de elementos de tipo cadena en tanto que otro puede ser de tipo entero.

Un array no siempre es la estructura de datos más adecuada para resolver un problema. En este tema se presenta unaestructura de datos alternativa al array: la lista enlazada. Por otra parte, se presentan dos estructuras de datos lineales utilizadas frecuentemente en programación: las pilas y las colas.

A) LISTAS

Una lista es una secuencia de elementos llamados nodos. Cada nodo esta formado por un campo de datos y 1 o más campos de enlace que apunta(n) al siguiente nodo. Todo nodo tiene un predecesor yantecesor excepto el primero y el último.
La lectura de una lista se realiza secuencialmente pero su posición física en memoria solo depende del método para implementarla. Si por ejemplo usamos punteros –que es la técnica más adecuada– podemos almacenar los componentes de la lista en posiciones dispersas de memoria, aunque ante el usuario continuara apareciendo como una estructura secuencial.

Sellaman operaciones simples las que afectan a un solo dato y complejas las que afectan a varios. Las operaciones complejas pueden realizarse repitiendo las simples.

Dentro de las listas existen algunas clasificaciones, como son:

➢ LISTAS CIRCULARES: Son aquellas en las que el último elemento enlaza con el primero. Para evitar que la lista quede vacía se suele usar un nodo cabecera, que seráun nodo vacío que solo contiene la dirección del primer elemento de la lista. En el caso de listas ordenadas circulares, el nodo cabecera debe tener un valor inferior al de cualquier dato.

➢ LISTAS DOBLEMENTE ENLAZADAS: Aquellas con doble enlace para apuntar al nodo siguiente y anterior.

➢ LISTAS ENLAZADAS MULTIPLES: Aquellas con varios campos de enlace a elementos siguientes....