CP-UPV Bootcamp - Capítulo 7

Capítulo 7: Estructuras de datos

Introducción

En este capítulo, estudiaremos varias estructuras de datos fundamentales para el diseño eficiente de algoritmos. A lo largo del capítulo, revisaremos qué son, cómo se usan, y cómo se implementan.

Contenidos del capítulo:

• Stacks
• Queue
  • BFS (Breadth-First Search)
• LinkedList
• PriorityQueue
• Map
  • HashMap
• Set
• Mención de árboles y grafos

Stacks

Un Stack (pila) es una estructura de datos que sigue el principio LIFO (Last In, First Out), se añaden elementos encima de la pila, y a la hora de quitar elementos se cogen los de encima también. Esto significa que el último elemento que se inserta es el primero en salir, y no se pueden quitar elementos que no estén encima de la pila ni añadir por la mitad.

// Declaración de una pila, debemos especificar el tipo de dato
stack<int> s;

// Insertar elementos en el stack 
s.push(10); 
s.push(20); 
s.push(30); 

// Obtener el tamaño
s.size();
> 3

// Acceso al elemento superior 
cout << s.top() << endl; 
> 30 

// Eliminar el elemento superior 
s.pop(); 
cout << s.top() << endl; 
> 20

// Comprobar si el stack está vacío 
cout << s.empty() << endl; 
> 0

Queue

Una Queue (cola) es una estructura de datos que sigue el principio FIFO (First In, First Out), se añaden elementos al final de la cola y se quitan del principio. Aquí, el primer elemento en entrar es el primero en salir, un elemento no puede insertarse en el medio de la cola o quitarse si no está el primero.

// Declaración de una cola, debemos especificar el tipo de dato 
queue<int> q; 

// Insertar elementos en la cola 
q.push(10); 
q.push(20); 
q.push(30);

// Obtener el tamaño
q.size();
> 3

// Acceso al primer elemento 
cout << q.front() << endl;
> 10

// Eliminar el primer elemento 
q.pop(); 
cout << q.front() << endl; 
> 20 

// Comprobar si la cola está vacía 
cout << q.empty() << endl; 
> 0

BFS (Breadth-First Search)

BFS es un algoritmo de búsqueda que explora los nodos de un grafo o árbol por niveles. Se utiliza una cola para recorrer los nodos de manera uniforme, garantizando que se exploren todos los vecinos de un nodo antes de pasar a los siguientes niveles.

// Función que realiza BFS en un grafo representado como una lista de adyacencia
void BFS(int nodo_ini, const vector<vector<int>> grafo) {
    // Creamos una cola para almacenar los nodos a visitar
    queue<int> q;

    // Vector para guardar los nodos visitados, se inicializa con false (no hay ningún nodo visitado)
    vector<bool> visitado(grafo.size(), false);

    // Marcamos el nodo inicial como visitado y lo añadimos a la cola
    visitado[nodo_ini] = true;
    q.push(nodo_ini);

    // Mientras la cola no esté vacía, seguimos explorando el grafo
    while (!q.empty()) {
    // Extraemos el siguiente nodo de la cola
        int act_node = q.front();
        q.pop();

        // Recorremos todos los nodos vecinos al nodo actual
        for (int vecinos : grafo[nodo_ini]) {
            // Si el nodo adyacente no ha sido visitado, lo marcamos y lo añadimos a la cola
            if (!visitado[vecino]) {
                visitado[vecino] = true;
                q.push(vecino);
            }
        }
    }
}

int main() {
    // Grafo representado como una lista de adyacencia
    vector<vector<int>> grafo = {
        {1, 2}, 	// Nodos adyacentes al nodo 0
        {0, 3},  // Nodos adyacentes al nodo 1
        {0, 4}, // Nodos adyacentes al nodo 2
        {1},  // Nodos adyacentes al nodo 3
        {2},  // Nodos adyacentes al nodo 4
    };

    int nodo_ini = 0; // Nodo desde el cual comenzar BFS

    // Llamamos a la función BFS
    BFS(nodo_ini, grafo);

    return 0;
}

Linked List

Una Linked List o Lista Enlazada es una estructura de datos que consiste en una secuencia de elementos llamados nodos que están conectados. Cada nodo contiene dos partes: un valor o dato (data) y un puntero (pointer) que referencia al siguiente nodo en la secuencia. La principal característica de una Linked List es que los elementos no están almacenados en ubicaciones contiguas en la memoria, lo que permite una fácil inserción y eliminación de elementos.

Tipos de Linked List

• Lista Enlazada Simple (Simple Linked List): Cada nodo apunta solo al siguiente nodo.
• Lista Enlazada Doble (Double Linked List): Cada nodo tiene dos punteros, uno al siguiente nodo y otro al nodo anterior.
• Lista Enlazada Circular (Circular Linked List): En una lista enlazada simple o doble, el último nodo apunta de vuelta al primer nodo, formando un ciclo.

Implementación de una Linked List

// Definición del nodo
struct Node {
    int data;
    Node* next;
};

// Función para insertar un nuevo nodo al principio
void insertAtBeginning(Node** head, int newData) {
    Node* newNode = new Node(); // Crear un nuevo nodo
    newNode->data = newData; // Asignar el dato al nodo
    newNode->next = *head; // Hacer que el nuevo nodo apunte al anterior primer nodo
    *head = newNode; // Cambiar el head para que apunte al nuevo nodo
}
int main() {
    Node* head = nullptr;

    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    // Imprimir la lista
    while (n != nullptr) {
        cout << n->data << " ";
        n = n->next;
    }
    cout << endl;

    return 0;
}

En este ejemplo, se crea una lista enlazada simple que inserta elementos al principio. Se añaden tres elementos (30, 20, 10) y luego se imprimen.

PriorityQueue

Una Priority Queue o Cola de Prioridad es una estructura de datos que funciona similar a una cola normal, pero con la particularidad de que cada elemento tiene una "prioridad". Los elementos se eliminan de la cola basándose en su prioridad, no en el orden en que fueron añadidos. Las colas de prioridad se utilizan en algoritmos como Dijkstra y en sistemas donde se deben procesar tareas según su importancia.

En C++, una Priority Queue se implementa típicamente usando un std::priority_queue, que por defecto es un Max-Heap (el elemento de mayor prioridad es el máximo).

// Crear una Priority Queue (Max-Heap por defecto)
priority_queue<int> pq;

// Insertar elementos en la cola de prioridad
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(5);

// Imprimir y eliminar elementos según su prioridad (el mayor primero)
while (!pq.empty()) {
        cout << pq.top() << “ ”; // Imprime el elemento de mayor prioridad
        pq.pop(); // Elimina el elemento de mayor prioridad
}
> 30 20 10 5

Map

Un Map es una estructura de datos que almacena pares clave-valor, permitiendo acceso, inserción y eliminación eficientes de valores a través de sus claves. En C++ existe la clase map para este propósito, pero es más eficiente la estructura de datos que se muestra a continuación.

Hash Map

Un Hash Map es una implementación de un mapa que utiliza una función hash para convertir la clave en un índice en una tabla donde se almacenan los pares clave-valor.

// Crear un Hash Map que asocia cadenas (keys) con enteros (values)
unordered_map<string, int> hashMap;

// Insertar elementos en el Hash Map
hashMap[“uno”] = 1;
hashMap[“dos”] = 2;
hashMap[“tres”] = 3;

// Acceder a un valor a través de su clave
cout << “El valor asociado a ‘dos’ es: “ << hashMap[“dos”] << endl;
> El valor asociado a ’dos’ es: 2

// Verificar si una clave existe
if (hashMap.find("cuatro") != hashMap.end()) {
    cout << “‘cuatro’ existe en el Hash Map” << endl;
} else {
    cout << “‘cuatro’ no existe en el Hash Map” << endl;
}
> ‘cuatro’ no existe en el Hash Map

// Iterar sobre el Hash Map
for (const auto& pair : hashMap) {
    cout << pair.first << “: “ << pair.second << endl;
}
> uno: 1
> dos: 2
> tres: 3

En este ejemplo, unordered_map y map se pueden usar de la misma manera, pero map tiende a ser menos eficiente en casos más grandes porque map guarda los datos como un árbol binario de búsqueda (operaciones en \(O(\log n)\)) mientras que unordered_map guarda los datos en una tabla (operaciones en \(O(1)\)).

Set

Un Set es una estructura de datos que almacena una colección de elementos únicos, sin ningún orden específico. Los Sets son útiles cuando se necesita asegurarse de que cada elemento aparezca una sola vez en la colección.

// Crear un set de enteros
unordered_set<int> set;

// Insertar elementos en el set
set.insert(10);
set.insert(20);
set.insert(30);
set.insert(10); // No se insertará ya que 10 ya está en el set

// Comprobar si un elemento existe en el set
if (set.find(20) != set.end()) {
    cout << “20 está en el set”<< endl;
} else {
    cout << “20 no está en el set” << endl;
}
> 20 está en el set

// Iterar sobre el set
for (const int& num : set) {
    cout << num << “ ”;
}
> 10 20 30 

En C++ se puede utilizar set y unordered_set de la misma manera, pero al igual que con map y unordered_map, unordered_set es más eficiente para problemas más grandes

Mención de árboles y grafos

Los árboles y grafos son estructuras de datos más complejas utilizadas para representar jerarquías y relaciones entre elementos. Aunque no se exploran en detalle en este capítulo, son fundamentales en muchos algoritmos avanzados, como búsqueda y optimización. Este tema se explorará en detalle en el próximo capítulo.