Estructuras de Datos: Pilas, Colas, Listas, Árboles, Grafos y Más

Conceptos Fundamentales de Estructuras de Datos

Este documento explora diversas estructuras de datos y algoritmos comúnmente utilizados en informática y telecomunicaciones.

Pilas (Stacks)

1. Una pila es una lista de elementos en la cual se puede insertar o eliminar elementos solo por uno de sus extremos.
2. Las pilas son estructuras de datos tipo LIFO (Last In, First Out - Último en entrar, primero en salir).
3. Se pueden representar mediante arreglos y listas enlazadas.
4. La operación de insertar un elemento se llama Push.
5. La operación de eliminar un elemento se llama Pop.
6. Las pilas se utilizan en problemas como llamadas a subprogramas, recursión, tratamiento de expresiones aritméticas y ordenación.

Colas (Queues)

7. Una cola es una lista de elementos en la que se introducen elementos por un extremo y se eliminan por el otro.
8. Las colas son estructuras de datos tipo FIFO (First In, First Out - Primero en entrar, primero en salir).
9. La variable que guarda la posición del primer elemento de la cola se llama Frente.
10. La variable que guarda la posición del último elemento de la cola se llama Final.
11. Las operaciones que se pueden realizar en una cola son: Insertar un elemento y Eliminar un elemento.
12. Las colas circulares sirven para hacer un uso más eficiente de la memoria disponible, y además, el elemento anterior al primero es el último.
13. Bicola (Doble Cola): En este tipo de cola, los elementos pueden ser eliminados por cualquiera de los extremos.

Variantes de Doble Cola

14. Doble Cola con Entrada Restringida: Permite que las eliminaciones se realicen por cualquiera de los dos extremos, mientras que las inserciones solo se realizan por el final de la cola.
15. Doble Cola con Salida Restringida: Permite que las inserciones puedan hacerse por cualquiera de los dos extremos, mientras que las eliminaciones solo se realizan por el frente de la cola.

Listas

17. Una lista es una colección de elementos llamados generalmente nodos.
18. El orden de los nodos se establece por medio de punteros.
19. Borrado de un elemento: Consiste en quitar un nodo de la lista redefiniendo las ligas que correspondan.
20. Pasos para el borrado de un elemento:
    • Eliminar el primer nodo.
    • Eliminar el último nodo.
    • Eliminar un nodo con información X.
    • Eliminar el nodo anterior/posterior al nodo con información X.
21. Búsqueda de un elemento: En esta operación se deben recorrer los nodos, tomando el campo liga como puntero al siguiente nodo a visitar.
22. Listas Circulares: Estas listas tienen la característica de que el último elemento de la misma apunta al primero.
23. Listas Doblemente Ligadas: Es una colección de nodos, en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (liga izquierda) y otro a su sucesor (liga derecha).
24. Operaciones que se pueden realizar en las listas doblemente ligadas:
    • Recorrido de la lista.
    • Inserción de un elemento.
    • Borrado de un elemento.
25. Recorrido de la lista: Esta operación se puede hacer tanto del inicio al final, como en sentido inverso de la lista.
26. Inserción de un elemento: Se puede realizar al inicio y final de la lista, o antes/después de un nodo como referencia.
27. Listas Doblemente Ligadas Circulares: En estas listas, el campo de la liga izquierda del primer nodo de la lista apunta al último, y el campo de la liga derecha de este apunta al primero.
28. La principal ventaja de las listas circulares es que permiten la navegación en cualquier sentido a través de la misma y, además, se puede recorrer toda la lista partiendo de cualquier nodo.

Arreglos

30. Un arreglo es una colección finita, homogénea y ordenada de elementos.
31. Arreglo Unidimensional: Es un tipo de datos estructurado que está formado por una colección finita y ordenada de datos del mismo tipo.
32. Arreglos Bidimensionales: Cada elemento está simultáneamente en una fila y una columna.
33. Arreglos Multidimensionales: Son los arreglos con más de dos dimensiones.

Punteros

34. Un puntero es una variable que da referencia a una región de memoria.
35. Puntero de Dirección: Variable que contiene una dirección de memoria.
36. Puntero de Indirección: Variable que regresa el valor almacenado.

Árboles

1. Los árboles son abstracciones matemáticas que juegan un rol central en el diseño y análisis de algoritmos.
2. Árbol: Es un conjunto de vértices y aristas que satisfacen ciertos requisitos.
3. Vértice: Es un objeto simple, también denominado nodo, que contiene información.
4. Arista: Es una conexión entre dos vértices.
5. Camino: Es una lista de vértices distintos, en los que cada uno de ellos se encuentran conectados sucesivamente por aristas en el árbol.
6. Nodo: Es la unidad sobre la que se construye el árbol, y puede tener cero o más nodos hijos conectados a él (por medio de aristas). Esta propiedad se le denomina grado.
7. Un árbol solo puede tener un único nodo sin padres, al cual se le denomina RAIZ.
8. Hoja o Terminal: Es cuando un nodo que no tiene hijos.
9. Rama: Son los nodos que tienen padre y uno o varios hijos.
10. Nivel de un árbol binario: La raíz del árbol tiene el nivel 0, y el nivel de cualquier otro nodo en el árbol es uno más el nivel de su padre.

Recorridos de Árboles

A continuación, se presentan los recorridos de los árboles. El recorrido de cada uno es con respecto al árbol de la parte inferior de la hoja.

• Recorrido Preorden: ABDGCEHIF
  1. Visitar la raíz.
  2. Recorrer el subárbol izquierdo en orden previo.
  3. Recorrer el subárbol derecho en orden previo.
• Recorrido Inorden: DGBAHEICF
  1. Recorrer el subárbol izquierdo en orden simétrico.
  2. Recorrer la raíz.
  3. Recorrer el subárbol derecho en orden simétrico.
• Recorrido Postorden: GDBHIEFCA
  1. Recorrer el subárbol izquierdo en orden posterior.
  2. Recorrer el subárbol derecho en orden posterior.
  3. Recorrer la raíz.

Algoritmos de Ordenación y Búsqueda

Algoritmos de Ordenación

1. Método de Ordenación por Intercambio Directo (Método de la Burbuja): Es el más simple y consiste en comparar dos elementos adyacentes para determinar si se realiza un intercambio entre los mismos, esto en caso de que el primero sea mayor que el segundo (forma ascendente) o el caso de que el primero sea menor que el segundo (forma descendente).
2. Método de Ordenamiento Rápido (Método Quicksort): Es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos en un tiempo proporcional a n² en el peor de los casos o a n log n en el mejor de los casos. El algoritmo original es recursivo, como la técnica en la que se basa.
3. Método de Ordenación Shellsort: Es una versión mejorada del método de ordenación por inserción directa, que se utiliza cuando el número de elementos es grande. Este método recibe su nombre gracias a su creador Donald L. Shell. También se conoce con el nombre de inserción con incrementos decrecientes.
4. Algoritmos de Ordenamiento por Distribución: Ordenan el arreglo tomando cada número e insertándolo en la posición que toma su valor, es decir, si se tiene un cinco, se coloca en la posición cinco del arreglo, "si 10 vales, en esa posición te pongo". Esto indica que no se podrán ordenar los arreglos que tengan valores repetidos y el arreglo necesita el tamaño del número más grande que se encuentre en él.
5. Método de Ordenación Radix: Es un algoritmo que ordena datos procesando sus elementos de forma individual, según la posición que ocupan dentro del dato. Los datos numéricos los ordena por dígitos y los datos alfabéticos por letras.

Tablas Hash

6. Una tabla hash, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que asocia llaves o claves con valores.
7. Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se pueden hacer implementaciones multidimensionales basadas en varias claves.

Grafos

8. Grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia).
9. Los grafos constan de un conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.

Algoritmos de Búsqueda

10. Búsqueda Secuencial: Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final.
11. Búsqueda Binaria: Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.