En esta nueva entrega de Code Time continuamos con los temas que todo desarrollador de software debe de saber a la hora de crear un programa y en esta ocasión la temática se centró en algunas estructuras de datos dinámicas basadas en los tipos abstractos de datos Pila, Cola y Diccionario.
Repasando un poco las estructuras de datos, vimos que podían clasificarse en estáticas y dinámicas. En las primeras el tamaño de las mismas es fijado durante su creación mientras que las segundas permiten inicializarse con un tamaño y modificar este durante la ejecución. Al igual que en episodio anterior nos enfocamos en las estructuras dinámicas.
Anteriormente vimos las listas que permiten almacenar información de manera secuencial y los árboles que, en cambio, mantienen los datos jerárquicamente.
Pilas o Stacks
Son un tipo abstracto de dato que lleva una colección de datos ordenada de manera LIFO (Last In, First Out – Último Entrado, Primero Salido). Al igual que las listas mantienen un orden lineal pero con la peculiaridad de que no se puede acceder a ningun elemento salvo al último elemento agregado.
Una analogía simple a este TAD es una pila de platos. A la hora de extraer un plato tomamos el que está en la parte superior siendo este el último en haber sido apilado.
Entre las operaciones que las pilas permiten tenemos:
- Insertar elemento o push
- Extraer elemento o pop
- Observar proximo elemento a extraer o top
- Verificar si la pila está vacía o isEmpty
Para implementar este tipo en una estructura de dato podemos utilizar las listas teniendo solo que utilizar las funciones que estas proveen para definir la de las pilas.
Colas o Queues
Es un tipo de dato secuencial que lleva una colección de datos ordenada bajo el orden FIFO (First In, First Out – Primero Entrado, Primero Salido).
Para poder entender mejor este tipo es mejor verlo con un ejemplo como ser la cola de un supermercado. La primera persona en ser atendida es la primera en haberse formado. Las colas son muy utilizadas por ejemplo a la hora de atender solicitudes de clientes en servidores, colas de procesamiento de archivos, etc.
Entre las operaciones que las colas permiten tenemos:
- Insertar un elemento al final o enqueue
- Observar el elemento al principio o front
- Quitar el primer elemento o dequeue
- Verificar si la cola está vacía o isEmpty
Al igual que en el caso de las pilas, las colas pueden implementarse utilizando listas
Diccionarios
Como recordamos, los arreglos son una forma secuencial de almacenar información que puede ser accedida mediante un índice. Esta implementación no solo es rígida con respecto al tamaño sino que fuerza a conocer el índice a utilizar. Los diccionarios brindan mucha más flexibilidad ya que funcionan como arreglos dinámicos asociativos, es decir, se puede utilizar otro tipo de dato en lugar de un entero. A esta asociación se la conoce como clave-valor (key,value) siendo el valor asociado a la llave. Un claro ejemplo de esto es una agenda telefónica donde a cada nombre se le asocia un número, en este caso los números de teléfono (valores) se acceden mediante el propietario(clave).
Posibles implementaciones
Uno de los primeros acercamientos sería mantener dos arreglos. Uno con las claves y otro con los valores. Para acceder a un valor habría que recorrer el arreglo de claves y una vez encontrada la coincidencia se utilizaría el índice asociado para obtener el valor. La desventaja de este modelo es que podría requerirse recorrer todo el arreglo para realizar una búsqueda. Si consideramos un diccionario de 100000 elementos tendríamos que procesar demasiada información lo que conlleva a una pérdida de rendimiento.
Otra forma sería utilizando hashes. Antes que nada hay que ver que es un hash. Una función hash es una función que toma un elemento y retorna otro más simple como ser un entero. Esta tiene que ser fácil de calcular y ser capaz de distribuir equitativamente los resultados. Con esta función lo que se hace es tener un arreglo de valores y cada valor es guardado en el índice que indique la función hash evaluada en la llave.
Esta forma de trabajar a pesar de ser mucho más eficiente que la anterior presenta un inconveniente, ¿que sucede si la función hash en dos llaves distintas vale lo mismo? En ese caso decimos que tenemos una colisión. Para resolverlas tenemos distintos técnicas:
- No hacer nada: simplemente se ignora y se permite que se pisen los valores. Esta es la peor solución, si es que se la puede llamar así
- Encadenado: En lugar de tener un solo valor se tiene una lista por lo que en realidad hay recorrerla pero como es mucho más pequeña no es una tarea de alto costo.
- Fusionado: En lugar de colocarse en el lugar asignado, al estar ya ocupado, se lo coloca en el siguiente libre. Esto a su vez acarrea el problema de que cuando se busca un valor hay trabajar con más cuidado y hay que desarrollar algoritmos capaces de trabajar correctamente con la estructura.
Espero que les haya gustado la nota y el podcast. Nos vemos en la próxima entrega.
Si quieren seguirme pueden hacerlo mediante Spreaker, iTunes e Ivoox y via o Gmail.
