Business Model
Data Structures
Casi todos los lenguajes de programación tienen tipos de datos primitivos como: lógicos (boolean), caracteres y cadenas de texto (Char y String), numéricos (Integer y Float/Decimal), nulos (Null/None)...
Pero, ¿y si quieres almacenar muchos boolean
o muchos strings
en una sola estructura? Por ejemplo: Si tienes una lista de cosas por hacer (string) y quisieras ponerlas juntas en una lista así:
1por_hacer = ['hacer la cama', 'limpiar la casa', 'pagar impuestos']
Para casos como estos, el mundo de la informática ha creado otros tipos de datos más complejos entre los que están las listas. Este grupo es conocido como Estructuras de datos
.
Es una forma de organizar datos que se utilizarán de manera más efectiva en una situación en particular.
Hay muchas estructuras de datos conocidas y también puedes crear las tuyas. Partamos por revisar las más populares:
Tipo | Qué es | Propósito y eficiencia |
---|---|---|
Array o Lista | Es una forma de tener muchos valores o de un mismo tipo en una sola variable | Agrupar valores, relacionarlos entre si, para que sean más accesibles como hemos hecho con la lista anterior. El computador reservará espacios sucesivos en la memoria para todos los valores, para acceder a ellos más rápido |
Matrix o Matriz | Es un array de dos(o más) dimensiones en donde accedes a los elementos usando dos posiciones así:print(matrix[0][1]) | Las matrices son ideales para las coordenadas; puedes hacer un gráfico cartesiano con facilidad |
Stack o Pila | Stack es una estructura de datos lineal, es como un Array pero con dos métodos adicionales: stack.pop() que elimina el último elemento y stack.push() que añade un elemento al final. orden LIFO(Last In First Out o último en entrar primero en salir)/FILO(First In Last Out o primero en entrar último en salir). | Como es lineal, es muy eficiente en cuanto a memoria porque el computador solo escribe en los bordes de la estructura |
Queue o cola | La queue o cola es como el stack pero puede obtener el elemento en la primera posición: FIFO(First in First Out o primero en entrar primero en salir) | Es un poco menos eficiente que el stack, pero es bastante rápido y utilizado en muchos escenarios de la vida real |
Hash Table o tabla hash | La tabla hash es como un array pero puedes usar letras para identificar las posiciones en la lista. Por ej. print(person["name"]) . En Python le llamamos Diccionarios en Javascript objetos literales. | Al poder acceder a los elemnetos usando un string como key es ideal para algunas situaciones. Por ejemplo: podríamos tener una estructura para cada idioma e imprimir ambos idiomas así:print(german["Hello World"]) y print(spanish["Hello World"]) |
Graph o grafos | Los grafos son una estructura de datos en la cual cualquier elemento (llamado node) puede apuntar hacia cualquier otro node. Puedes usar grafos para representar jerarquías, calles de una ciudad, etc. | Los grafos son muy eficientes porque te permiten apuntar directamente a otros nodes en vez de tener que hacerle un bucle a una secuencia, por ejemplo Google Maps Traffic usa graphs para calcular la hora estimada de llegada |
Tree o árbol | Trees son un tipo de grafos con jerarquía (padres e hijos), todo empieza en el node superior y puedes usar node.childs() para obtener los hijos de cualquier elemento y seguir profundizando en la jerarquía. Los trees son eficientes en muchas jerarquías de la vida real en nuestro presente como por ej: representar a una familia, el directorio de archivos de un computador, el menu de un sitio web, etc. |
☝️ Hay otros tipos de estructuras de datos y también puedes crear tus propias estructuras pero abordamos estos casos porque representan la gran mayoría de las situaciones de la vida real que encontrarás mientras programas.
Cada lenguaje de programación tiene una implementación de array diferente pero la idea más básica y original era tener una forma eficiente de bajo nivel para almacenar valores relacionados. Los arrays son una forma eficiente de almacenar porque:
Puedes manipular arrays de esta forma en casi cualquier lenguaje de programación:
1# obtener un valor 2primera_tarea = tareas[0] 3 4# restablecer el valor de la 3º posición 5tareas[2] = "comprar comida" 6 7# añade un nuevo valor al final de la lista 8todos.append("Call mom")
Si almacenas arrays dentro de un array obtienes una matriz, por ejemplo:
1# tablero de un juego de gato 2tablero = [ 3 [ 0,0,0 ], 4 [ 0,0,0 ], 5 [ 0,0,0 ] 6]
En el ejemplo anterior replicamos el tablero de un juego de gato usando una matriz (un array de dos dimensiones), si quisieramos restablecer cualquiera de estos valores tendríamos que hacer algo así:
1tablero[0][1] = "x" 2 3# el tablero se vería así: 4tablero = [ 5 [ 0,1,0 ], 6 [ 0,0,0 ], 7 [ 0,0,0 ] 8]
Hay muchas cosas que puedes representar con una matriz: mapas, gráficos cartesianos, planos, etc.
Los stacks son buenos porque también son muy rápidos y eficientes. El stack sigue la regla FILO: primero en entrar, primero en salir
En la vida real hay muchas situaciones que replican un stack:
1my_stack = [] 2 3my_stack.append("A") 4my_stack.append("W") 5my_stack.append("F") 6 7# Si quiero obtener A tendría que usar pop (eliminar desde el final) F y W primero 8 9f = my_stack.pop() # elimina F y lo devuelve 10w = my_stack.pop() # elimina W y lo devuelve 11a = my_stack.pop() # elimina A y lo devuelve 12
Al igual que el stack, queue se usa en escenarios de la vida real:
Una Queue es como un stack pero con comportamiento FIFO: primero en entrar, primero en salir
1my_queue = [] 2 3my_queue.append("A") 4my_queue.append("W") 5my_queue.append("F") 6 7# A será el primero en obtenerse porque fue el primero en entrar 8a = my_queue.pop(0) # saca de la cola a A y lo devuelve 9w = my_queue.pop(0) # saca de la cola a W y lo devuelve 10f = my_queue.pop(0) # saca de la cola a F y lo devuelve
Algunas de las implementaciones más populares de tablas hash son:
1language_hash_table = { 2 "hello world": { 3 "german": "Hallo Welt", 4 "spanish": "Hola Mundo" 5 } 6} 7 8# Ahora podemos obtener cualquier idioma instantáneamente en base al inglés: 9print(language_hash_table["hello world"]["german"]) 10print(language_hash_table["hello world"]["spanish"]) 11
Los grafos son una forma totalmente nueva para almacenar y acceder a datos, ahora en vez de tener un array o una lista en una secuencia, puedes tener elementos que se apunten entre si.
Los graphs o grafos son ideales para representar relaciones, jerarquías y conexiones. Por ejemplo:
Un grafo puede representarse a través de una tabla hash de esta forma:
1graph = { 2 'A': ['B', 'C'], 3 'B': ['C', 'D'], 4 'C': ['D'], 5 'D': ['C'], 6 'E': ['F'], 7 'F': ['C'] 8}
Puedes ver a los árboles como un subtipo de grafos, porque los nodos de los árboles están conectados entre sí, pero el único tipo de conexión que puede existir entre ellos es la relación Padre->Hijo
Los árboles pueden usarse en varias situaciones como:
Un árbol puede representarse usando un grafo de esta manera:
1pequeña_familia = { 2 'A': { 3 "hijos": ['C', 'D'] 4 }, 5 'B': { 6 "hijos": ['C', 'D'] 7 } 8 'C': { 9 "hijos": ['E'] 10 } 11}
Nota: A y B son probablemente cónyuges, C es hijo de A & B y E es hijo de C.