Documentación de la Biblioteca de Estructuras de Datos Avanzadas

"Nunca consideres el estudio como una obligación sino como una oportunidad para penetrar en el bello y maravilloso mundo del saber…"

Introducción

Cuando se implementa una clase es necesario preocuparse por elegir una representación para los objetos de esa clase. Esta representación consiste en un conjunto de variables de instancias que almacenarán todos los datos que se requiere memorizar para poder realizar las operaciones, además es necesario preocuparse por implementar las operaciones de las clases.

Existen patrones de organización para las variables de instancia, estos patrones se denominan Estructuras de Datos y una de las aplicaciones más interesantes y potentes de la memoria dinámica y los punteros son precisamente estas.

No existe una estructura de datos que sirva para todos los propósitos, por tal motivo es importante conocer las ventajas y desventajas de cada una de ellas para en un momento dado conocer cual es la más óptima para darle solución a un determinado problema.

Antes de explorar las diferentes estructuras de datos y sus algoritmos específicos, es necesario examinar una cuestión básica: ¿Qué es una estructura de datos? El conocimiento de este concepto ayudará a entender mejor este documento.

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales[1]con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.

Los datos de tipo estándar pueden ser organizados en diferentes estructuras de datos: estáticas y dinámicas.

• Estructura de Datos Estáticas:

Son aquellas en las que el espacio ocupado en la memoria de la computadora se define en tiempo de compilación y no puede ser modificado durante la ejecución del programa. Corresponden a este tipo los arreglos y los registros.

• Estructuras de Datos Dinámicas:

Son aquellas en las que el espacio ocupado en la memoria de la computadora puede ser modificado en tiempo de ejecución. Corresponden a este tipo las listas, las pilas, las colas, etc.

Cada estructura de datos dinámica posee un comportamiento específico y como tal una lógica diferente para operarla, tanto es así que no es lo mismo eliminar un nodo de una lista simplemente enlazada que uno en una de doble referencia, debido a que la lógica cambia aunque la operación sea la misma.

Las estructuras de datos tienen en común que un identificador y un nombre pueden representar a múltiples datos individuales.

Una estructura de datos define además la organización e interrelación de los elementos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

• Adicionar, adiciona un nuevo valor a la estructura.

• Eliminar, borra un valor de la estructura.

• Buscar, encuentra un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binaria (siempre y cuando los datos estén ordenados).

Otras operaciones que se pueden realizar son:

• Ordenar, ordena a los elementos pertenecientes a la estructura.

• Concatenar, dadas dos estructuras originar una nueva ordenada y que contenga a las concatenadas.

Para la realización de las operaciones cada estructura ofrece ventajas y desventajas en relación a su simplicidad y eficiencia. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos, así como la naturaleza de los datos que se almacenarán.

Este documento de ayuda explora cinco de esas estructuras de datos en algunas de sus variantes de implementación:

• Listas:

• Lista con Arreglo.

• Lista Simplemente Enlazada.

• Lista Circular Simplemente Enlazada.

• Lista Doblemente Enlazada.

• Lista Circular Doblemente Enlazada.

• Pilas:

• Pila con Arreglo.

• Pila con Listas Enlazables.

• Colas:

• Cola de Prioridad:

• Cola de Prioridad con Arreglo.

• Cola de Prioridad con Listas Enlazables.

• Cola de Amigos:

• Cola de Amigos con Arreglo.

• Cola de Amigos con Listas Enlazables.

• Tablas Hash:

• Tabla Hash Abierta.

• Tabla Hash Cerrada.

• DCEL.

Seleccionar un tipo de estructura de datos idónea para una aplicación dependerá esencialmente de la naturaleza del problema a resolver y en menor medida del lenguaje de programación.

La elección adecuada de las estructuras de datos y el algoritmo empleado permite obtener un diseño eficiente, tanto en recursos ocupados en la memoria de la computadora como en el tiempo de ejecución.

CAPÍTULO 1

Estructura de datos: Lista

En este capítulo se da a conocer el concepto de la estructura de datos Lista y de algunas de sus formas de implementación, conjuntamente se reflejan las ventajas y las desventajas de algunas, así como las aplicaciones que tienen en la vida práctica, además de mostrar el seudocódigo. Lo mencionado anteriormente permite tener un mejor conocimiento de este tipo de estructura de datos y saber en un problema determinado cual es la más óptima para darle solución al mismo.

¿Qué es una lista?

Una lista se define como una n-tupla de elementos (donde li es el i-ésimo elemento de la lista) ordenados de forma consecutiva, o sea, el elemento li precede al elemento li +1: L= (l1, l2,…, ln). Si la lista contiene cero elementos se denomina lista vacía. (1)

Operaciones básicas del TDA Lista:

• a. Vacía ( ), devuelve verdadero si la longitud de la lista es cero. No se modifica la lista.

• b. Longitud ( ), devuelve |L|, la longitud de la lista (cantidad de elementos). No se modifica la lista.

• c. Obtener (i), devuelve el i-ésimo elemento de la lista (el que se encuentra en la posición i), si la posición i no existe se dispara una excepción. No se modifica la lista.

• d. Adicionar(x), adiciona el elemento x en la cola de la lista, haciendo que la longitud de la lista se incremente en uno. Si la operación no tiene éxito, se dispara una excepción.

• e. Insertar(x, i), inserta el elemento x en la posición i, haciendo que los elementos li, li+1,…, ln pasen a ser los elementos li+1, li+2,…, ln+1 y se incrementa en uno la longitud de la lista. Si la operación no tiene éxito, se dispara una excepción.

• f. Eliminar(i), elimina el elemento almacenado en la posición i de la lista, haciendo que los elementos li+1, li+2,…,ln pasen a ser los elementos li, li+1, …, ln-1, esta operación disminuye en uno la longitud de la lista. Si la posición no existe se dispara una excepción.

Ventajas:

• Las listas son dinámicas, es decir, se pueden almacenar en ellas tantos elementos como se necesiten, siempre y cuando haya espacio suficiente en la memoria de la computadora.

• Al insertar un elemento en la lista, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces de los mismos.

• Al eliminar un elemento sucede lo mismo que se mencionó en el punto anterior.

Desventajas:

• El acceso a un elemento es más lento, debido a que la información no está en posiciones contiguas en la memoria de la computadora, por lo que no se puede acceder a un elemento con base en su posición como se hace en los arreglos.

Aplicaciones:

• Las listas son comunes en la vida diaria: listas de alumnos, listas de clientes, listas de espera, listas de distribución de correo, etc.

• Las listas son estructuras de datos muy útiles para los casos en los que se quiere almacenar información de la que no se conoce su tamaño con antelación.

• También son valiosas para las situaciones en las que el volumen de datos se puede incrementar o decrementar dinámicamente durante la ejecución del programa.

• Cuando se aplican restricciones de acceso a las listas, se tienen a las pilas y a las colas, que son listas especiales.

• Puede usarse para implementar una amplia variedad de TDA, es decir, el TDA Lista, sirve a menudo como una pieza básica en la construcción de los TDA más complicados, como es el caso de las tablas hash, los árboles, los grafos, etc.

1.1 Lista utilizando arreglos.

Definición 1.1:

Un TDA Lista puede utilizar como estructura de datos a los arreglos lineales, esta clase se deriva de la clase Lista. Los arreglos lineales son convenientes fundamentalmente por la simplicidad de su uso, además el tiempo de acceso a los elementos individuales de un arreglo es fijo para todas las operaciones, lo que resulta muy eficiente. (1)

Sin embargo, las operaciones de inserción y borrado de los elementos en los arreglos son ineficientes, puesto que para insertar un elemento en la parte media del arreglo es necesario mover todos los elementos que se encuentren detrás de él para hacer espacio y al borrar un elemento es preciso mover todos los elementos para ocupar el espacio desocupado.

Ventajas:

• Todos los elementos de la lista se almacenan en posiciones de memoria consecutivas, pero se habla de disposición secuencial en la memoria de la computadora. Con esta disposición se accede a cualquier elemento de la estructura de datos en tiempo constante, o sea, permiten un acceso aleatorio.

• Son convenientes por una razón fundamental, la simplicidad de su uso.

• Además el tiempo de acceso a los elementos individuales de un arreglo es fijo para todas las operaciones, lo cual resulta muy eficiente.

Desventajas:

• Al asignar el arreglo en tiempo de compilación debe establecerse un límite a priori sobre el número de elementos que pueden ser almacenados en las listas.

• Para inserciones y eliminaciones frecuentes hay que hacer corrimientos costosos.

• Otra limitación de estas listas que emplean arreglos es que se llenarán ó necesitarán ser redimensionadas, lo cual es una costosa operación que incluso puede no ser posible si la memoria de la computadora se encuentra fragmentada.

• Al insertar un elemento en el arreglo, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces. Esto no es así en los arreglos, ya que si el elemento se inserta al inicio o en el medio, se posee un tiempo lineal debido a que se tienen que mover todos los elementos que se encuentran a la derecha de la posición donde se va a insertar y después insertar el elemento en dicha posición; solo al insertar al final del arreglo se obtienen tiempos constantes.

• Al eliminar un elemento sucede lo mismo que se mencionó en el punto anterior.

Seudocódigo:

1.2 Lista Enlazada.

Definición 1.2:

Una lista enlazada es una secuencia de nodos enlazados donde el orden de los elementos está determinado por un campo de enlace (referencia) explícito en cada elemento. Esta definición remite al concepto de nodo.

Un nodo se compone de un campo que contiene el tipo de dato de los elementos de la lista y por uno o más campos que son referencias a otros nodos. (2)

Figura 1.1 Representación gráfica de un Nodo.

Ventajas:

• Una lista enlazada es un TDA dinámico, su tamaño puede cambiar durante la ejecución del programa y los elementos se pueden insertar indefinidamente.

• No es preciso conocer la cantidad de elementos en tiempo de compilación.

• Ni las inserciones ni las eliminaciones implican realizar corrimientos de los elementos de la lista. Al insertar un elemento en la lista, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces.

Desventajas:

• No permite el acceso directo a un elemento arbitrario de la lista. Para acceder al i-ésimo elemento, se debe recorrer la lista, comenzando por el primer nodo, hasta llegar al elemento deseado, es decir, permiten solamente un acceso secuencial a los elementos.

1.3 Lista Simplemente Enlazada.

Definición 1.3:

Una lista simplemente enlazada se compone por nodos de enlace simple, es decir, por nodos que tienen solamente un campo Dirección. Un nodo sólo esta enlazado con el nodo que le sigue. (2)

Figura 1.2 Representación gráfica de una Lista Simplemente Enlazada.

Desventajas:

• Las listas simplemente enlazadas solo pueden ser recorridas en una dirección. Esto hace que las listas sean inadecuadas para aquellos casos en los que es útil buscar un elemento por su índice rápidamente, como el heapsort.

• Otra desventaja de las listas simplemente enlazadas es el almacenamiento extra necesario para las referencias, que a menudo las hacen poco prácticas para listas de pequeños datos como caracteres o valores booleanos.

Seudocódigo:

1.3.1 Lista Circular Simplemente Enlazada.

Definición 1.4:

Una lista circular simplemente enlazada es una lista lineal en la que el último elemento se enlaza con el primero. Cada nodo tiene un enlace similar al de las listas simplemente enlazadas, excepto que el siguiente nodo del último apunta al primero.

En las listas circulares no puede hablarse ni de "primero" ni de "último", porque cualquier nodo puede ser el nodo de entrada y de salida. Al igual que en una lista simplemente enlazada, los nuevos nodos pueden ser solo eficientemente insertados después de uno que se tenga referenciado, por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista circular simplemente enlazada, esto permite rápidas inserciones al principio y accesos al primer nodo desde el puntero del último nodo. Además es posible acceder a cualquier elemento de la lista desde cualquier punto dado. La figura 1.3 muestra la representación gráfica de una Lista Circular Simplemente Enlazada.

Figura 1.3 Representación gráfica de una Lista Circular Simplemente Enlazada.

Ventajas:

• Son útiles para describir estructuras circulares.

• Pueden recorrer la lista desde cualquier punto.

• También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

• No existe ningún elemento que apunte a Nulo.

• Se integra una estructura de tipo anillo.

• Solo hay una cabeza. La cabeza siempre será el siguiente enlace para algún nodo.

Desventaja:

• Se pueden llegar a crear recorridos en bucles infinitos.

Aplicaciones:

• Este tipo de listas es el más usado para dirigir buffers, para "ingerir" datos y para visitar todos los nodos de una lista a partir de uno dado.

1.4 Lista Doblemente Enlazada.

Definición 1.5:

Una lista doblemente enlazada es una lista lineal que se compone por nodos de enlace doble, es decir, por nodos que tienen dos campos: Dirección1 y Dirección2. Un nodo está enlazado con el nodo que le sigue y con el nodo que inmediatamente le antecede. Esto permite recorrer la lista en cualquier dirección. (2)

Figura 1.4 Representación gráfica de una Lista Doblemente Enlazada.

Ventajas:

• Una ventaja que tienen es que pueden recorrerse en ambos sentidos, ya sea para efectuar la operación de insertar, actualizar o borrar cualquier elemento.

• Otra ventaja de las listas doblemente enlazadas es que se puede usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera.

• La otra ventaja es que las búsquedas son algo más rápidas puesto que no hace falta hacer referencia al elemento anterior.(3)

Desventajas:

• El único precio que se paga por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de las listas, es decir, ocupan más espacio en memoria por nodo que una lista simple y sus operaciones básicas resultan más costosas.(3)

Seudocódigo:

1.4.1 Lista Circular Doblemente Enlazada.

Definición 1.6:

Una lista circular doblemente enlazada es una lista lineal en la que cada elemento tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero.

Al igual que una lista doblemente enlazada, en la circular doble las inserciones y eliminaciones pueden realizarse desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni final. Un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola y así mantener el orden como en una lista doblemente enlazada. La figura 1.5 muestra la representación gráfica de una Lista Circular Doblemente Enlazada.

Figura 1.5 Representación gráfica de una Lista Circular Doblemente Enlazada.

Ventajas:

• Son útiles para describir estructuras circulares.

• Pueden recorrer la lista desde cualquier punto.

• También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

• No existe ningún elemento que apunte a Nulo.

• Se integra una estructura de tipo anillo.

• Solo hay una cabeza. La cabeza siempre será el siguiente enlace para algún nodo.

Desventaja:

• Se pueden llegar a crear recorridos en bucles infinitos.

1.5 Observaciones Generales sobre el TDA Lista.

Listas Enlazadas vs. Arreglos.

En las implementaciones de las listas utilizando arreglos los métodos son sencillos, la manipulación en sí del arreglo lo es, pero una limitante importante es que aún siendo dinámico el arreglo y pueda crecer según se le necesite, está compuesto por un número definido a priori, que impone restricciones sobre el tamaño de la lista.

Otra limitante relacionada con esto, es que al hacer crecer el arreglo no se puede hacer sobre él mismo, esto implica que al cambiarle el tamaño sería necesario copiar sus elementos en un arreglo temporal, lo que introduce un elemento de ineficiencia en la solución que las utilice.

Los arreglos lineales son convenientes por una razón fundamental, la simplicidad de su uso, además el tiempo de acceso a los elementos individuales de un arreglo es fijo para todas las operaciones, lo que resulta muy eficiente. La clase derivada se llamaría Lista basada en Arreglos Estáticos.

Las listas enlazadas poseen muchas ventajas sobre los arreglos. Los elementos se pueden insertar en una lista indefinidamente mientras que un arreglo tarde o temprano se llenará ó necesitará ser redimensionado, una costosa operación que incluso puede no ser posible si la memoria de la computadora se encuentra fragmentada.

En algunos casos se pueden lograr ahorros de la memoria de la computadora almacenando la misma "cola" de elementos entre dos o más listas, es decir, la lista concluye en la misma secuencia de elementos. De este modo, se pueden añadir nuevos elementos al frente de la lista manteniendo una referencia tanto al nuevo como a los viejos elementos, esto es un ejemplo simple de una estructura de datos persistente.

Por otra parte, los arreglos permiten accesos aleatorios mientras que las listas enlazadas solo permiten acceso secuencial a los elementos. Las listas simplemente enlazadas solo pueden ser recorridas en una dirección. Esto hace que las listas sean inadecuadas para aquellos casos en los que es útil buscar un elemento por su índice rápidamente, como el heapsort. El acceso secuencial en los arreglos también es más rápido que en las listas enlazadas.

Otra desventaja de las listas enlazadas es el almacenamiento extra necesario para las referencias, que a menudo las hacen poco prácticas para listas de pequeños datos como caracteres o valores booleanos.

También puede resultar lento y abusivo el asignar memoria para cada nuevo elemento. Existe una variedad de listas enlazadas que contemplan los problemas anteriores para resolver los mismos.

Un buen ejemplo que muestra los pros y los contras del uso de los arreglos sobre las listas enlazadas es la implementación de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de círculo. Se empieza a partir de una persona predeterminada y se cuenta n veces, la persona n-ésima se saca del círculo y se vuelve a cerrar el grupo. Este proceso se repite hasta que queda una sola persona, que es la que gana.

Este ejemplo muestra las fuerzas y debilidades de las listas enlazadas frente a los arreglos, ya que viendo a la gente como nodos conectados entre sí en una lista circular se observa como es más fácil suprimir estos nodos. Sin embargo, se ve como la lista perderá utilidad cuando haya que encontrar a la siguiente persona a borrar. Por otro lado, en un arreglo el suprimir los nodos será costoso ya que no se puede quitar un elemento sin reorganizar el resto. Pero en la búsqueda de la n-ésima persona tan sólo basta con indicar el índice n para acceder a él, resultando mucho más eficiente.

Listas Doblemente Enlazadas vs. Listas Simplemente Enlazadas.

Las listas doblemente enlazadas requieren más espacio por nodo y sus operaciones básicas resultan más costosas pero ofrecen una mayor facilidad para manipular los elementos ya que permiten el acceso secuencial a la lista en ambas direcciones. En particular, se puede insertar o borrar un nodo con un número fijo de operaciones dando la dirección de dicho nodo (las listas simples requieren la dirección del nodo anterior para insertar o suprimir correctamente.). Algunos algoritmos requieren el acceso en ambas direcciones.

Listas Circulares Enlazadas vs. Listas Lineales Enlazadas.

Las listas circulares son más útiles para describir estructuras circulares y tienen la ventaja de poder recorrer la lista desde cualquier punto. También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

Las listas circulares evitan excepciones en las operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

CAPÍTULO 2

Estructura de datos: Pila

A lo largo de este capítulo se muestra el concepto de la estructura de datos Pila y de algunas de sus formas de implementación, al mismo tiempo se exponen las ventajas y las desventajas de cada una, así como las aplicaciones que tienen en la vida práctica, además de mostrar el seudocódigo. Lo mencionado anteriormente permite tener un mejor conocimiento de este tipo de estructura de datos y saber en un problema determinado cual es la más óptima para darle solución al mismo.

Las pilas pueden representarse mediante el uso de:

• Arreglos.

• Listas enlazadas.

¿Qué es una Pila?

Una pila (stack en inglés) es una estructura sencilla, mucho más simple que la lista y se puede definir como una colección ordenada de elementos S = (S1, S2,…, Sn) donde se adicionan y eliminan por un mismo extremo conocido como tope. Se dice que S1 es el elemento del fondo de la pila y Sn es el elemento que se encuentra en el tope. Se les conoce como estructuras LIFO[2]debido al orden en que se apilan y extraen los elementos en la misma. (3)

Figura 2.1 Representación gráfica de una Pila.

La interfaz de este TDA provee las siguientes operaciones:

• a. Vacía ( ), devuelve verdadero si la pila está vacía.

• b. Tope ( ), devuelve el elemento que se encuentra en el tope de la pila, se conoce también con el nombre de cima. Si es llamado con la pila vacía lanza una excepción.

• c. Apilar (x), coloca a x en el tope de la pila, se conoce también con el nombre de adicionar.

• d. Desapilar ( ), elimina el elemento que se encuentra en el tope de la pila se conoce también con el nombre de extraer. Si es llamado con la pila vacía lanza una excepción.

Aplicaciones:

• Se usan en los compiladores (parsers: reconocedores sintácticos de los compiladores).

• En la programación de sistemas (para registrar llamadas a subprogramas y recuperar los datos anteriores, o recuperar los parámetros).

• Otra aplicación de las pilas lo constituye el mecanismo que establecen los lenguajes de programación para garantizar las llamadas anidadas a subprogramas dentro de una aplicación.

• Se aplican además en la recuperación de elementos en orden inverso al que fueron colocados (en un depósito, una pila de contenedores, sillas, etc.).

• Convertir notación infija a postfija o prefija.

• Para la implementación de la recursividad.

2.1 Pila utilizando arreglos.

Definición 2.1:

Una pila puede ser implementada usando un arreglo el cual se irá llenando en la forma usual, conjuntamente con este se tiene un atributo que almacena el índice de la última posición utilizada. (3).

Si se implementa una pila utilizando un arreglo se debe especificar primero el tamaño máximo de la pila y además definir una operación que nos indique que la misma está llena y en caso de que se desee adicionar un elemento sería necesario crear otro arreglo mayor que el anterior, copiar todos los elementos de la pila en este arreglo y finalmente liberar la memoria ocupada por el arreglo inicial.

Figura 2.2 Representación gráfica de una Pila utilizando arreglos.

Desventajas:

• El inconveniente de esta implementación es que es necesario fijar de antemano el número máximo de elementos que puede contener la pila, MAX_ELEM, y por lo tanto al apilar un elemento es necesario controlar que no se inserte un elemento si la pila está llena.

Seudocódigo:

2.2 Pila utilizando listas enlazadas.

Definición 2.2:

Otra implementación de la pila puede ser utilizando listas enlazadas, donde los nodos de la lista simplemente enlazada se emplean para almacenar la información de la pila. En este caso no existe el problema de tener que fijar el tamaño máximo de la pila pues la capacidad de la pila está acotada por la cantidad de memoria de la computadora y la operación que indica que la misma está llena no tiene sentido. (3)

Figura 2.3 Representación gráfica de una Pila con listas enlazables.

En este caso no existe el problema de tener que fijar el tamaño máximo de la pila (aunque siempre está acotado por la cantidad de la memoria disponible en la computadora).

Ventajas:

• En este caso no existe el problema de tener que fijar el tamaño máximo de la pila, es decir, no se necesita saber la cantidad de elementos que va a contener. Esto se debe a que al ser implementadas a base de punteros, se va tomando memoria a medida que se cargan los datos, si no hay más memoria disponible no se ingresan más datos.

Aplicaciones:

• Una de sus aplicaciones más sencillas es invertir una cadena.

• Otra aplicación más compleja consiste en identificar si una expresión tiene sus paréntesis balanceados[3]

• Permite la conversión de expresiones infijas a postfijas.

• Se utilizan en la implementación de la recursividad.(5)

Seudocódigo:

2.3 Observaciones Generales sobre el TDA Pila.

El uso del arreglo es idóneo cuando se conoce de antemano el número máximo de elementos que van a ser apilados y el compilador admite una región contigua de memoria para el arreglo. En otro caso lo más recomendable sería usar la implementación por listas enlazadas, donde podría emplearse además si el número de elementos llegara a ser excesivamente grande.

La implementación por arreglo es ligeramente más rápida. En especial, es mucho más rápido a la hora de eliminar los elementos que hayan quedado en la pila. Por lista enlazada esto no es tan rápido. Por ejemplo, piénsese en un algoritmo que emplea una pila y que en algunos casos al terminar éste su ejecución deja algunos elementos sobre la pila. Si se implementa la pila mediante una lista enlazada entonces quedaría en memoria una serie de elementos que es necesario borrar. La única manera de borrarlos es liberar todas las posiciones de la memoria de la computadora que le han sido asignadas a cada elemento, esto es desapilar todos los elementos. En el caso de una implementación con arreglo esto no es necesario, salvo que quiera liberarse la región de la memoria ocupada por éste.(6)

No es difícil implementar las operaciones Apilar y Desapilar en tiempo T (1) utilizando tanto una lista con disposición secuencial, como una lista enlazada. Para ambas formas de listas se tienen dos opciones básicas: se puede mantener el tope de la pila en la cabeza o en la cola de la lista. En una lista con disposición secuencial es más eficiente mantener el tope de la pila en la cola de la lista. En este caso, en la operación de Apilar simplemente se añade un nuevo elemento a la cola de la lista y en una operación de Desapilar se elimina el elemento que se encuentra al final de la lista.

CAPÍTULO 3

Estructura de datos: Cola

En el transcurso de este capítulo se aborda el concepto de la estructura de datos Cola y de algunas de sus formas de implementación, conjuntamente se exponen las ventajas y las desventajas de cada una, así como las aplicaciones que tienen en la vida práctica, además de mostrar el seudocódigo. Lo mencionado anteriormente permite tener un mejor conocimiento de este tipo de estructura de datos y saber en un problema determinado cual es la más óptima para darle solución al mismo.

¿Qué es una cola?

Una cola (queue en inglés) es una estructura de datos caracterizada por ser una lista ordenada de elementos Q = (Q1, Q2,…, Qn), donde la operación de adición se realiza por un extremo, llamado cola, y la operación de extracción por el otro, llamado cabeza y tiene un comportamiento de tipo FIFO[4]por el modo de acceso a sus elementos. (3)

Figura 3.1 Representación gráfica de una Cola.

La Cola tiene como operaciones básicas:

• a. Vacía ( ), devuelve verdadero si la cola está vacía.

• b. Frente ( ), devuelve el elemento que se encuentra en la primera posición de la cola. Se dispara una excepción cuando la cola está vacía.

• c. Fondo ( ), devuelve el elemento que se encuentra en la última posición de la cola. Se dispara una excepción cuando la cola está vacía.

• d. Adicionar (x), coloca a x en la cola (después del último elemento) de la cola.

• e. Extraer ( ), elimina el elemento que se encuentra en la cabeza de la cola, si está vacía se dispara una excepción.

Aplicaciones:

• Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos.

• Su utilización es infinita, sobre todo en aquellos problemas que tienen un componente de simulación de procesos, por ejemplo la simulación de una cola formada frente a un cajero automático.

• Para modelar 'colas reales' en el mundo de las computadoras: colas de tareas, colas de procesos, colas de impresión en el sistema operativo Windows, etc. Cada usuario de una red de Windows coloca sus trabajos de impresión y el sistema lo imprime en el mismo orden en que fueron insertados en la cola de impresión.

• La aplicación más común de las colas es la organización de tareas de un ordenador. Los procesos forman colas para la utilización de los recursos de un sistema computacional.

3.1 Cola de prioridad.

Definición 3.1:

Una cola de prioridad es una cola cuyos elementos tienen asociado  una prioridad y se atienden en el orden indicado por la misma, de forma que el orden  en  que  los elementos son procesados sigue las siguientes reglas:

• El elemento con mayor prioridad es procesado primero.

• Si varios elementos tienen la misma prioridad, se atenderán en dependencia del orden en que fueron adicionados. Hay dos formas de implementación:

• A cada nodo añadirle un campo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

Figura 3.2 Representación gráfica de una Cola de Prioridad.

• Crear tantas colas como prioridades exista y almacenar a cada elemento en la cola correspondiente.

Figura 3.3 Representación gráfica de una Cola de Prioridad con varias Colas asociadas a cada prioridad.

Tipos de Colas de Prioridad:

• Colas de prioridad con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.

• Colas de prioridad con ordenamiento descendente: son iguales que las colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

Operaciones de las colas de prioridad (en cada una de estas operaciones, P se supone que es una cola de prioridad arbitraria):

• a. Insertar (P, x), añade el elemento x a P.

• b. Encontrar_Min (P), devuelve elemento de P con la prioridad más alta (menor valor de clave). Si P está vacía esta operación produce un error.

• c. Eliminar_Min (P), quita y devuelve el elemento de P con la prioridad más alta (menor valor de clave). Si P está vacía esta operación produce un error.(4)

Desventajas:

• La implementación de las colas de prioridad es costosa en algunas implementaciones:

Partes: 1, 2