Documentación de la Biblioteca de Estructuras de Datos Avanzadas
- Introducción
- Estructura de datos: Lista
- Estructura de datos: Pila
- Estructura de datos: Cola
- Estructura de datos: Tabla
Hash - Estructura de datos: DCEL
- Coclusiones
- Glosario de Términos y
siglas - Referencias
bibliográficas
"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.
Arreglo | Lista Enlazada | |
Indexado | O(1) | O(n) |
Inserción / | O(1) | O(1) or O(n)2 |
Inserción / | O(n) | O(1) |
Persistencia | No | Simples sí |
Localización | Buena | Mala |
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:
Página siguiente ![]() |