Pilas y Colas: Estructuras de Datos Esenciales

En el vasto universo de la programación, comprender las estructuras de datos es esencial. Dos de las más fundamentales y omnipresentes son las Pilas (Stacks) y las Colas (Queues). Su lógica es intuitiva y se inspira en situaciones cotidianas:

• Imagina una pila de platos: el último que se coloca es el primero que se retira. Esta es la esencia de una Pila.
• Piensa en una fila de personas esperando: el primero en llegar es el primero en ser atendido. Así funciona una Cola.

Estas estructuras, aunque conceptualmente sencillas, son los cimientos para algoritmos complejos como la recursión, la búsqueda en profundidad (DFS) y en anchura (BFS), la gestión de memoria de programas y la planificación de tareas.

La Pila (Stack): El Principio LIFO (Last In, First Out)

Una Pila es una colección lineal de elementos que restringe las operaciones de inserción y eliminación a un solo extremo, conocido como la cima (Top). Su principio fundamental es "último en entrar, primero en salir" (LIFO). Piensa en un cargador de dardos: el dardo que pones al último es el primero que disparas.

• Cima (Top): El único extremo donde se permite la inserción y eliminación de elementos.
• Fondo (Bottom): El extremo opuesto, estático, donde no se realizan operaciones.
• Apilar (Push): Operación para añadir un elemento a la cima de la pila.
• Desapilar (Pop): Operación para retirar un elemento de la cima de la pila.

Las pilas pueden implementarse de dos maneras principales: mediante un almacenamiento secuencial (usando arrays o arrays dinámicos) o mediante un almacenamiento enlazado (usando listas enlazadas).

Pila con Almacenamiento Secuencial (Basada en Array)

Definición de la Estructura para Pila Secuencial

Una pila secuencial utiliza un segmento contiguo de memoria (como un array o un array dinámico) para almacenar sus elementos. Se gestiona mediante el movimiento de un índice que apunta a la cima.

• Características: Un índice (comúnmente llamado cima o top) indica la posición del elemento superior o la próxima posición disponible para la inserción. Es crucial decidir si cima apunta al último elemento o al siguiente espacio libre. En este artículo, cima apuntará al siguiente espacio disponible, lo que convenientemente iguala su valor al número de elementos.
• Ventajas: Acceso eficiente a los elementos debido a la contigüidad en memoria, lo que resulta en un tiempo de acceso O(1).
• Desventajas: Requiere pre-asignar memoria. Si la pila se llena, necesita una re-asignación dinámica que puede incurrir en costos de rendimiento.

// Define el tipo de dato que almacenará la pila (ej. entero)
typedef int TipoDatoPila;

// Estructura para una pila basada en array (secuencial)
typedef struct PilaArreglo
{
    TipoDatoPila* elementos; // Puntero al array dinámico de elementos
    int indiceCima;          // Índice del próximo espacio disponible (también cuenta de elementos)
    int capacidadTotal;      // Capacidad actual del array
} PilaSecuencial;

Operaciones Básicas de una Pila Secuencial

A continuación, se presenta la implementación en C de las operaciones fundamentales para una pila secuencial: inicialización, destrucción, apilar, desapilar, obtener elemento superior, verificar si está vacía y obtener el tamaño.

// Inicializa una pila secuencial
void InicializarPilaSec(PilaSecuencial* pPila)
{
    // Verifica que el puntero a la pila no sea nulo
    assert(pPila);
    pPila->elementos = NULL;
    pPila->indiceCima = 0;
    pPila->capacidadTotal = 0;
}

// Destruye una pila secuencial, liberando la memoria
void DestruirPilaSec(PilaSecuencial* pPila)
{
    assert(pPila);
    free(pPila->elementos); // Libera la memoria del array
    pPila->elementos = NULL;
    pPila->indiceCima = 0;
    pPila->capacidadTotal = 0;
}

// Apila un elemento en la cima de la pila
void ApilarSec(PilaSecuencial* pPila, TipoDatoPila valor)
{
    assert(pPila);
    // Verifica si es necesario redimensionar el array
    if (pPila->indiceCima == pPila->capacidadTotal)
    {
        // Duplica la capacidad; si es 0, inicializa a 4
        int nuevaCapacidad = pPila->capacidadTotal == 0 ? 4 : (pPila->capacidadTotal * 2);
        TipoDatoPila* temp = (TipoDatoPila*)realloc(pPila->elementos, nuevaCapacidad * sizeof(TipoDatoPila));
        if (temp == NULL)
        {
            perror("Error al redimensionar la pila!\n");
            return;
        }
        pPila->elementos = temp;
        pPila->capacidadTotal = nuevaCapacidad;
    }
    // Inserta el elemento y actualiza el índice de la cima
    pPila->elementos[pPila->indiceCima] = valor;
    pPila->indiceCima++;
}

// Desapila un elemento de la cima de la pila
void DesapilarSec(PilaSecuencial* pPila)
{
    assert(pPila);
    // Asegura que la pila no esté vacía antes de desapilar
    assert(pPila->indiceCima > 0);
    pPila->indiceCima--; // Simplemente decrementa el índice de la cima
}

// Obtiene el elemento en la cima de la pila sin eliminarlo
TipoDatoPila ObtenerCimaSec(PilaSecuencial* pPila)
{
    assert(pPila);
    // Asegura que la pila no esté vacía
    assert(pPila->indiceCima > 0);
    return pPila->elementos[pPila->indiceCima - 1]; // El elemento superior está en 'indiceCima - 1'
}

// Verifica si la pila está vacía
bool EstaVaciaSec(PilaSecuencial* pPila)
{
    assert(pPila);
    return pPila->indiceCima == 0;
}

// Obtiene el número de elementos en la pila
int ObtenerTamanoSec(PilaSecuencial* pPila)
{
    assert(pPila);
    return pPila->indiceCima;
}

Pila con Almacenamiento Enlazado (Basada en Lista Enlazada)

Definición de la Estructura para Pila Enlazada

A diferencia de la pila secuencial, una pila enlazada utiliza una lista enlazada simple para su implementación. Cada elemento se almacena en un nodo independiente que contiene el dato y un puntero al siguiente nodo.

• Características: Las operaciones de apilar y desapilar se corresponden con las operaciones de inserción y eliminación al principio de la lista enlazada (cabeza). Un puntero (pCima) apunta al primer nodo de la lista, que es la cima de la pila.
• Ventajas: No requiere pre-asignación de memoria y puede crecer o encogerse dinámicamente, eliminando el riesgo de "desbordamiento de pila". Las operaciones de apilar y desapilar tienen una complejidad de tiempo O(1).
• Desventajas: Cada nodo requiere espacio adicional para el puntero, lo que puede resultar en un uso de memoria ligeramente menos eficiente que una pila secuencial.

// Define el tipo de dato que almacenará la pila
typedef int TipoDatoPilaEnlazada;

// Estructura para un nodo de la pila enlazada
typedef struct NodoPila
{
    TipoDatoPilaEnlazada dato;
    struct NodoPila* siguiente;
} NodoPila;

// Estructura para la pila enlazada
typedef struct PilaLista
{
    NodoPila* pCima; // Puntero al nodo superior (primer nodo de la lista)
    int cantidad;    // Número de elementos en la pila
} PilaEnlazada;

Operaciones Básicas de una Pila Enlazada

Aquí se proporciona la implementación en C para las operaciones de una pila enlazada, incluyendo inicialización, destrucción, apilar, desapilar, obtención del elemento superior, verificación de vacía y tamaño.

// Inicializa una pila enlazada
void InicializarPilaEnlazada(PilaEnlazada* pPila)
{
    assert(pPila);
    pPila->pCima = NULL; // La cima está vacía al inicio
    pPila->cantidad = 0;
}

// Destruye una pila enlazada, liberando todos los nodos
void DestruirPilaEnlazada(PilaEnlazada* pPila)
{
    assert(pPila);
    NodoPila* actual = pPila->pCima;
    while (actual != NULL)
    {
        NodoPila* proximo = actual->siguiente;
        free(actual);
        actual = proximo;
    }
    pPila->pCima = NULL;
    pPila->cantidad = 0;
}

// Apila un elemento en la cima de la pila (inserción al principio de la lista)
void ApilarEnlazada(PilaEnlazada* pPila, TipoDatoPilaEnlazada valor)
{
    assert(pPila);
    NodoPila* nuevoNodo = (NodoPila*)malloc(sizeof(NodoPila));
    if (nuevoNodo == NULL)
    {
        perror("Error de asignación de memoria para nuevo nodo!\n");
        exit(EXIT_FAILURE);
    }
    nuevoNodo->dato = valor;
    nuevoNodo->siguiente = pPila->pCima; // El nuevo nodo apunta al antiguo nodo superior
    pPila->pCima = nuevoNodo;           // El nuevo nodo se convierte en la cima
    pPila->cantidad++;
}

// Desapila un elemento de la cima de la pila (eliminación al principio de la lista)
void DesapilarEnlazada(PilaEnlazada* pPila)
{
    assert(pPila && pPila->pCima); // Asegura que la pila no esté vacía
    NodoPila* nodoARetirar = pPila->pCima;
    pPila->pCima = pPila->pCima->siguiente; // El siguiente nodo se convierte en la nueva cima
    free(nodoARetirar);                      // Libera la memoria del nodo retirado
    pPila->cantidad--;
}

// Obtiene el elemento en la cima de la pila sin eliminarlo
TipoDatoPilaEnlazada ObtenerCimaEnlazada(PilaEnlazada* pPila)
{
    assert(pPila && pPila->pCima); // Asegura que la pila no esté vacía
    return pPila->pCima->dato;
}

// Verifica si la pila está vacía
bool EstaVaciaEnlazada(PilaEnlazada* pPila)
{
    assert(pPila);
    return pPila->pCima == NULL;
}

// Obtiene el número de elementos en la pila
int ObtenerTamanoEnlazada(PilaEnlazada* pPila)
{
    assert(pPila);
    return pPila->cantidad;
}

La Cola (Queue): El Principio FIFO (First In, First Out)

Una Cola es otra estructura de datos lineal crucial que se adhiere estrictamente al principio "primero en entrar, primero en salir" (FIFO). Imagina una fila en el supermercado: el primero en llegar es el primero en ser atendido y en salir. Las operaciones se realizan en extremos opuestos.

• Cabeza (Front / Head): El extremo por donde se eliminan los elementos (desencolar).
• Cola (Rear / Tail): El extremo por donde se insertan los elementos (encolar).
• Encolar (Enqueue / Push): Añadir un elemento al final de la cola.
• Desencolar (Dequeue / Pop): Retirar un elemento del principio de la cola.

Nota importante: Implementar una cola utilizando un array tradicional (almacenamiento secuencial) es complejo y propenso a problemas como el "falso desbordamiento" (cuando hay espacio libre pero no se puede insertar más) y operaciones de desencolado ineficientes (O(N) debido al desplazamiento de elementos). Por esta razón, las colas suelen implementarse de forma más eficiente usando listas enlazadas o arrays circulares.

Cola con Almacenamiento Enlazado (Basada en Lista Enlazada)

Definición de la Estructura para Cola Enlazada

Una cola enlazada utiliza una lista enlazada para su implementación. Para garantizar una eficiencia O(1) en ambas operaciones (encolar y desencolar), se emplean dos punteros:

• Puntero a la Cabeza (pCabeza): Apunta al primer elemento de la cola, facilitando la operación de desencolado.
• Puntero a la Cola (pFinal): Apunta al último elemento de la cola, facilitando la operación de encolado.

// Define el tipo de dato que almacenará la cola
typedef int TipoDatoCola;

// Estructura para un nodo de la cola enlazada
typedef struct NodoCola
{
    TipoDatoCola dato;
    struct NodoCola* siguiente;
} NodoCola;

// Estructura para la cola enlazada
typedef struct ColaLista
{
    NodoCola* pCabeza; // Puntero al nodo de la cabeza (frente)
    NodoCola* pFinal;  // Puntero al nodo del final (cola)
    int tamano;        // Número de elementos en la cola
} ColaEnlazada;

Operaciones Básicas de una Cola Enlazada

La implementación en C de las operaciones básicas para una cola enlazada (inicialización, destrucción, encolar, desencolar, obtener frente/final, verificar si está vacía y tamaño) es sencilla, asemejándose a las operaciones fundamentales de una lista enlazada.

// Inicializa una cola enlazada
void InicializarColaEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    pCola->pCabeza = NULL; // La cabeza y el final están vacíos al inicio
    pCola->pFinal = NULL;
    pCola->tamano = 0;
}

// Destruye una cola enlazada, liberando todos los nodos
void DestruirColaEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    NodoCola* actual = pCola->pCabeza;
    while (actual != NULL)
    {
        NodoCola* proximo = actual->siguiente;
        free(actual);
        actual = proximo;
    }
    pCola->pCabeza = pCola->pFinal = NULL;
    pCola->tamano = 0;
}

// Encola un elemento al final de la cola (inserción al final de la lista)
void EncolarEnlazada(ColaEnlazada* pCola, TipoDatoCola valor)
{
    assert(pCola);
    NodoCola* nuevoNodo = (NodoCola*)malloc(sizeof(NodoCola));
    if (nuevoNodo == NULL)
    {
        perror("Error de asignación de memoria para nuevo nodo!\n");
        exit(EXIT_FAILURE);
    }
    nuevoNodo->dato = valor;
    nuevoNodo->siguiente = NULL; // El nuevo nodo siempre va al final

    if (pCola->pFinal == NULL) // Si la cola está vacía
    {
        pCola->pCabeza = pCola->pFinal = nuevoNodo; // El nuevo nodo es cabeza y final
    }
    else
    {
        pCola->pFinal->siguiente = nuevoNodo; // El actual final apunta al nuevo nodo
        pCola->pFinal = nuevoNodo;           // El nuevo nodo se convierte en el final
    }
    pCola->tamano++;
}

// Desencola un elemento del principio de la cola (eliminación al principio de la lista)
void DesencolarEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    assert(!EstaVaciaEnlazada(pCola)); // Asegura que la cola no esté vacía

    NodoCola* nodoARetirar = pCola->pCabeza;
    pCola->pCabeza = pCola->pCabeza->siguiente; // El siguiente nodo se convierte en la nueva cabeza
    
    // Si la cabeza se vuelve NULL, la cola está vacía, también el final debe ser NULL
    if (pCola->pCabeza == NULL)
    {
        pCola->pFinal = NULL;
    }
    free(nodoARetirar); // Libera la memoria del nodo retirado
    pCola->tamano--;
}

// Obtiene el elemento al frente de la cola sin eliminarlo
TipoDatoCola ObtenerFrenteEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    assert(!EstaVaciaEnlazada(pCola));
    return pCola->pCabeza->dato;
}

// Obtiene el elemento al final de la cola sin eliminarlo
TipoDatoCola ObtenerFinalEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    assert(!EstaVaciaEnlazada(pCola));
    return pCola->pFinal->dato;
}

// Verifica si la cola está vacía
bool EstaVaciaEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    return pCola->pCabeza == NULL;
}

// Obtiene el número de elementos en la cola
int ObtenerTamanoColaEnlazada(ColaEnlazada* pCola)
{
    assert(pCola);
    return pCola->tamano;
}

Cola Circular

Definición de la Estructura para Cola Circular

Aunque las colas enlazadas son flexibles, en escenarios donde se requiere alta eficiencia y contigüidad de memoria, una implementación basada en array es deseable. Para superar los problemas de "falso desbordamiento" y movimiento ineficiente de elementos en las colas de array tradicionales, se utiliza la Cola Circular.

Una cola circular trata los extremos de un array como conectados, formando un bucle. Cuando el puntero de cola llega al final del array, "envuelve" al principio, reutilizando el espacio de manera eficiente. Aquí, frente apunta al primer elemento y final apunta a la próxima posición disponible para insertar.

El movimiento de los punteros frente y final se realiza mediante la operación de módulo (%). El resultado de (indice + 1) % MAXSIZE asegura que el índice siempre permanezca dentro del rango del array y se "reinicie" a 0 cuando alcanza el final.

• Inicialización: obj->frente = 0; obj->final = 0;
• Avanzar Frente: obj->frente = (obj->frente + 1) % (obj->capacidadMaxima + 1);
• Avanzar Final: obj->final = (obj->final + 1) % (obj->capacidadMaxima + 1);
• Longitud de la Cola: (obj->final - obj->frente + obj->capacidadMaxima + 1) % (obj->capacidadMaxima + 1);

Un desafío clave es distinguir entre una cola vacía y una cola llena, ya que en ambas situaciones frente == final. Las soluciones comunes incluyen:

1. Sacrificar un espacio: El array tiene una capacidad real de K+1, pero solo almacena K elementos. La condición para estar llena es (final + 1) % (K + 1) == frente. La condición para estar vacía es frente == final. (Este es el método más común y el que se ilustra aquí).
2. Mantener una cuenta de elementos (tamano): Se usa una variable adicional para rastrear el número de elementos. Llena: tamano == CapacidadMaxima. Vacía: tamano == 0.
3. Usar una bandera de estado (tag): Una variable booleana indica la última operación (inserción o eliminación) para desambiguar frente == final.

// Estructura para la cola circular (k es la capacidad máxima solicitada por el usuario)
typedef struct 
{
    int* datosArray;      // Array para almacenar los elementos
    int frente;          // Puntero al índice del primer elemento
    int final;           // Puntero al índice del próximo espacio disponible
    int capacidadMaxima; // Capacidad definida por el usuario (sin contar el espacio sacrificado)
} ColaCircular;

Operaciones Básicas de una Cola Circular

// Declaraciones de funciones auxiliares (para mantener la coherencia)
bool estaVaciaColaCircular(ColaCircular* obj);
bool estaLlenaColaCircular(ColaCircular* obj);

// Crea una cola circular con una capacidad 'k'
ColaCircular* crearColaCircular(int k)
{
    ColaCircular* obj = (ColaCircular*)malloc(sizeof(ColaCircular));
    if (obj == NULL) {
        perror("Error de asignación de memoria para ColaCircular!\n");
        exit(EXIT_FAILURE);
    }
    // Se asigna k+1 espacios para permitir distinguir entre llena y vacía
    obj->datosArray = (int*)malloc((k + 1) * sizeof(int)); 
    if(obj->datosArray == NULL)
    {
        perror("Error de asignación de memoria para datosArray!\n");
        free(obj); // Libera obj si falla la segunda asignación
        exit(EXIT_FAILURE);
    }
    obj->frente = 0; // Punteros inicializados a 0
    obj->final = 0;
    obj->capacidadMaxima = k; // Capacidad lógica
    return obj;
}

// Encola un elemento en la cola circular
bool encolarColaCircular(ColaCircular* obj, int valor)
{
    if(estaLlenaColaCircular(obj)) // Primero verifica si la cola está llena
    {
        return false;
    }
    obj->datosArray[obj->final] = valor;
    obj->final = (obj->final + 1) % (obj->capacidadMaxima + 1); // Avanza 'final' cíclicamente
    return true;
}

// Desencola un elemento de la cola circular
bool desencolarColaCircular(ColaCircular* obj)
{
    if(estaVaciaColaCircular(obj)) // Primero verifica si la cola está vacía
    {
        return false;
    }
    obj->frente = (obj->frente + 1) % (obj->capacidadMaxima + 1); // Avanza 'frente' cíclicamente
    return true;
}

// Obtiene el elemento del frente de la cola
int obtenerFrenteColaCircular(ColaCircular* obj)
{
    if(estaVaciaColaCircular(obj))
    {
        return -1; // Retorna -1 si la cola está vacía (o lanza un error)
    }
    return obj->datosArray[obj->frente];
}

// Obtiene el elemento del final de la cola
int obtenerFinalColaCircular(ColaCircular* obj)
{
    if(estaVaciaColaCircular(obj))
    {
        return -1; // Retorna -1 si la cola está vacía (o lanza un error)
    }
    // 'final' apunta al próximo espacio libre, así que el último elemento es el anterior
    // Se añade (obj->capacidadMaxima + 1) para manejar correctamente el módulo si (obj->final - 1) es negativo
    return obj->datosArray[(obj->final - 1 + obj->capacidadMaxima + 1) % (obj->capacidadMaxima + 1)];  
}

// Verifica si la cola circular está vacía (frente y final coinciden)
bool estaVaciaColaCircular(ColaCircular* obj)
{
    return obj->frente == obj->final;
}

// Verifica si la cola circular está llena (el siguiente de 'final' es 'frente')
bool estaLlenaColaCircular(ColaCircular* obj)
{
    return (obj->final + 1) % (obj->capacidadMaxima + 1) == obj->frente;    
}

// Libera los recursos de la cola circular
void liberarColaCircular(ColaCircular* obj)
{
    free(obj->datosArray);
    free(obj);    
}

Ejercicios Prácticos con Pilas y Colas

La mejor manera de consolidar el conocimiento de estas estructuras es a través de la práctica. Los siguientes problemas clásicos te ayudarán a comprender la versatilidad y las aplicaciones de pilas y colas.

Implementar una Pila Usando Dos Colas

El desafío es simular una pila (LIFO) utilizando únicamente las operaciones permitidas en colas (FIFO): encolar, desencolar, obtener frente/final, y verificar si está vacía. Esto se logra manteniendo los elementos en un orden "invertido" entre dos colas.

• Apilar (Push): Se inserta el nuevo elemento en la cola no vacía. Si ambas están vacías, se inserta en cualquiera.
• Desapilar (Pop): Para obtener el "último" elemento (según la lógica LIFO), se transfieren todos menos el último elemento de la cola no vacía a la cola vacía. El elemento restante en la cola original es el que se desapila.
• Obtener Cima (Top): Similar a desapilar, pero sin eliminar el elemento.

// Define el tipo de dato para los elementos de la cola
typedef int TipoElementoCola;

// Nodo para la lista enlazada interna de la cola
typedef struct NodoEnlaceCola
{
    TipoElementoCola dato;
    struct NodoEnlaceCola* siguiente;
} NodoEnlaceCola;

// Estructura de la cola simple para el ejercicio
typedef struct EstructuraCola
{
    NodoEnlaceCola* frente;
    NodoEnlaceCola* final;
    int conteo; // Número de elementos
} ColaSimple;

// Declaraciones de funciones para ColaSimple
void InicializarColaSimple(ColaSimple* c);
void EncolarSimple(ColaSimple* c, TipoElementoCola valor);
void DesencolarSimple(ColaSimple* c);
TipoElementoCola ObtenerFrenteSimple(ColaSimple* c);
TipoElementoCola ObtenerFinalSimple(ColaSimple* c);
bool EstaVaciaColaSimple(ColaSimple* c);
int ObtenerConteoSimple(ColaSimple* c);
void DestruirColaSimple(ColaSimple* c);

// Implementación de las funciones de ColaSimple (simplificada para el ejercicio)
void InicializarColaSimple(ColaSimple* c)
{	
	assert(c);
	c->frente = NULL;
	c->final = NULL;
	c->conteo = 0;
}

void EncolarSimple(ColaSimple* c, TipoElementoCola valor)
{
	assert(c);
	NodoEnlaceCola* nuevoNodo = (NodoEnlaceCola*)malloc(sizeof(NodoEnlaceCola));
	if (nuevoNodo == NULL)
	{
		perror("Error malloc en EncolarSimple!\n");
		exit(EXIT_FAILURE);
	}
	nuevoNodo->dato = valor;
	nuevoNodo->siguiente = NULL;
	if (c->final == NULL)
	{
		c->frente = c->final = nuevoNodo;
	}
	else
	{
		c->final->siguiente = nuevoNodo;
		c->final = nuevoNodo;
	}
	c->conteo++;
}

bool EstaVaciaColaSimple(ColaSimple* c)
{
	assert(c);
	return c->frente == NULL;
}

void DesencolarSimple(ColaSimple* c)
{
	assert(c);
	assert(!EstaVaciaColaSimple(c));
	if (c->frente == c->final) // Si solo hay un elemento
	{
		free(c->frente);
		c->frente = c->final = NULL;
	}
	else
	{
		NodoEnlaceCola* nodoTemp = c->frente->siguiente;
		free(c->frente);
		c->frente = nodoTemp;
	}
	c->conteo--;
}

TipoElementoCola ObtenerFrenteSimple(ColaSimple* c)
{
	assert(c);
	assert(!EstaVaciaColaSimple(c));
	return c->frente->dato;
}

TipoElementoCola ObtenerFinalSimple(ColaSimple* c)
{
	assert(c);
	assert(!EstaVaciaColaSimple(c));
	return c->final->dato;
}

int ObtenerConteoSimple(ColaSimple* c)
{
	assert(c);
	return c->conteo;
}

void DestruirColaSimple(ColaSimple* c)
{
	assert(c);
	NodoEnlaceCola* actual = c->frente;
	while (actual)
	{
		NodoEnlaceCola* proximo = actual->siguiente;
		free(actual);
		actual = proximo;
	}
	c->frente = c->final = NULL;
	c->conteo = 0;
}

// Estructura de la Pila implementada con dos colas
typedef struct 
{
    ColaSimple colaPrincipal;
    ColaSimple colaAuxiliar;    
} MiPilaConColas;

// Crea una nueva pila
MiPilaConColas* crearMiPilaConColas()
{
    MiPilaConColas* pila = (MiPilaConColas*)malloc(sizeof(MiPilaConColas));
    if (pila == NULL) {
        perror("Error malloc en crearMiPilaConColas!\n");
        exit(EXIT_FAILURE);
    }
    InicializarColaSimple(&(pila->colaPrincipal));
    InicializarColaSimple(&(pila->colaAuxiliar)); 
    return pila;   
}

// Apila un elemento 'x'
void apilarMiPilaConColas(MiPilaConColas* pila, int x)
{
    // El elemento se inserta en la cola que no esté vacía
    if(!EstaVaciaColaSimple(&(pila->colaPrincipal)))
    {
        EncolarSimple(&(pila->colaPrincipal), x);
    }
    else
    {
        EncolarSimple(&(pila->colaAuxiliar), x);
    }
}

// Desapila y retorna el elemento superior
int desapilarMiPilaConColas(MiPilaConColas* pila)
{
    ColaSimple* colaActiva = NULL;
    ColaSimple* colaPasiva = NULL;

    // Identifica qué cola contiene elementos
    if(!EstaVaciaColaSimple(&(pila->colaPrincipal)))
    {
        colaActiva = &(pila->colaPrincipal);
        colaPasiva = &(pila->colaAuxiliar);
    }
    else if (!EstaVaciaColaSimple(&(pila->colaAuxiliar)))
    {
        colaActiva = &(pila->colaAuxiliar);
        colaPasiva = &(pila->colaPrincipal);
    } else {
        // La pila está vacía, no se puede desapilar
        // En un caso real, se manejaría un error o se devolvería un valor sentinel.
        assert(false && "La pila está vacía, no se puede desapilar.");
        return -1; 
    }

    // Mueve todos los elementos excepto el último de la cola activa a la cola pasiva
    while(ObtenerConteoSimple(colaActiva) > 1)
    {
        EncolarSimple(colaPasiva, ObtenerFrenteSimple(colaActiva));
        DesencolarSimple(colaActiva);
    }
    
    // El último elemento de la cola activa es el que debe ser desapilado
    int valorDesapilado = ObtenerFrenteSimple(colaActiva);
    DesencolarSimple(colaActiva);
    
    return valorDesapilado;
}

// Retorna el elemento superior sin eliminarlo
int verCimaMiPilaConColas(MiPilaConColas* pila) 
{
    if(!EstaVaciaColaSimple(&(pila->colaPrincipal)))
    {
        return ObtenerFinalSimple(&(pila->colaPrincipal)); // En esta implementación, la cima es el final de la cola activa
    }
    else if (!EstaVaciaColaSimple(&(pila->colaAuxiliar)))
    {
        return ObtenerFinalSimple(&(pila->colaAuxiliar));
    }
    // La pila está vacía
    assert(false && "La pila está vacía, no hay cima.");
    return -1;
}

// Verifica si la pila está vacía
bool estaVaciaMiPilaConColas(MiPilaConColas* pila)
{ 
    return EstaVaciaColaSimple(&(pila->colaPrincipal)) && EstaVaciaColaSimple(&(pila->colaAuxiliar));
}

// Libera los recursos de la pila
void liberarMiPilaConColas(MiPilaConColas* pila)
{
    DestruirColaSimple(&(pila->colaPrincipal));
    DestruirColaSimple(&(pila->colaAuxiliar));
    free(pila);
}

Implementar una Cola Usando Dos Pilas

Este ejercicio consiste en construir una cola (FIFO) utilizando únicamente las operaciones de pila (apilar, desapilar, obtener cima, y verificar si está vacía).

• Encolar (Push): Los elementos se apilan directamente en la pila de entrada.
• Desencolar (Pop): Si la pila de salida contiene elementos, significa que ya están en el orden correcto de cola, así que simplemente se desapila de allí. Si la pila de salida está vacía, se transfieren todos los elementos de la pila de entrada a la pila de salida (lo que invierte su orden, colocándolos en orden FIFO), y luego se desapila de la pila de salida.
• Ver Frente (Peek): Similar a desencolar, pero solo obteniendo el valor.

// Define el tipo de dato para los elementos de la pila
typedef int TipoElementoPilaArray;

// Estructura de la Pila simple basada en array para el ejercicio
typedef struct PilaArraySimple
{
	TipoElementoPilaArray* arr;
	int contadorElementos; // Apunta al siguiente espacio disponible (también el tamaño)
	int capActual;
} PilaSimpleArray;

// Declaraciones de funciones para PilaSimpleArray
void InicializarPilaSimpleArray(PilaSimpleArray* p);		
void DestruirPilaSimpleArray(PilaSimpleArray* p);	
void ApilarSimpleArray(PilaSimpleArray* p, TipoElementoPilaArray valor);
void DesapilarSimpleArray(PilaSimpleArray* p);
TipoElementoPilaArray ObtenerCimaSimpleArray(PilaSimpleArray* p);
bool EstaVaciaPilaSimpleArray(PilaSimpleArray* p);
int ObtenerTamanoPilaSimpleArray(PilaSimpleArray* p);

// Implementación de las funciones de PilaSimpleArray
void InicializarPilaSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	p->arr = NULL;
	p->contadorElementos = 0;
	p->capActual = 0;
}

void DestruirPilaSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	free(p->arr);
	p->arr = NULL;
	p->contadorElementos = 0;
	p->capActual = 0;
}

void ApilarSimpleArray(PilaSimpleArray* p, TipoElementoPilaArray valor)
{
	assert(p);
	if (p->contadorElementos == p->capActual)
	{
		int nuevaCapacidad = p->capActual == 0 ? 4 : (p->capActual * 2);
		TipoElementoPilaArray* temp = (TipoElementoPilaArray*)realloc(p->arr, nuevaCapacidad * sizeof(TipoElementoPilaArray));
		if (temp == NULL)
		{
			perror("Error realloc en ApilarSimpleArray!\n");
			return;
		}
		p->arr = temp;
		p->capActual = nuevaCapacidad;
	}
	p->arr[p->contadorElementos] = valor;
	p->contadorElementos++;
}

void DesapilarSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	assert(p->contadorElementos > 0);
	p->contadorElementos--;
}

TipoElementoPilaArray ObtenerCimaSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	assert(p->contadorElementos > 0);
	return p->arr[p->contadorElementos - 1];
}

bool EstaVaciaPilaSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	return p->contadorElementos == 0;
}

int ObtenerTamanoPilaSimpleArray(PilaSimpleArray* p)
{
	assert(p);
	return p->contadorElementos;
}

// Estructura de la Cola implementada con dos pilas
typedef struct 
{
    PilaSimpleArray pilaEntrada;
    PilaSimpleArray pilaSalida;   
} MiColaConPilas;

// Crea una nueva cola
MiColaConPilas* crearMiColaConPilas()
{
    MiColaConPilas* obj = (MiColaConPilas*)malloc(sizeof(MiColaConPilas));
    if (obj == NULL) {
        perror("Error malloc en crearMiColaConPilas!\n");
        exit(EXIT_FAILURE);
    }
    InicializarPilaSimpleArray(&(obj->pilaEntrada));
    InicializarPilaSimpleArray(&(obj->pilaSalida));
    return obj;    
}

// Encola un elemento 'x'
void encolarMiColaConPilas(MiColaConPilas* obj, int x)
{
    ApilarSimpleArray(&(obj->pilaEntrada), x);
}

// Desencola y retorna el elemento del frente
int desencolarMiColaConPilas(MiColaConPilas* obj)
{
    // Si la pila de salida está vacía, se mueven todos los elementos de la pila de entrada
    if(EstaVaciaPilaSimpleArray(&(obj->pilaSalida)))
    {
        while(!EstaVaciaPilaSimpleArray(&(obj->pilaEntrada)))
        {
            ApilarSimpleArray(&(obj->pilaSalida), ObtenerCimaSimpleArray(&(obj->pilaEntrada)));
            DesapilarSimpleArray(&(obj->pilaEntrada));
        }
    }
    // Si la pila de salida sigue vacía, significa que la cola original estaba vacía
    if(EstaVaciaPilaSimpleArray(&(obj->pilaSalida))) {
        assert(false && "La cola está vacía, no se puede desencolar.");
        return -1;
    }
    int datoDesencolado = ObtenerCimaSimpleArray(&(obj->pilaSalida));
    DesapilarSimpleArray(&(obj->pilaSalida));
    return datoDesencolado;
}

// Retorna el elemento del frente sin eliminarlo
int verFrenteMiColaConPilas(MiColaConPilas* obj)
{
    // Si la pila de salida está vacía, se mueven todos los elementos de la pila de entrada
    if(EstaVaciaPilaSimpleArray(&(obj->pilaSalida)))
    {
        while(!EstaVaciaPilaSimpleArray(&(obj->pilaEntrada)))
        {
            ApilarSimpleArray(&(obj->pilaSalida), ObtenerCimaSimpleArray(&(obj->pilaEntrada)));
            DesapilarSimpleArray(&(obj->pilaEntrada));
        }
    }
    // Si la pila de salida sigue vacía, significa que la cola original estaba vacía
    if(EstaVaciaPilaSimpleArray(&(obj->pilaSalida))) {
        assert(false && "La cola está vacía, no hay frente.");
        return -1;
    }
    return ObtenerCimaSimpleArray(&(obj->pilaSalida));
}

// Verifica si la cola está vacía
bool estaVaciaMiColaConPilas(MiColaConPilas* obj) 
{
    return EstaVaciaPilaSimpleArray(&(obj->pilaEntrada)) && EstaVaciaPilaSimpleArray(&(obj->pilaSalida));
}

// Libera los recursos de la cola
void liberarMiColaConPilas(MiColaConPilas* obj)
{
    DestruirPilaSimpleArray(&(obj->pilaEntrada));
    DestruirPilaSimpleArray(&(obj->pilaSalida));
    free(obj);
}

Problema de Balanceo de Paréntesis

Descripción: Dada una cadena s que contiene solo los caracteres '(', ')', '{', '}', '[' y ']', determina si la cadena de entrada es válida. Una cadena se considera válida si:

1. Todo paréntesis de apertura debe cerrarse con el mismo tipo de paréntesis.
2. Todo paréntesis de apertura debe cerrarse en el orden correcto.
3. Todo paréntesis de cierre tiene un paréntesis de apertura correspondiente del mismo tipo.

Análisis: Una pila es la estructura de datos ideal para resolver este problema, ya que puede actuar como un "contenedor de espera" que garantiza la correcta secuencia de emparejamiento.

• Recorrido de la cadena: Se escanea la cadena de izquierda a derecha, carácter por carácter.
• Paréntesis de apertura: Si se encuentra un paréntesis de apertura (ej., '(', '{', '['), este se apila. Esto indica que esperamos encontrar su correspondiente paréntesis de cierre más adelante.
• Paréntesis de cierre: Si se encuentra un paréntesis de cierre (ej., ')', '}', ']'), se realiza la siguiente verificación:
  • Pila vacía: Si la pila está vacía, significa que no hay un paréntesis de apertura correspondiente para este de cierre, por lo tanto, la cadena es inválida.
  • Pila no vacía: Se desapila el elemento superior de la pila. Se compara si este elemento (el paréntesis de apertura) coincide en tipo con el paréntesis de cierre actual. Si no coinciden (ej., se encuentra ')' pero la cima era '['), la cadena es inválida.
• Fin del recorrido: Una vez que se ha procesado toda la cadena:
  • Pila vacía: Si la pila está vacía, todos los paréntesis de apertura fueron correctamente emparejados y desapilados. La cadena es válida.
  • Pila no vacía: Si la pila contiene elementos, significa que quedaron paréntesis de apertura sin cerrar. La cadena es inválida.