C++ Estructuras de Datos

C++ proporciona múltiples estructuras de datos, tanto básicas como arreglos, estructuras, clases, etc., como contenedores STL avanzados comovector、mapyunordered_mapetc.

A continuación se detallan las estructuras de datos más utilizadas en C++, sus características y usos.

1. Arreglo (Array)

El arreglo es la estructura de datos más básica, utilizada para almacenar un conjunto de datos del mismo tipo.

Características：

  • Tamaño fijo; una vez declarado, el tamaño no puede cambiar.
  • Acceso directo a los elementos, con complejidad temporal O(1).
  • Adecuado para manejar colecciones de tamaño conocido y con elementos del mismo tipo.

Ejemplo

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // Imprime el primer elemento

Ventajas y Desventajas：

  • Ventajas: acceso rápido, memoria compacta.
  • Desventajas: tamaño fijo, no se puede expandir dinámicamente, no apto para manejar conjuntos de datos de tamaño incierto.

2. Estructura (Struct)

La estructura permite combinar datos de diferentes tipos para formar un tipo de dato personalizado.

Características：

  • Puede contener variables miembro de diferentes tipos.
  • Proporciona un encapsulamiento básico de los datos, pero con funcionalidad limitada.

Ejemplo：

Ejemplo

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Imprime Alice

3. Clase (Class)

La clase es la estructura central en C++ para la programación orientada a objetos, que permite definir variables miembro y funciones miembro. Similar astructla estructura (struct), pero con mayor funcionalidad, soporta características como herencia, encapsulamiento y polimorfismo.

Características：

  • Puede contener variables miembro, funciones miembro, constructores y destructores.
  • Soporta características de orientación a objetos, como encapsulamiento, herencia y polimorfismo.

Ejemplo

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // Imprime: Name: Bob, Age: 30

4. Lista Enlazada (Linked List)

La lista enlazada es una estructura de datos dinámica compuesta por una serie de nodos; cada nodo contiene datos y un puntero al siguiente nodo.

Características：

  • Ajusta dinámicamente su tamaño, no necesita definir capacidad de antemano.
  • Las operaciones de inserción y eliminación son eficientes, con complejidad temporal O(1) (al operar en la cabeza o cola de la lista).
  • Búsqueda lineal, con complejidad temporal O(n).

Ejemplo (Lista Enlazada Simple)

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // Insertar nuevo nodo

Ventajas y Desventajas：

  • Ventajas: tamaño dinámico, adecuado para escenarios con inserciones y eliminaciones frecuentes.
  • Desventajas: la eficiencia del acceso aleatorio es baja, no es tan rápido como el acceso directo de los arreglos.

5. Pila (Stack)

La pila es una estructura de datos de tipo LIFO (Last In First Out), comúnmente utilizada en escenarios como recursión, búsqueda en profundidad, etc.

Características：

  • Solo permite operaciones de inserción y eliminación en la cima de la pila.
  • La complejidad temporal es O(1).

Ejemplo

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // Imprime 2
s.pop();

Ventajas y Desventajas：

  • Ventajas: operación simple y alta eficiencia.
  • Desventajas: solo se puede operar en la cima de la pila; para acceder a otros elementos es necesario sacar los elementos superiores.

6. Cola (Queue)

La cola es una estructura de datos de tipo FIFO (First In First Out), comúnmente utilizada en escenarios como búsqueda en amplitud, planificación de tareas, etc.

Características：

  • La inserción se realiza en la parte trasera (final) y la eliminación en la parte delantera (frente).
  • La complejidad temporal es O(1).

Ejemplo

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // Imprime 1
q.pop();

Ventajas y Desventajas：

  • Ventajas: adecuado para escenarios de procesamiento secuencial de datos, como la planificación de tareas.
  • Desventajas: no se puede acceder aleatoriamente a los elementos.

7. Cola de Doble Extremo (Deque)

La cola de doble extremo permite operaciones de inserción y eliminación en ambos extremos; es una combinación de pila y cola.

Características：

  • Permite insertar y eliminar en ambos extremos.
  • La complejidad temporal es O(1).

Ejemplo

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // Imprime 2
dq.pop_front();

Ventajas y Desventajas：

  • Ventajas: operaciones bidireccionales flexibles.
  • Desventajas: mayor uso de espacio, adecuado para escenarios con operaciones frecuentes en ambos extremos.

8. Tabla Hash (Hash Table)

La tabla hash es una estructura de datos que almacena datos mediante pares clave-valor, soporta búsqueda, inserción y eliminación rápidas. En C++,unordered_mapes la implementación de la tabla hash.

Características：

  • Utiliza una función hash para localizar elementos rápidamente, con complejidad temporal O(1).
  • No garantiza el orden de los elementos.

Ejemplo

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // Imprime 10

Ventajas y Desventajas：

  • Ventajas: alta eficiencia en operaciones de búsqueda, inserción y eliminación.
  • Desventajas: no se puede garantizar el orden de los elementos, y el rendimiento disminuye cuando hay colisiones hash.

9. Mapa (Map)

mapEs un contenedor ordenado de pares clave-valor, cuya implementación subyacente es un árbol rojo-negro. A diferencia deunordered_mapeste garantiza el orden de las claves, con una complejidad temporal de O(log n) para la búsqueda, inserción y eliminación.

Características：

  • Garantiza que los elementos se ordenen según la clave.
  • Se implementa mediante un árbol binario de búsqueda.

Ejemplo

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // Imprime 10

Ventajas y Desventajas：

  • Ventajas: elementos ordenados, adecuado para escenarios que requieren procesamiento secuencial de datos.
  • Desventajas: la eficiencia operativa, en comparación conunordered_mapes ligeramente inferior.

10. Conjunto (Set)

setEs un conjunto ordenado para almacenar elementos únicos, implementado también con un árbol rojo-negro. Garantiza elementos no repetidos y ordenados.

Características：

  • Garantiza la unicidad de los elementos.
  • Los elementos se ordenan automáticamente en orden ascendente.
  • La complejidad temporal es O(log n).

Ejemplo

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // Imprime 1

Ventajas y Desventajas：

  • Ventajas: ordenación automática y garantía de unicidad.
  • Desventajas: la eficiencia de inserción y eliminación es inferior a la de los conjuntos desordenados.

11. Vector Dinámico (Vector)

vectorEs la implementación de arreglo dinámico proporcionada por la biblioteca estándar de C++, puede expandir dinámicamente su capacidad y soporta acceso aleatorio.

Características：

  • Ajusta dinámicamente el tamaño.
  • Soporta acceso aleatorio, con complejidad temporal O(1).
  • Cuando la capacidad es insuficiente, se expande dinámicamente, con complejidad temporal amortizada O(1).

Ejemplo

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // Imprime 1

Ventajas y Desventajas：

  • Ventajas: soporta acceso aleatorio y expansión dinámica.
  • Desventajas: la eficiencia de inserción y eliminación en el medio es baja.
Otras Extensiones