Fundamentos de estructuras de datos: arrays, pilas, colas, árboles y tablas hash

Este artículo está escrito con fines didácticos. Los ejemplos son pequeños a propósito. En C++ real conviene comenzar por un contenedor de la biblioteca estándar, salvo que una necesidad medida justifique una implementación propia.

Aprender estructuras de datos puede parecer una tarea de memorizar nombres como push, pop y nodos de listas. La habilidad importante consiste en organizar los datos para que las operaciones más frecuentes del programa sean sencillas, baratas y predecibles.

Los mismos diez valores pueden pertenecer a un array cuando domina el acceso por índice, a una pila para deshacer la acción más reciente, a una cola para procesar primero la solicitud más antigua o a una tabla hash para buscar por clave.

Estructura de datos y tipo abstracto

Una pila define la regla de retirar primero el último elemento insertado. Internamente puede usar un array contiguo o una lista enlazada. Las operaciones y reglas visibles forman el tipo abstracto de datos; el almacenamiento concreto es su implementación.

• push inserta en la parte superior.
• pop elimina el elemento superior.
• top o peek lo consulta sin eliminarlo.
• empty comprueba si no hay elementos.
• size devuelve la cantidad.

std::stack es un adaptador de contenedor de C++ y usa std::deque por defecto.

Vocabulario mínimo de complejidad

Big O no lo explica todo. También importan la memoria, la localidad de caché, las asignaciones, la invalidación de iteradores y la complejidad de implementación.

Los arrays usan memoria contigua

int scores[5] = { 10, 20, 30, 40, 50 };

Con la dirección base y el tamaño de elemento se calcula directamente la dirección del índice i.

address(i) = base + i × sizeof(element)

El acceso es O(1) y el recorrido continuo suele aprovechar la caché. Insertar en el medio desplaza los elementos posteriores y cuesta O(N) en el peor caso. C++ ofrece std::array para tamaños fijos.

Arrays dinámicos y std::vector

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

Un vector administra memoria contigua, su size actual y la capacity disponible. Añadir al final es constante mientras quede espacio. Cuando se agota, se reserva un bloque mayor y se trasladan los elementos. Una reasignación es O(N), pero una larga serie de push_back tiene coste amortizado O(1) por inserción.

reserve reduce reasignaciones si se conoce una cantidad aproximada. Después de reasignar pueden quedar inválidos los punteros, referencias e iteradores antiguos.

Listas enlazadas

struct Node
{
    int value;
    Node* next;
};

Si ya se conoce un nodo, insertar directamente después solo cambia algunos enlaces y es O(1). Para llegar al elemento cien hay que atravesar los anteriores, por lo que el acceso aleatorio es O(N).

Las listas consumen memoria para enlaces, suelen tener peor localidad y complican la propiedad en implementaciones manuales. Tener muchas inserciones no demuestra por sí solo que una lista supere a un vector; también cuenta encontrar la posición.

Las pilas retiran primero el último valor

Una pila sigue LIFO, Last In First Out.

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

top vale 30 y después quedan 10 y 20.

pop no devuelve el valor

std::stack::pop() solo elimina y devuelve void. Hay que leer primero y retirar después.

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

Nunca se llama a top ni pop sobre una pila vacía.

Una pila pequeña basada en vector

template <typename T>
class SimpleStack
{
public:
    void push(const T& value) { values_.push_back(value); }

    void pop()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        return values_.back();
    }

    bool empty() const { return values_.empty(); }

private:
    std::vector<T> values_;
};

Las pilas sirven para llamadas a funciones, historial de deshacer, validación de paréntesis, búsqueda en profundidad, expresiones postfijas y versiones iterativas de algoritmos recursivos.

Las colas retiran primero el valor más antiguo

Una cola sigue FIFO, First In First Out.

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

first vale 101. Las colas encajan con planificación, mensajes, trabajos de impresión, búsqueda en anchura y búferes de paquetes.

Búfer circular

En vez de desplazar todo al quitar el primer elemento de un array, se mantienen índices head y tail separados. Al llegar al final físico, el módulo permite volver a cero.

tail = (tail + 1) % Capacity;
head = (head + 1) % Capacity;

Un ring buffer fijo es útil para audio, eventos de juegos y tuberías productor-consumidor limitadas. Varios hilos siguen necesitando sincronización o una concurrent queue apropiada.

Deque y cola de prioridad

std::deque permite insertar y eliminar en ambos extremos. Se usa en work stealing, sliding windows y colas bidireccionales. A diferencia de vector, no garantiza un único bloque continuo.

Una cola de prioridad entrega el valor de mayor prioridad en vez del más antiguo.

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);
int highest = scores.top();
scores.pop();

Suele basarse en un heap. Consultar la parte superior es O(1); insertar y retirarla es O(log N).

Tablas hash

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

Una función hash elige un bucket a partir de la clave. Con buena distribución y factor de carga, buscar, insertar y borrar cuesta en promedio O(1). Las colisiones son inevitables y el peor caso puede llegar a O(N).

Para una clave propia, igualdad y hash deben concordar: dos claves iguales tienen que producir el mismo hash.

Árboles y árboles binarios de búsqueda

Los árboles representan sistemas de archivos, UI, scene graphs y jerarquías de documentos. La root no tiene parent, una leaf no tiene children, depth mide la distancia a la root y height la distancia a la leaf más profunda.

Un árbol binario de búsqueda tiene como máximo dos hijos. Una regla habitual coloca claves menores a la izquierda y mayores a la derecha. Equilibrado, buscar, insertar y borrar cuesta O(log N). Insertar datos ya ordenados en un árbol simple puede crear una cadena y degradar a O(N).

std::map conserva el orden con operaciones O(log N). Si el orden no importa y se prefiere búsqueda media constante, se puede usar std::unordered_map.

Heaps

En un max-heap cada parent es al menos tan grande como sus children; en un min-heap ocurre lo contrario. La colección completa no está ordenada.

Un árbol binario completo se almacena con eficiencia en un array. Para el índice i desde cero:

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

Los heaps son adecuados para extraer repetidamente un mínimo o máximo. Buscar un valor arbitrario sigue siendo normalmente O(N).

Tries y grafos

Un trie usa caracteres o bits de la clave como recorrido y comparte prefijos. La búsqueda suele describirse como O(L) para longitud L. Se usa en autocompletado, diccionarios y rutas.

Un grafo contiene vertices y edges. Una matriz de adyacencia comprueba una conexión en O(1) y consume O(V²) memoria. Una lista de adyacencia usa aproximadamente O(V + E) y se adapta a grafos dispersos.

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

BFS usa una cola; DFS utiliza la pila de llamadas o una pila explícita.

Complejidades representativas

Elección y errores frecuentes

Hay que preguntar qué operación domina, si se conserva orden, si hace falta índice, clave o extremos, si se conoce el máximo, si los punteros deben ser estables, si una API exige memoria contigua y si habrá varios hilos. Para una secuencia ordinaria, std::vector es un buen comienzo.

Errores frecuentes son acceder a pilas o colas vacías, esperar que pop devuelva un valor, conservar punteros de vector tras reasignar, ignorar la búsqueda de posición en listas, prometer O(1) en hash, olvidar la profundidad recursiva y construir propiedad con punteros sin una política clara.

Resumen

Arrays y vectors proporcionan índice rápido y buena localidad. Las listas cambian enlaces con rapidez en una posición conocida, pero pagan por recorrer y dispersar memoria. Stack, queue, deque y priority queue imponen distintos órdenes. Las tablas hash ofrecen búsqueda media rápida, los árboles equilibrados conservan orden, los heaps exponen extremos y los grafos representan conexiones generales.

La mejor estructura no es la más compleja, sino la que hace claras y predecibles las operaciones reales del programa.