Tablas Hash

Antes de que comencemos, démonos unos minutos para ver hasta donde hemos llegado:

Arrays

array-2

Ventajas

  • Nos permiten guardar información de un mismo tipo de dato
  • La guardan de manera contigua (osea junta, una al lado de la otra) en memoria.
  • Gracias a lo anterior podemos acceder a cualquier posición que queramos mediante un simple paso, en un tiempo constante sin importar si el el primero o el décimo elemento.

Desventajas

  • No es dinámico, es decir debemos especificar su tamaño cuando lo declaramos
  • Por lo tanto, es muy muy difícil y tardado añadir o quitar elementos (es más ni siquiera es seguro que haya mas espacio libre contiguo en memoria para añadir más elementos)

Listas Enlazadas

lista-enlazad

Ventajas

  • Son super fáciles de hacer crecer pues sus elementos NO son contiguos en memoria.

Desventajas

  • Ya NO toma lo mismo acceder a un elemento cualquiera, pues tendremos que recorrer TODA la lista comparando uno por uno. Es más podemos decir que el tiempo de búsqueda en el peor caso es O(n)

Entonces:

¿Qué pasa si quiero algo que sea mucho más rápido para localizar elementos y que al mismo tiempo sea mucho más fácil de hacerlo crecer si es necesario?

Pues justo para eso se inventaron las:


Tablas Hash

“Heredero de las listas enlazadas e hijo de la reina array”

Usando una definición de libro: Las Tablas Hash son estructuras de datos que se utilizan para almacenar un número elevado de datos sobre los que se necesitan operaciones de búsqueda e inserción muy eficientes.

En palabras simples una Tabla Hash es solo la unión de un array y un función que llamamos Función Hash.

parteshas

Partes de una Lista Hash

Podemos entonces decir que una Tabla Hash se forma por 3 elementos:

  • Una tabla de un tamaño razonable para almacenar los pares (clave, valor).

  • Una función “hash” que recibe la clave y devuelve un índice para acceder a una posición de la tabla.

  • Un procedimiento para tratar los casos en los que la función anterior devuelve el mismo índice para dos claves distintas. Esta situación se conoce con el nombre de colisión.

…¿Qué demonios? ¿Cómo lo hace?

Una Tabla Hash almacena un conjunto de pares “(clave, valor)”.

  • Dato/Clave/Key: Es el parámetro de entrada, es el “dato que queremos guardar”
  • Valor/Indice/HashValue/Code: Es un número, un entero positivo si nos ponemos exquisitos que nos indica donde debemos guardar nuestro “dato” o “clave” dentro de la tabla.

has2

 

Es decir, es casi como hacer que nuestra información nos diga donde debería ir, en vez e ordenarla nosotros mismos.

El único problema que existe con esta estructura es que es HORRIBLE para ordenar información, son simplemente horribles.

Así que: USALA CUANDO NO TE IMPORTE SI LA INFORMACIÓN SE GUARDA DE MANERA ORDENADA.


Función Hash

Esto es la clave, la Función Hash es la clave de toda la magia, porque nos indica donde hay que guardar nuestro dato y también donde es que debemos buscarlo si es que queremos alguna vez.

Esta función SIEMPRE regresa lo mismo: Un entero positivo. Usaremos ese número que nos regresa para saber en que índice de un array vamos a guardar la información

Debido a esto es muy importante que esta se comporte de manera consistente.

¿Qué necesito para que mi Función Hash sea asombrosa?

rainbowmeme

Pero mira esa función papu

Hay muchas cosas, pero nos vamos a enfocar en varios puntos claves, es decir tu función debe ser:

  • Tiene que minimizar las posibilidades de que ocurra una colisión como de lugar.
  • Usará TODA la información que sea proporcionada para maxilar la cantidad de códigos hash.
  • Es determinista, es decir, si le das una entrada x, siempre, siempre tendrá que regresarte el mismo número como resultado.
  • Distribuya los valores de manera equitativa (osea que cosas como “gatos” y  “gata” acaben en lugares muy muy diferentes de la tabla).
  • Repite, tiene que ser capaz de generar indices muy diferentes para datos muy parecidos.
  • Usa una función “sencilla” no hagas 50,000 operaciones para generar cada indice o todo el tiempo de ejecución te la pasarás haciendo eso.

Ahora, dicho esto, hay muchísimas muchísimas buenas función en internet y deberías usar eso a tu favor, escribir una de estas funciones es más un arte.

hash

El Tamaño de la Tabla

El tamaño de una tabla hash es el otro parámetro que debe ser ajustado con cierto cuidado.

Por ejemplo, si el tamaño es demasiado pequeño, digamos 1, de nuevo la tabla se comporta como una lista encadenada.

En cambio, si el tamaño es enorme, el malgasto de memoria es evidente, puesto que habrá un elevado número de posiciones cuya lista de colisiones está vacía.


Colisiones

Antes de hablar de operaciones veamos un último problema con las Tablas Hash, las colisiones, como te has dado cuenta insertar es una operación bastante simple, pero hay un grave problema.. ¿Qué pasa si la clave Hash me da el mismo resultado para dos datos diferentes que quiero guardar?

Por ejemplo si queremos ordenar palabras basados en su primera letra:

Pues hay dos formas de lidear con esto:

Team Linear Probing

Esta solución le vale un comino la vida y si respuesta es simple: Si esta ocupado ese lugar simplemente busca el más próximo que este libre.

lineal

La solución #1

Y esta forma de pensar lleva un problema, y es que empieza a pasar que si mandar ahora tu dato a ese lugar “disponible cerca” ..¿Qué pasará cuando queramos meter el valor que si que debería estar en ese lugar que acabamos de ocupar?

La Respuesta: Otra colisión. Este problema se conoce como “clustering” y esta es principalmente la razón por la cual no usamos este método. Solo trae más problemas.

Y lo peor es que hace que ahora para buscar elementos volvamos a un caso de O(n), es decir todo nuestro trabajo NO valió para nada. :`(

Pero no se preocupen, hay otra solución…

Team Separate Chaining

Esta solución propone lo que veíamos al principio…¿Recuerdas las listas enlazadas?…¿Cuál era su mayor ventaja?

Este team propone que el array donde guardemos la información no sea mas que un array de punteros hacia listas enlazadas…¡Y esa es una solución cojonuda!

Soluciona todos nuestros problemas y hace que nuestra estructura se vea más o menos así:

tabla

¿Ven? ¡Parece una Tabla! Por eso la llaman Tabla Hash

Fíjate que diferentes posiciones de la tabla pueden tener listas de diferente longitud, o incluso vacías.

Dada una clave, el proceso de búsqueda consiste en calcular primero su índice mediante la función de hash, y a continuación buscar esa clave en la lista de colisiones.

hash table.png

Ejemplo de una Hash Table usando Listas

Con esto se logra que el nuevo peor caso posible sea O(n/k)…Y si, a nivel de “complejidad” es lo mismo, pero en el mundo real esa k si que vale, pues si k= 100 por ejemplo hará que programa se ejecute 100 veces más rápido. ¡A eso yo llamo eficiencia! 

btn1 btn
btn

Arboles 3: La Venganza de los Árboles B

Ok, estamos ya en la última parte de árboles, esto si que ha estado siendo pesado, pero no te preocupes ya casi terminamos, así que veamos…

¿Qué hay más allá de los BTS?

Árboles K-arios

A veces lo llaman m-ario o n-ario.

“Un árbol k-ario es todo aquel árbol que tiene grado k, es decir que cada nodo tiene  máximo k hijos”

 

 


Árboles B

“Como los binarios, pero mejorados..(y más difíciles)”

Pero, ¿Porqué existe? ¿Qué no un BTS es lo más eficiente de todo el mundo?

Si, la respuesta es sí, pero el problema es que no vivimos en el mundo perfecto y debido a esto es imposible usar siempre BTS sobretodo por un grave problema, son muchos hijos, eso quiere decir que tendré que buscar varias veces en un lugar muy feo… El disco duro.

hdvsram

Mira, te explico el problema, los discos de almacenamiento son lentos..como que muy lentos, así que un BTS no termina siendo la mejor opción, necesitamos algo parecido pero con más hijos, y ahí están, te presento los Árboles B:

¿Cómo se forma un Árbol B?

Nodo o Páginas

Un nodo en un Árbol B es bastante raro déjame te lo muestro y luego me explico:

CADA Nodo de un Árbol B tiene:

  • K Datos o Claves guardados en el Nodo
  • K+1 Hijos máximo (también se usa la C) (Recuerda que esto es el grado)
b.png

Nodo de un Árbol B

Ok, ok, como te has dado cuenta esto ya no se ve sencillo, me explico ahora si:

  • Todas las claves o datos del nodo deben estar ordenados, osea:

K1 < K2 < K3

  • Entre cada Dato hay un puntero a un hijo, ese hijo tiene que tener datos que son mayores que los datos que están a la izquierda pero datos menos que el dato que esta a la derecha.

 

Se ve mejor con una imagen:

b-2

Los hijos tienen valores entre K1 y K2

 

Cosas Importantes:

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO M/2 de hijos. (Excepto de la raíz)

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO (M-1)/2 claves. (Excepto de la raíz)

m.png

 

btn1 btn
btn

 

 

Arboles II: El Ataque de los BST

Nota: Esta lección se lee mejor con palomitas a la mano y el código completo de BTS

*Dale click a las palomitas para ir al Código*palomitas


…Bienvenidos a a segunda parte de Árboles, es de lo más útil que nos encontraremos pero ¿Qué demonios son?

BTS: Binary Search Tree, osea que es un árbol binario de búsqueda (ósea que esta ordenado)…Si, eso es todo, así de simple un árbol binario ordenado.Punto”

bst-2

Ejemplo de BTS

Digo que un árbol esta “ordenado” cuando tengo un nodo (lo llamamos nodoRaiz) tal que para cualquier nodo que elija se tienen que cumplirse que:

  1. El hijo izquierdo de nodoRaiz (si es que hay) debe ser menor
  2. El hijo derecho de nodoRaiz (si es que hay) debe de ser mayor.

Esta regla se debe de cumplir para TODOS los nodos del árbol.

Para verificarlo basta con que miremos de izquierda a derecha el árbol y veamos is los elementos van de menor a mayor:

bts

BTS

¿Y que vamos a buscar?

De igual manera que con los arboles normales ls BTS guardan su información en nodos, pero más bien la forma de encontrarlos va a ser por comparación, sea de números, ID o por orden alfabético o un método se te ocurra.


Operaciones

Veamos las operaciones que podemos hacer con un BST:

Búsqueda

busqueda

Ejemplo de Búsqueda

Se usa principalmente para dos operaciones derivadas:

  • Una función que se llama Existe que busca si existe un elemento.
  • Una función que se llama ObtenerElemento que regresa un objeto cuyo identificador sea igual al que pedimos.
  • Una función que se llama EliminarElemento que ..bueno, elimina un elemento (que primero hay que encontrar)

Algoritmo

  1. ¿Es el nodo donde estas ahora el que buscas?, si es así regresa el valor, sino:
  2. ¿Es menor? Ve a la rama izquierda
  3. ¿Es mayor? Ve a la rama derecha
  4. ¿Es una hoja? …No existe

Insertar Elemento

Aquí lo primero es preguntarnos si nuestro árbol va a permitir elementos duplicados, sino también (recomendable) hay que tener eso en cuenta.

Recuerda, siempre se inserta en las hojas.

insertar.gif

Insertar

Algoritmo

  1. Si esta vacío va a la raíz
  2. Si donde estamos es igual al elemento a añadir hay que ver que onda con los duplicados
  3. Si es menor que el elemento actual recursivamente inserta en la rama derecha
  4. Si es mayor que el elemento actual recursivamente inserta en la rama izquierda
  5. Si llegamos a una hoja, le haremos un hijo y pondremos el dato ahí

 

 


Eliminar Elementos

Ok, ok, no te alarmes, pero esta puede que sea la operación más difícil de todas (pero ni tanto) 

Pero es que hay varias “formas”de hacerlo dependiendo del número de hijos que tengas, así que vamos con el algoritmo:

Algoritmo:

Como podemos dividir esto en 3 casos, hoy a explicarlo como 3 casos diferentes pero recuerda que todos están unidos:

Caso 1: Si eres un nodo hoja has que tu padre apunte a NULL y borralo, tan simple.

Caso 2: Si tienes un hijo entonces has que tu padre apunte a tu hijo y borralo, tan simple.

Caso 3: Si tienes 2 hijos (aquí esta lo feo) … Así que habrá que hacer dos caminos 3A y 3B desde aquí, pero antes explicaré que vamos a hacer:

..Espera, creo que me he perdido en esa última parte ¿Como que 3A y 3B?

Lo que pasa es que no hay “una forma correcta” de eliminar un nodo con dos hijos ya que a fuerzas hay que cambiar la estructura del árbol para que no perdamos información.

Así que ahora hay que pensar: ¿Qué vamos a poner en donde esta el nodo que vamos a eliminar? ¡Pues muy fácil!, mira este árbol binario, quizá con dibujos sea más fácil:

bst

Aquí un BTS con sus elementos ordenados

Ahora, ¿recuerdas que podemos hacer barras verticales de manera que solo toquen a un nodo?..y eso hace que sea más obvio que esta ordenado:

bts

Perdonen calidad de GIF

Bueno digamos que quiero eliminar el 23, ¿Qué hago?

Pues nuestro objetivo es eliminarlo pero haciendo cuanto menos desastre mejor, así que habrá que elegir en un valor que este muy próximo a 23, mira, aquí esta una lista de cuanto vale cada nodo de forma ordenada:

05,12,21,23,26,53…

Bueno, en realidad solo nos importan los valores próximos a 23:

05,12,21,23,26,53…

Bueno tenemos dos candidatos: O el 21 o el 26, ahora bien: ¿Cuál?

La respuesta es que no tengo ni idea, quizá dependiendo de como este tu árbol te convenga más usar uno u el otro, quizá te de lo mismo, quizá uno sea la raíz de un árbol enorme que no te conviene reajustar, la verdad es que depende, así que te dejo a que tu eligas como quieras (con una función tuya o al azar o siempre poniendo siempre el mismo-el de la derecha o el de la izquierda- o lo que tu quieras) .

…Pongamos otro ejemplo, ahora con la raíz, el 53, si quisiéramos eliminarlo tenemos dos opciones.

BSTs.png

¡Es por eso que esto es tan difícil, porque no hay un camino “correcto” pero bueno, explicado este texto enorme continuamos…Ya elegimos uno pero ¿Ahora qué?

Camino 3A(Queremos que en donde estaba nuestro nodo este algo más grande):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol derecho el que tenga el valor mínimo (o dicho de otra forma el que este más a la izquierda)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

Camino 3B(Queremos que en donde estaba nuestro nodo este algo más pequeño):

  1. Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol izquierdo  el que tenga el valor máximo (o dicho de otra forma el que este más a la derecha)
  2. Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

 

 

 

 

 


AVL: La versión Pro

Un Árbol AVL es un BTS muy especial, en el que además que todas las cosas que ya conocemos le agregamos algo mas… Es que se auto balancea.

Decimos que un BTS es un AVL si que la diferencia entre la profundidad de dos nodos cuales quiera no puede ser mas de uno.

AVL

 

 


Rotaciones

 

Hay muchas versiones de las rotaciones, muchos nombre, así que haré mi mejor esfuerzo para mostrarles todas las versiones que hay de las mismas:

La Super Pro

Con estas rotaciones podemos sacar todas las que necesitamos:

SuperRotaciones.png

Las Rotaciones Pro

 

Ahora veamos las Comunes y como las podemos representar usando las que creamos arriba:

Right-Right Rotation (Rotación Derecha)

También la llaman simplemente Right Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (X y sus hijos son T1 arriba)

 

RightRotation.png

La Clásica Rotación Derecha

Left-Left Rotation (Rotación Izquierda)

También la llaman simplemente Left Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (Z y sus hijos son T3 arriba)

 

LeftRotation.png

La Clásica Rotación Izquierda

 

 

Right-Left Rotation (Rotación Derecha-Izquierda)

Logramos esto de manera completa así:

RightLeftRotation.png

La Compleja Derecha Izquierda

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Derecha en Hijo derecho de la Raíz
  2. Después has una rotación a la Izquierda en la Raíz

Veámoslo en acción:

 

RightLeftRotationPart1.png

Paso 1: Rotación Derecha en Z

RightLeftRotationPart2.png

Paso 2: Rotación Izquierda en X

Left-Right Rotation (Rotación Izquierda-Derecha)

Logramos esto de manera completa así:

LeftRightRotation.png

La Compleja Izquierda-Derecha

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Izquierda en Hijo Izquierdo de la mañana
  2. Después has una rotación a la Derecha en la Raíz

Veámoslo en acción:

LeftRightRotationPart1.png

Paso 1: Rotación Izquierda en X

LeftRightRotationPart2.png

Paso 2: Rotación Derecha en Z

 

 

 

 

btn1 btn
btn

Árboles I: La Amenaza Fantasma

…Sabia que algún dia iba a ocupar los grafos. ¡Lo sabía!

g53Los arboles son casi casi crear un grafo en una computadora, así que antes que nada tengo algo que decirte:

Esta lección no la empezaré desde cero, pues voy a suponer que ya sabes que son los grafos, al menos lo básico, así que ve y revisa esta lección primero:

MD: ¿Qué son los Grafos?

Ok, con esto fuera del camino es hora de que empecemos:

Árboles

 

arbolEstas son esencialmente diferentes a las listas y todas sus parientes. Esta estructura no es lineal (Osea que puede haber nodos que apunten a más de un elemento).

Estos son básicamente estructuras para guardar información en una jerarquía, son utilizadas en las bases de datos o para hacer un árbol de carpetas dentro de una computadora.

Al principio se parecen, volveremos a crear un nodo como antes:


Nodos

Vamos a meter cada información que queramos guardar en la pila en un nodo, esto es un nodo:

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar. Puede ser de cualquier tipo.
  2. Enlaces:Los arboles son como listas, pero tienen nodos, con s, son varios.

arbol


¿Qué es un árbol?

Así una árbol no es más que esto, un montón de nodos unidos. (Hasta se ve sencillo si lo ves así). En Matemáticas Un árbol es un grafo que:

  • Es dirigido (Osea en enlace en el nodo tiene un “origen y una dirección”).
  • Es conexo (Eso quiere decir que no existen nodos “perdidos” o inaccesibles desde la raíz, es decir que en un árbol puedo llegar  a cualquier nodo desde la raíz).
  • Todos los vértices tienen grado de entrada 1 excepto  un vértice (Eso quiere decir que en “español” que cualquier nodo tiene un solo padre, y que solo es posible llegar a ese nodo a través de ese padre; PD: Ese que no tiene grado de entrada se llama raíz).
  • No puedes tener ciclos: Ósea regresar a un nodo si ya habías pasado por ahí

Así que veámoslo gráficamente:

  • Raíz: Es el nodo al que no es apuntado por nada, es el origen del árbol…digo, por algo se llama raíz.
  • Hoja: Es la punta del árbol, no apuntan a nada, no tienen hijos.
raiz-hoja

Raiz- Hoja

padreshijos

Padres e Hijos

Nivel: Es el numero de “saltos” que tengo que hacer para llegar a el nodo indicado.

nivel-arbol

Nivel de un árbol

Podemos finalmente hablar de un último concepto:

Orden: Orden es el número MAXIMO de hijos que puede tener un nodo.


Árboles Binarios

g53.pngLos árboles binarios son mis favoritos, son muy my poderosos, pero ¿Porque me deberían de interesar?

El tema de localizar elemento es muy interesante porque son lo que se utiliza en cosas como las bases de datos, pues con su estructura son capaces de encontrar lo que nosotros le pidamos demasiado rápido.

¿No me crees?

Imagínate un montón de nombres, por ejemplo en una guía telefónica o una base de datos, si fuera un árbol binario (BTS) por ejemplo podría encontrar cualquier elemento de una base tan grande como una de 32,000 nombres en menos de 15 comparaciones. Si, 15 pasos y puedo encontrar a más de 32,000 personas, con 30 comparaciones puedo encontrar hasta 1,073,741,824 nombres. ¡Asombroso! …Pero ¿Cómo lo hacen?

¡Ya lo veremos!

Pero bueno, sigamos, sus características son sencillas:

  • Tienes Orden 2 ó máximo 2 hijos, como ustedes quieran verlo.
  • Se distingue entre hijo derecho o izquierdo

 

 


Tipos de Árboles

 

Full Binary Tree

Todos los nodos o son hojas o tienen 2 hijos. Esa es la única condición.

output_Y95Fjl

Complete Binary Tree

Si ignoras el último nivel es un Perfect Tree. Si hay UN solo hijo en el ultimo nivel tiene que irse llenando de IZQUIERDA A DERECHA

Complete

Perfect Tree

Es un árbol en el que todos sus nodos o tienen dos hijos o sin hojas y que esta completo INCLUYENDO el último nivel, son preciosos.

perfect

Conceptos:

  • Un Árbol es degenerado si solo tiene un hijo.

Así que bueno, con esto terminamos por hoy, si, se que es mucho, imagínate a mi inocente cuando pensé que podía meter todo lo de Árboles en una lección. Inocente yo.

btn1 btn
btn

Listas Enlazadas

 

Lista Enlazadas Simples

Ok, empecemos por esta que es la más sencilla, aquí la definición: “Es un grupo de elementos en forma de secuencia”

Y antes de que me lo digas, si se que parece que estoy diciendo array de manera fancy y si, son casi iguales.

La lista enlazada nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber “a priori” los elementos que puede contener.


¿Cómo creamos una lista como concepto?

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

 

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la lista en un nodo, esto es un nodo:

listas-4

Partes de un Nodo

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Lista

Ahora podemos dar hasta una mejor definición de lista: Un montón de nodos.

 

Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero. La asignación de memoria es hecha durante la ejecución.

En una lista los elementos son contiguos en lo que concierne al enlazado. En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero. En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento tiene que apuntar hacia NULL (el fin de la lista). 


Partes de la Lista

Claro que no pudieron parar ahí así que les pusieron nombres raros a sus partes:

Cabeza

Es el nodo principal y es el único que necesitamos para acceder a la lista y empezar a trabajar, pues simplemente vamos accediendo de enlace a enlace hasta llegar a donde queramos.

listas-7.png

Y a todo lo que no es cabeza le llamamos cola:

listas-8.png

Y así podemos irnos al infinito porque las colas son listas, que tienen una cabeza y así:

listas-9.png


Ventajas

Una vez que ya aprendimos que son las listas, nos preguntamos ¿porque usarlas?

  • Los nodos no tienen porque estar contiguos en memoria, gracias a esto evitar problemas al trabajar con gran cantidad de datos.
  • Pueden tener longitud variable
  • Podemos agregar o quitar elementos en tiempo de ejecucción.

Pero como en la vida también tienen cosas negativas:

  • No tienen un indice, por lo que no podemos entrar a cualquier nodo así como así
  • Necesitan más espacio en memoria, pues guardo el dato y el enlace.

 

 


Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

codigo

 

 

 

 

btn1 btn
btn

Colas

peach

Tenia que ponerlo

Ok, antes de que hagan un chiste lo haré yo, una cola es el nombre más ridículo, perfecto y divertido para una estructura de datos.

Pero bueno, vamos a ponernos serios, las colas son estructuras de datos que almacenan datos de un mismo tipo, pero lo hacen de una manera muy especial.

Tienen un nombre que muchas veces ocupan en los libros de computación, las llaman estructuras FIFO (First In First Out) o en español: “Lo primero que entra es la primero que sale”.

Una cola es de verdad un buen nombre porque la estructura funciona igual que en la vida real, pues siguen sus dos principios básicos:

  • Al llegar a una cola tu siempre vas al final
  • Siempre se atiende al primero y así sucesivamente

Así que para hacer nuestra cola, haremos algo parecido a una lista, es más, haremos algo muy parecido y más simple.

(Si no sabes que es una lista no te preocupes, no es necesario, pero te puedo adelantar que son como colas con esteroides, capaces de hacer lo mismo que te enseñare ahora y más, así que quizá te guste echarles un vistazo después, solo digo: Lección de Listas Enlazadas).

Colas.png


¿Cómo creamos una Cola como concepto?

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la cola en un nodo, esto es un nodo:

El nodo tiene dos partes:

listas-4

Partes del Nodo

  1. Dato: Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la cola; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Así una cola no es más que esto, un montón de nodos unidos.

pilas-dibujos

Diagrama de una Cola

Y si, no son mas que una versión “de prueba” de una lista enlazada, estas estructuras las puedes revisar aquí.

 


Funciones Básicas de una Cola

ENQUEUE: Encolar

Es básicamente introducir algo en la cola, ósea añadir un elemento al final de la estructura

colas

 

UNQUEUE: Procesar una Cola

Esta operación se puede dividir en dos operaciones independientes:

procesarcola



Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

Esta parte sera algo, algo MUY largo, así que te recomiendo que veas el código completo y original que tengo en Github. Da click en el botón:

Codigo.png

 

 

Y ya esta, como te das cuenta estas estructuras sirven un propósito muy específico, así que espero que ya haya gustado esta lección.

Ahora si, estas listo para ver las listas enlazadas, esto se va a poner bueno.

 

 

btn1 btn
btn

Pilas

pilasLas pilas, son todo un clásico porque no son la forma mas tradicional de agrupar datos, pero una vez que las comprendes veras que son muy muy útiles.

Tienen un nombre que muchas veces ocupan en los libros de computación, las llaman estructuras LIFO (Last In First Out) o en español: “Lo último que entra es la primero que sale”.

Una pila es de verdad un buen nombre porque la estructura funciona igual que en la vida real, pues siguen sus dos principios básicos:

  • Al llegar a una pila tu siempre vas al final
  • Siempre se atiende al último y así sucesivamente

Así que para hacer nuestra pila, haremos algo parecido a una lista, es más, haremos algo muy parecido y más simple.

(Si no sabes que es una lista no te preocupes, no es necesario, pero te puedo adelantar que son como pilas con esteroides, capaces de hacer lo mismo que te enseñare ahora y más, así que quizá te guste echarles un vistazo después, solo digo: Lección de Listas Enlazadas).

¿Cómo que se procesa el último?

– Si, se que parece algo muy estúpido, ¿para que haría eso?

– Pues no te preocupes, te explicaré con varios ejemplos donde son útiles las pilas:

Ejemplo #1: Bolsas de Dinero

Imagínate que eres rico trabajando de programador (que divertido ¿verdad?), entonces tienes un montón de dinero que tienes que guardar, así que lo ordenas en un pila.

Entonces como los ordenaste en una pila cuando te llega tu nuevo pago del mes lo metes en la pila. Y luego cuando quieres sacar algo de tus pequeños ahorros para comprarte a última Mac, entonces sacas LA ÚLTIMA BOLSA.

pila.gif

Una pila…y mucho dinero

Ejemplo #2: Simplificar una expresión

expresion

Como puedes ver hay muchas situaciones donde una pila puede ser una herramienta muy útil para organizar información, pero bueno, es hora de ponernos a trabajar ¿Cómo las creamos?


¿Cómo creamos una Pila como concepto?

 

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la pila en un nodo, esto es un nodo:

El nodo tiene dos partes:

  1. Dato: Representa el dato a almacenar. Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
  2. Enlace: Es un puntero al siguiente elemento de la pila; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.
listas-4

Partes de un Nodo

Así una pila no es más que esto, un montón de nodos unidos.

pila

Y si, no son mas que una versión “de prueba” de una lista enlazada, estas estructuras las puedes revisar aquí.

 


Funciones Básicas de una Pila

Bueno, listo estas funciones podemos ahora si ver las dos que controlan una lista:

PUSH: Apilar en la Pila

Es básicamente introducir algo en la pila, ósea podemos verlo como añadir algo al principio de la lista:

apilar

POP: Procesar una Pila

Vamos a trabajar con un elemento, procesarlo y eliminarlo, y lo vamos a hacer en el mismo sentido que en el que apilamos (en listas esto sería equivalente a eliminar el primer elemento). Esta operación se puede dividir en dos operaciones independientes:

desapilar

PEEK: Consulta la Cabeza

Nos regresa, sin eliminar nada la cabeza de nuestra pila, esto s puede lograr usando un POP, y después un PUSH .


Implementación con Array

Hay otra manera, si entendiste la de arriba, esta es mucho más sencilla, vamos a usar arrays y punteros, verás que cool es:

Y es que las pilas en inglés se llaman Stack, así que vamos a usar un “Stack pointer” para convertir nuestro array en una pila:

Aquí esta la primera función:

stack

Como ven nuestro puntero va posicionándose en un lugar libre y lo va llenando..cuando el puntero apunta fuera de nuestro “stack” decimos que paso un “stack overflow”.

stack

La segunda operación es también muy fácil de visualizar, mira:

array

 

 

 


Zona Dos: Código Real

Ok, ok, todo muy bonito hasta aquí, pero ahora es hora de ponernos a trabajar.

Esta parte sera algo, algo MUY largo, así que te recomiendo que veas el código completo y original que tengo en Github. Da click en el botón:

Codigo.png

 

 

 

 

 

 

btn1 btn
btn