Pilas, Colas y Estructuras Lineales Restringidas - Programación 1

Pilas (Stacks)¶

Una pila es una estructura de datos lineal que sigue el principio LIFO (Last In, First Out): el último elemento en entrar es el primero en salir. Es análogo a una pila de platos donde solo podés agregar o quitar platos desde la parte superior.

Figure 1:Estructura de pila con operaciones push (apilar) y pop (desapilar). El acceso es únicamente por el tope.

Operaciones Fundamentales¶

push(elemento): Agrega un elemento al tope de la pila.
pop(): Extrae y retorna el elemento del tope.
peek() o top(): Retorna el elemento del tope sin extraerlo.
es_vacia(): Verifica si la pila está vacía.

Implementación con Lista Enlazada¶

Figure 2:Representación en memoria de una pila implementada con lista enlazada. El tope apunta al primer nodo de la lista.

Estructura de Datos¶

typedef struct nodo {
    void *dato;
    struct nodo *siguiente;
} nodo_t;

struct pila {
    nodo_t *tope;
    size_t tamanio;
};

Creación de una Pila¶

pila_t *pila_crear(void)
{
    pila_t *pila = malloc(sizeof(*pila));
    if (pila == NULL)
    {
        return NULL;
    }
    pila->tope = NULL;
    pila->tamanio = 0;
    return pila;
}

Apilar (Push)¶

bool pila_push(pila_t *pila, void *dato)
{
    if (pila == NULL)
    {
        return false;
    }
    
    nodo_t *nuevo = malloc(sizeof(*nuevo));
    if (nuevo == NULL)
    {
        return false;
    }
    
    nuevo->dato = dato;
    nuevo->siguiente = pila->tope;
    pila->tope = nuevo;
    pila->tamanio++;
    
    return true;
}

Desapilar (Pop)¶

bool pila_pop(pila_t *pila, void **dato)
{
    if (pila == NULL || pila->tope == NULL)
    {
        return false;
    }
    
    nodo_t *nodo_a_eliminar = pila->tope;
    if (dato != NULL)
    {
        *dato = nodo_a_eliminar->dato;
    }
    pila->tope = nodo_a_eliminar->siguiente;
    
    free(nodo_a_eliminar);
    pila->tamanio--;
    
    return true;
}

Ver Tope (Peek)¶

bool pila_peek(const pila_t *pila, void **dato)
{
    if (pila == NULL || pila->tope == NULL)
    {
        return false;
    }
    
    if (dato != NULL)
    {
        *dato = pila->tope->dato;
    }
    return true;
}

Verificar si está Vacía¶

bool pila_es_vacia(const pila_t *pila)
{
    return (pila == NULL) || (pila->tope == NULL);
}

Destruir Pila¶

void pila_destruir(pila_t *pila, destruir_dato_fn destruir_dato)
{
    if (pila == NULL)
    {
        return;
    }
    
    while (pila->tope != NULL)
    {
        nodo_t *nodo_actual = pila->tope;
        pila->tope = nodo_actual->siguiente;
        if (destruir_dato != NULL && nodo_actual->dato != NULL)
        {
            destruir_dato(nodo_actual->dato);
        }
        free(nodo_actual);
    }
    
    free(pila);
}

Análisis de Complejidad (Lista Enlazada)¶

Operación	Complejidad Temporal	Complejidad Espacial
push	$O(1)$	$O(1)$
pop	$O(1)$	$O(1)$
peek	$O(1)$	$O(1)$
es_vacia	$O(1)$	$O(1)$

Implementación con Arreglo Dinámico¶

Una alternativa es implementar la pila usando un arreglo, donde el tope es el último elemento ocupado.

Pila implementada con arreglo. El índice tope indica la posición del último elemento. — Figure 3:Pila implementada con arreglo. El índice `tope` indica la posición del último elemento.

Estructura de Datos¶

struct pila {
    void **elementos;
    size_t tope;       // Próximo índice libre / Cantidad de elementos
    size_t capacidad;  // Capacidad total del arreglo
};

Creación con Capacidad Inicial¶

pila_t *pila_crear_arreglo(size_t capacidad_inicial)
{
    if (capacidad_inicial == 0)
    {
        return NULL;
    }
    
    pila_t *pila = malloc(sizeof(*pila));
    if (pila == NULL)
    {
        return NULL;
    }
    
    pila->elementos = malloc(capacidad_inicial * sizeof(*(pila->elementos)));
    if (pila->elementos == NULL)
    {
        free(pila);
        return NULL;
    }
    
    pila->tope = 0;
    pila->capacidad = capacidad_inicial;
    
    return pila;
}

Apilar con Redimensionamiento¶

static bool pila_redimensionar(pila_t *pila)
{
    size_t nueva_capacidad = pila->capacidad * 2;
    void **nuevo_arreglo = realloc(pila->elementos, nueva_capacidad * sizeof(*nuevo_arreglo));
    if (nuevo_arreglo == NULL)
    {
        return false;
    }
    
    pila->elementos = nuevo_arreglo;
    pila->capacidad = nueva_capacidad;
    
    return true;
}

bool pila_push_arreglo(pila_t *pila, void *dato)
{
    if (pila == NULL)
    {
        return false;
    }
    
    if (pila->tope >= pila->capacidad)
    {
        if (!pila_redimensionar(pila))
        {
            return false;
        }
    }
    
    pila->elementos[pila->tope] = dato;
    pila->tope++;
    
    return true;
}

Desapilar (Arreglo)¶

bool pila_pop_arreglo(pila_t *pila, void **dato)
{
    if (pila == NULL || pila->tope == 0)
    {
        return false;
    }
    
    pila->tope--;
    if (dato != NULL)
    {
        *dato = pila->elementos[pila->tope];
    }
    
    return true;
}

Análisis de Complejidad (Arreglo)¶

Operación	Complejidad Temporal	Complejidad Espacial
push	$O(1)$ amortizado	$O(1)$
pop	$O(1)$	$O(1)$
peek	$O(1)$	$O(1)$
es_vacia	$O(1)$	$O(1)$

Aplicaciones de Pilas¶

Las pilas aparecen naturalmente en numerosos contextos de programación:

Gestión de llamadas a funciones: La pila de ejecución (call stack) mantiene los registros de activación.
Evaluación de expresiones: Conversión de notación infija a postfija, evaluación de expresiones postfijas.
Backtracking: Algoritmos de búsqueda en profundidad, resolución de laberintos.
Deshacer/Rehacer: Editores de texto mantienen pilas de operaciones.
Parsing: Análisis sintáctico de lenguajes de programación (verificación de paréntesis balanceados).

Ejemplo: Verificación de Paréntesis Balanceados¶

bool parentesis_balanceados(const char *expresion)
{
    if (expresion == NULL)
    {
        return false;
    }
    
    pila_t *pila = pila_crear();
    if (pila == NULL)
    {
        return false;
    }
    
    for (size_t i = 0; expresion[i] != '\0'; i++)
    {
        char caracter = expresion[i];
        if (caracter == '(')
        {
            if (!pila_push(pila, caracter))
            {
                pila_destruir(pila);
                return false;
            }
        }
        else if (caracter == ')')
        {
            if (pila_es_vacia(pila))
            {
                pila_destruir(pila);
                return false;
            }
            int temporal;
            pila_pop(pila, &temporal);
        }
    }
    
    bool resultado = pila_es_vacia(pila);
    pila_destruir(pila);
    return resultado;
}

Colas (Queues)¶

Una cola es una estructura de datos lineal que sigue el principio FIFO (First In, First Out): el primer elemento en entrar es el primero en salir. Es análogo a una fila de personas donde quien llega primero es atendido primero.

Figure 4:Representación en memoria de una cola implementada con lista enlazada. Se mantienen punteros al frente y al final.

Estructura de Datos¶

typedef struct nodo {
    void *dato;
    struct nodo *siguiente;
} nodo_t;

struct cola {
    nodo_t *frente;
    nodo_t *final;
    size_t tamanio;
};

Note

A diferencia de la pila que solo requiere de un puntero al tope, la cola utiliza dos punteros: uno al frente (para cola_dequeue) y otro al final (para cola_enqueue). Esto garantiza que ambas operaciones se ejecuten en tiempo constante $O(1)$ .


#### Creación de una Cola

```c
cola_t *cola_crear(void)
{
    cola_t *cola = malloc(sizeof(*cola));
    if (cola == NULL)
    {
        return NULL;
    }
    
    cola->frente = NULL;
    cola->final = NULL;
    cola->tamanio = 0;
    
    return cola;
}
```

#### Encolar (Enqueue)

```c
bool cola_enqueue(cola_t *cola, void *dato)
{
    if (cola == NULL)
    {
        return false;
    }
    
    nodo_t *nuevo = malloc(sizeof(*nuevo));
    if (nuevo == NULL)
    {
        return false;
    }
    
    nuevo->dato = dato;
    nuevo->siguiente = NULL;
    
    if (cola->final == NULL)
    {
        cola->frente = nuevo;
        cola->final = nuevo;
    }
    else
    {
        cola->final->siguiente = nuevo;
        cola->final = nuevo;
    }
    
    cola->tamanio++;
    return true;
}
```

:::{important}
Es indispensable considerar el caso particular de la cola vacía. En tal situación, tanto el puntero `frente` como el puntero `final` deben referenciar al nuevo nodo creado.

Desencolar (Dequeue)¶

bool cola_dequeue(cola_t *cola, void **dato)
{
    if (cola == NULL || cola->frente == NULL)
    {
        return false;
    }
    
    nodo_t *nodo_a_eliminar = cola->frente;
    if (dato != NULL)
    {
        *dato = nodo_a_eliminar->dato;
    }
    cola->frente = nodo_a_eliminar->siguiente;
    
    if (cola->frente == NULL)
    {
        cola->final = NULL;
    }
    
    free(nodo_a_eliminar);
    cola->tamanio--;
    
    return true;
}

Ver Frente (Peek)¶

bool cola_peek(const cola_t *cola, void **dato)
{
    if (cola == NULL || cola->frente == NULL)
    {
        return false;
    }
    
    if (dato != NULL)
    {
        *dato = cola->frente->dato;
    }
    return true;
}

Destruir Cola¶

void cola_destruir(cola_t *cola, destruir_dato_fn destruir_dato)
{
    if (cola == NULL)
    {
        return;
    }
    
    while (cola->frente != NULL)
    {
        nodo_t *nodo_actual = cola->frente;
        cola->frente = nodo_actual->siguiente;
        if (destruir_dato != NULL && nodo_actual->dato != NULL)
        {
            destruir_dato(nodo_actual->dato);
        }
        free(nodo_actual);
    }
    
    free(cola);
}

Análisis de Complejidad (Lista Enlazada)¶

Operación	Complejidad Temporal	Complejidad Espacial
enqueue	$O(1)$	$O(1)$
dequeue	$O(1)$	$O(1)$
peek	$O(1)$	$O(1)$
es_vacia	$O(1)$	$O(1)$

Implementación con Arreglo Circular¶

Una implementación eficiente de cola con arreglo usa la técnica de arreglo circular, donde los índices “dan la vuelta” al final del arreglo.

Figure 5:Cola implementada como arreglo circular. Los índices se calculan módulo la capacidad.

Estructura de Datos¶

struct cola {
    void **elementos;
    size_t frente;
    size_t final;
    size_t tamanio;
    size_t capacidad;
};

Creación de Cola Circular¶

cola_t *cola_crear_circular(size_t capacidad_inicial)
{
    if (capacidad_inicial == 0)
    {
        return NULL;
    }
    
    cola_t *cola = malloc(sizeof(*cola));
    if (cola == NULL)
    {
        return NULL;
    }
    
    cola->elementos = malloc(capacidad_inicial * sizeof(*(cola->elementos)));
    if (cola->elementos == NULL)
    {
        free(cola);
        return NULL;
    }
    
    cola->frente = 0;
    cola->final = 0;
    cola->tamanio = 0;
    cola->capacidad = capacidad_inicial;
    
    return cola;
}

Encolar en Arreglo Circular¶

static bool cola_redimensionar_circular(cola_t *cola)
{
    size_t nueva_capacidad = cola->capacidad * 2;
    void **nuevo_arreglo = malloc(nueva_capacidad * sizeof(*nuevo_arreglo));
    if (nuevo_arreglo == NULL)
    {
        return false;
    }
    
    for (size_t i = 0; i < cola->tamanio; i++)
    {
        size_t indice = (cola->frente + i) % cola->capacidad;
        nuevo_arreglo[i] = cola->elementos[indice];
    }
    
    free(cola->elementos);
    cola->elementos = nuevo_arreglo;
    cola->frente = 0;
    cola->final = cola->tamanio;
    cola->capacidad = nueva_capacidad;
    
    return true;
}

bool cola_enqueue_circular(cola_t *cola, void *dato)
{
    if (cola == NULL)
    {
        return false;
    }
    
    if (cola->tamanio == cola->capacidad)
    {
        if (!cola_redimensionar_circular(cola))
        {
            return false;
        }
    }
    
    cola->elementos[cola->final] = dato;
    cola->final = (cola->final + 1) % cola->capacidad;
    cola->tamanio++;
    
    return true;
}

Desencolar en Arreglo Circular¶

bool cola_dequeue_circular(cola_t *cola, void **dato)
{
    if (cola == NULL || cola->tamanio == 0)
    {
        return false;
    }
    
    if (dato != NULL)
    {
        *dato = cola->elementos[cola->frente];
    }
    cola->frente = (cola->frente + 1) % cola->capacidad;
    cola->tamanio--;
    
    return true;
}

Análisis de Complejidad (Arreglo Circular)¶

Operación	Complejidad Temporal	Complejidad Espacial
enqueue	$O(1)$ amortizado	$O(1)$
dequeue	$O(1)$	$O(1)$
peek	$O(1)$	$O(1)$
es_vacia	$O(1)$	$O(1)$

Aplicaciones de Colas¶

Las colas modelan situaciones donde el orden de llegada importa:

Sistemas operativos: Scheduling de procesos, colas de impresión.
Redes: Buffers de transmisión, enrutamiento de paquetes.
Algoritmos de grafos: Búsqueda en anchura (BFS).
Simulaciones: Modelado de filas de espera, teoría de colas.
Procesamiento asíncrono: Cola de tareas, sistemas de mensajería.

Comparación: Pilas vs Colas¶

Aspecto	Pila (LIFO)	Cola (FIFO)
Política	Last In, First Out	First In, First Out
Analogía	Pila de platos	Fila de personas
Operaciones	push, pop, peek	enqueue, dequeue, peek
Complejidad	$O(1)$ todas	$O(1)$ todas
Aplicación típica	Backtracking, parsing	Scheduling, BFS
Implementación simple	Lista (un puntero)	Lista (dos punteros)
Implementación arreglo	Índice tope	Arreglo circular

Deques (Double-Ended Queues)¶

Un deque (pronunciado “deck”) es una generalización que permite insertar y extraer elementos en ambos extremos.

Figure 6:Deque con operaciones en ambos extremos. Es una generalización de pilas y colas.

Operaciones¶

push_front(elemento): Agrega al frente.
push_back(elemento): Agrega al final.
pop_front(): Extrae del frente.
pop_back(): Extrae del final.

Aplicaciones de Deques¶

Algoritmos de ventana deslizante: Mantener mínimos/máximos en una ventana.
Navegación con historial: Forward/backward en navegadores.
Work stealing: Algoritmos paralelos donde los threads roban tareas de ambos extremos.

Comparación de Implementaciones¶

Lista Enlazada vs Arreglo¶

Criterio	Lista Enlazada	Arreglo (Circular)
Memoria	Overhead por punteros	Compacta, localidad de caché
Tamaño	Dinámico sin límite	Requiere redimensionamiento
Operaciones	Siempre $O(1)$	$O(1)$ amortizado
Complejidad código	Media	Alta (aritmética modular)
Uso típico	Tamaño impredecible	Tamaño acotado

Panorama de Estructuras de Datos¶

Las pilas y colas son solo el comienzo. Existe un ecosistema rico de estructuras de datos, cada una optimizada para diferentes patrones de acceso.

Clasificación por Restricciones de Acceso¶

Acceso Completamente Restringido:
- Pilas: solo el tope es accesible
- Colas: solo frente y final
Acceso Parcialmente Restringido:
- Deques: ambos extremos
- Colas de Prioridad: elemento de máxima prioridad
Acceso Indexado:
- Arreglos: acceso por índice en $O(1)$
- Listas: acceso secuencial en $O(n)$
Acceso por Clave:
- Tablas Hash: búsqueda en $O(1)$ promedio
- Árboles Binarios de Búsqueda: búsqueda en $O(\log n)$

Estructuras Avanzadas¶

Árboles:

Heap (Montículo): Cola de prioridad eficiente, $O(\log n)$ insert/extract-min
BST (Binary Search Tree): Búsqueda, inserción, eliminación en $O(\log n)$ promedio
AVL/Red-Black: BST balanceados, garantizan $O(\log n)$ peor caso
B-trees: Árboles de búsqueda para almacenamiento en disco
Tries: Árboles de prefijos para strings

Grafos:

Matriz de Adyacencia: Representación densa, $O(1)$ para verificar arista
Lista de Adyacencia: Representación dispersa, eficiente en espacio

Tablas Hash:

Chaining: Manejo de colisiones con listas
Open Addressing: Probing para resolver colisiones
Rendimiento: $O(1)$ promedio para insert/search/delete

Estructuras Especializadas:

Union-Find: Conjuntos disjuntos dinámicos
Filtros de Bloom: Verificación probabilística de pertenencia
Skip Lists: Estructura probabilística alternativa a BST

Ejercicios de Pilas y Colas¶

Ejercicio 1: Inversión de una Cadena con Pila¶

Exercise 1

Implementá una función que use una pila para invertir una cadena de caracteres.

función invertir_cadena(cadena: cadena) → cadena:
    // Tu implementación aquí

Por ejemplo:

Entrada: “hola”
Salida: “aloh”

Ejercicio 2: Validar Expresiones con Múltiples Delimitadores¶

Exercise 2

Extendé el ejemplo de paréntesis balanceados para soportar múltiples tipos de delimitadores: (), [], {}. La función debe verificar que:

Cada apertura tenga su cierre correspondiente
Los cierres ocurran en el orden correcto

función delimitadores_balanceados(expresion: cadena) → booleano:
    // Tu implementación aquí

Por ejemplo:

"{[()]}" → válido
"{[(])}" → inválido (cierre en orden incorrecto)
"{[(" → inválido (sin cerrar)

Ejercicio 3: Simulador de Impresora¶

Exercise 3

Implementá un simulador de cola de impresión que:

Reciba trabajos con un identificador y cantidad de páginas
Procese trabajos en orden FIFO
Reporte el tiempo total de procesamiento (asumí 1 segundo por página)

Trabajo:
    id: entero
    paginas: entero

función simular_impresora(trabajos: arreglo de Trabajo) → entero:
    // Retorna tiempo total de procesamiento

Ejercicio 4: Implementar Cola con Dos Pilas¶

Exercise 4

Implementá una cola usando dos pilas. La idea es:

Una pila para enqueue (entrada)
Una pila para dequeue (salida)
Cuando la pila de salida está vacía, transferir todos los elementos de entrada a salida

Cola_con_Pilas:
    pila_entrada: Pila
    pila_salida: Pila

función enqueue_con_pilas(cola: Cola_con_Pilas, dato: entero) → booleano:
    // Tu implementación

función dequeue_con_pilas(cola: Cola_con_Pilas, dato: referencia a entero) → booleano:
    // Tu implementación

Analizá la complejidad amortizada de las operaciones.

Ejercicio 5: Evaluación de Expresiones Postfijas¶

Exercise 5

Implementá un evaluador de expresiones en notación postfija (Reverse Polish Notation) usando una pila.

En notación postfija, los operadores vienen después de los operandos:

Infija: (3 + 4) * 5
Postfija: 3 4 + 5 *

Algoritmo:

Recorrer la expresión
Si es número, apilar
Si es operador, desapilar dos operandos, aplicar operación, apilar resultado

función evaluar_postfija(expresion: cadena) → entero:
    // Tu implementación

Por ejemplo:

"3 4 + 5 *" → 35
"15 7 1 1 + - / 3 * 2 1 1 + + -" → 5

Referencias y Lecturas Complementarias¶

Para profundizar en el estudio de los TADs y estructuras de datos, se recomiendan las siguientes referencias:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Weiss, M. A. (2014). Data Structures and Algorithm Analysis in C (2nd ed.). Pearson.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

Para aspectos específicos de gestión de memoria y su impacto en la implementación de TADs, consultá:

Funciones de Gestión de Memoria (<stdlib.h>) para entender el modelo de memoria completo.
Resumen de Buenas Prácticas para patrones seguros de manejo de memoria dinámica.
Capítulo: Memoria Dinámica — sección Valgrind para técnicas de depuración de estructuras dinámicas.

Resumen¶

Los Tipos de Datos Abstractos son una herramienta fundamental para construir software modular y mantenible. En este apunte hemos cubierto:

El concepto de TAD y la separación entre interfaz e implementación.
El TAD Secuencia como abstracción fundamental, demostrando cómo la misma interfaz puede implementarse con diferentes estructuras de datos.
Dos implementaciones de Secuencia:
- Arreglos dinámicos: excelentes para acceso aleatorio y localidad de caché.
- Listas enlazadas: ideales para inserciones/eliminaciones dinámicas.
La diferencia entre memoria estática y dinámica, y cuándo usar cada una (para detalles completos, consultá Funciones de Gestión de Memoria (<stdlib.h>)).
Listas enlazadas simples, dobles y circulares, con todas sus operaciones fundamentales.
Pilas (LIFO) y Colas (FIFO) como TADs especializados:
- Múltiples implementaciones (lista enlazada, arreglo, arreglo circular)
- Aplicaciones prácticas en sistemas y algoritmos
- Análisis de complejidad temporal y espacial
Consideraciones de implementación: manejo de errores, invariantes y seguridad.
Análisis de complejidad temporal de las operaciones en diferentes implementaciones (para el fundamento teórico completo, consultá Introducción: El Estudio de la Eficiencia).
Panorama general de estructuras de datos avanzadas y su clasificación.