Estructuras de datos y todo eso

Acabo de empezar a escribir este blog, en el que me he propuesto escribir solo lo que me apetezca…  y el caso es que varios conocidos mios, están cursando la carrera de ingeniería informática, y estos últimos días me han pedido ayuda con la asignatura que ellos llaman FP2, y me ha parecido interesante escribir un poco, precisamente sobre eso, sobre algunos fundamentos de programación (en C/C++).

Voy a hablar de las estructuras de datos básicas que podríamos decir que son la Pila, lista y cola.

Una estructura de datos, es en programación, una forma de organizar y acceder a conjuntos de datos, de forma que podríamos decir, que las estructuras de datos, son distintos modelos de organizar conjuntos de información.

Como eso no suena muy claro, voy a enfocarlo de otra manera menos ortodoxa (espero que esto no lo lea nunca ningún experto :D)

Imagina que estás en tu casa, y de pronto el lavavajillas termina su trabajo, y los platos están listos para que los saques y los metas en el armario, bien, como la distancia entre el armario de los platos, y el lavavajillas, es un poco grande, os cansáis de tanto ir arriba y abajo, y le pedís a vuestra esposa/madre, que  se ponga al lado del armario, y vosotros le iréis pasando los platos.

Entonces empiezas a sacar platos del lavavajillas, y los vas dejando encima de la mesa, y de ahí, los va cogiendo ella, y los va metiendo en el armario.

En este ejemplo, los platos son los datos unitarios, y la mesa, es la memoria, en donde se almacenan los datos, el cómo nosotros pongamos los platos en la mesa, y en como ella los saque de la mesa, constituirán una estructura de datos.

Vamos a poner el ejemplo mas típico de todos, si vas dejando los platos encima de la mesa, cada uno encima del otro, estarás utilizando una estructura de datos llamada pila, y su particularidad es que el último plato que metas, será el primero en salir, esto se conoce como LIFO (Last Input, First Output).

Vale, con nuestro ejemplo de los platos, hemos descubierto ya la primera estructura de datos, la pila, la cual ya sabemos que es de tipo LIFO. En la pila, existe un concepto de siguiente, el siguiente plato es el que hay debajo de el que quitas, como siempre podemos ir agregando platos a la pila (en una habitación que no tuviese techo) la pila permite apilar tantos datos como quieras, sin afectar a los platos que yo había, ni cambiarlos de lugar o reestructurarlos.

Como vemos, el esfuerzo necesario para agregar un plato a la pila es mínimo y solo implica a ese plato.

Sin embargo, imagina que le dices a tu querida ayudante: saca primero el plato séptimo empezando por abajo, ella tendrá que primero contar los platos, recorriendo todos los platos hasta llegar al 7, levantar los de encima, coger el 7, y dejar otra vez los otros encima.

Como veis, el esfuerzo de acceder a un plato concreto, y no siempre el de encima, es muy grande.

Para solventar eso, podríamos cambiar el modo en el que apilamos los platos, podríamos colocar unas cajas numeradas encima de la mesa, en las que cada una cupiese un plato, al hacer esto, en la mesa cabrían como máximo unas 20 cajas, tu irías metiendo empezando por la caja 1, y acabando en la 20.

Al hacer esto, estaríamos usando un vector (array).

Tu ayudante, podría ir sacando platos de las cajas (posiciones del array), y metiéndolos en el armario. Si ahora le pidieses el plato número siete, solo tendría que ir y coger el plato de la caja (posición) 7, sin necesidad de mover nada, ni contar nada. El esfuerzo ha sido mucho menor, sin embargo, este método tiene también sus contras…

– Solo caben 20 platos, y si queremos meter mas, hay que hacer cosas muy costosas, como poner otra mesa y llenarla de cajas.
– Aunque tengas solo 3 platos, las cajas te ocupan gran parte de la mesa (que hemos dicho que es la memoria)

Como es lógico, todo el mundo, sin saber programar usa una pila para este problema, en el mundo real. La gente simplemente va apilando platos en lugar de utilizar cajas, por que? Por que en el problema planteado, no existe normalmente la necesidad de coger un plato arbitrario, sino que solo hay que ir apilando y desapilando.

Esta demostración sirve para ilustrar un par de cosas, la primera, es que distintas formas de organizar datos, proporcionan distintas ventajas y desventajas, y que en cada problema, hay que utilizar la adecuada.

Para extenderme un poco mas, seguramente alguien habrá pensado que el caso de la pila tiene otra desventaja, que es que los platos salen de la pila de platos, en un orden invertido al que entraron, por lo cual, el primer plato que apilaste, permanece en la pila mucho tiempo, y el último plato apilado, permanece en la pila un instante.

En el caso de los platos, esto no importa, pero, y si importase? Habría que utilizar una cola.

Una cola funciona exactamente igual que una pila, con la diferencia, que los platos se meten por arriba, y se sacan por abajo (imaginaros una mesa con una trampilla que tiene platos encima, y que se abre dejando caer un solo plato cada vez, y por ahí recoge los platos tu ayudante).

Usando una cola, tienes las mismas ventajas y desventajas que usando una pila, pues son sustancialmente lo mismo, pero en la cola se preserva el orden, el primer plato que metes, es el primer plato que sale (FIFO, First Input, First Output)

Es lógico que la gente use pilas y no colas para el problema de los platos, pues el orden en ese caso, no importa.

En toda esta explicación hay un concepto implicito, no tan fácil de ver, que es el concepto de lista, una lista es una forma de ordenar datos en la cual, cada datos apunta al siguiente, y el siguiente al siguiente, y nosotros solo tenemos el primero de todos, pero accediendo a su siguiente, y al siguiente del siguiente etc, podemos acceder a cualquier dato de la lista.

Una pila, es una lista, pues utilizamos el concepto siguiente, y una cola igual, cada vez que alguien desapila un plato de la pila, queda visible el siguiente, y cada vez que tu apilas un plato en la pila, lo haces encima del siguiente.

Como se puede ver, la pila y la cola, son formas de trabajar con listas, formas de ir metiendo y sacando cosas de listas, listas en las cuales, nosotros solo vemos el elemento que hay a la cabeza (como en el caso de los platos) y luego su siguiente, y su siguiente…

Existen otras estructuras de datos, pero de momento solo he querido entrar en estas 4 básicas: Vector, Pila, Cola y Lista.

En resumen:

– Si nuestro conjunto de datos, requiere que se pueda acceder a un dato concreto, de forma rápida, hay que utilizar un vector, donde podemos pedir la casilla X, sin pasar por las demas (acceso aleatorio)
– Si nuestro conjunto de datos tiene un volumen indeterminado y variable, debemos usar una lista
– En dependencia del orden y la forma en la que queramos ir sacando y metiendo cosas de la lista, debemos trabajar con ella en forma de cola, o en forma de pila

Como curiosidad, he desarrollado un ejemplo muy muy simplificado de Pila en C++, para que se vea una aplicación práctica, es un programa que apila 3 números, luego los desapila, y los muestra por pantalla:

Ejemplo de Pila en C++

Espero que esto ayude un poco a cualquiera que esté estudiando todos estos temas y se sienta un poco perdido🙂

Por cierto, cuando le explicaba a un conocido mio, un fanático de kde, que estaba ayudando a algunos conocidos a entender FP2, me dijo: “es que todo eso ya te lo da Qt, no hace falta saberlo cuando programas en Qt)” Qt es una librería de clases, utilizada como base de KDE… mi duda es: ¿y entonces, como disciernes que estructura de datos usar en cada caso y por que?

10 Responses to “Estructuras de datos y todo eso”


  1. 1 ironjon agosto 29, 2008 a las 1:06 pm

    Muy buena comparacion🙂

  2. 2 rooibo agosto 29, 2008 a las 2:30 pm

    Gracias ironjon, y bienvenido al blog🙂

  3. 3 Armormi enero 20, 2009 a las 4:14 am

    gracias por este blog ayuda mucho a ese tema

  4. 4 Brunny enero 20, 2009 a las 10:33 pm

    Excelente las comparaciones me sirvieron de mucho,gracias

  5. 5 JOEL marzo 23, 2009 a las 4:50 pm

    Muchas gracias por los comentarios y la comparacion, en este momento me encuentro realizando un trabajo con respecto a este tema.

    Es muy claro!!!

  6. 6 Corina junio 27, 2009 a las 12:55 am

    Hola, esta muy interezante todo, pero quisiera que me dieran un ejemplo en el que pudiera utilizar una pila y una cola hablando de algun sistema o algo asi cuando se puede utilizar, para que me sirve,etc, por que si se entiende la explicacion pero cuando la voy a utilizr….espero su mas pronta respuesta

  7. 7 fanny julio 20, 2009 a las 9:27 pm

    buenas tardes necesito que me digas cuales son las ventajas y desventajas de la estructura de datos cola? es urgente lo necesito para mañana en la mañana… agradezco tu respuesta!!!

  8. 8 Antonio enero 12, 2010 a las 6:50 pm

    Muy buena la explicacion, No saben de algun sitio o algun libro donde se hagan explicaciones de programacion asi (basadas en el mundo real).

  9. 9 Maria febrero 12, 2010 a las 1:07 am

    Muchas gracias tu ejemplo me ha aclarado muchas dudas.

  10. 10 Camilo Hernandez mayo 30, 2011 a las 12:41 am

    ¡Excelente explicación!


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s





A %d blogueros les gusta esto: