Visualizador Web de Estructuras de Datos

Cola de Prioridad

Descripcion del TAD

Estructura FIFO por nivel de prioridad: se atiende primero el elemento con menor valor numerico de prioridad y, en empate, se conserva el orden de llegada. La simulacion muestra inserciones ordenadas y el impacto de cada comparacion. La Cola de Prioridad conserva físicamente el orden de llegada. Para atender, recorre esa cadena y selecciona la mayor prioridad lógica (menor número); los empates se resuelven por llegada anterior.

Errores frecuentes

• Dibujar la cadena físicamente ordenada
• Romper el empate por llegada

Controles de ejecucion paso a paso

• Checkbox Interpretar codigo paso a paso: activado muestra toda la traza; desactivado aplica solo el resultado final.
• Botones de ejecucion: Reproducir y Reiniciar.
• Navegacion por traza: Anterior paso y Siguiente paso.
• Velocidad de simulacion: slider de -2x a +2x (0.00x = 1.00x real).
• En modo rapido (checkbox desactivado), el resultado visual final debe coincidir con el ultimo estado de la traza interpretada.
• Al llegar al ultimo paso, Siguiente paso se bloquea hasta cambiar entradas/operacion; Anterior paso se habilita solo cuando ya avanzaste.

Operaciones soportadas

• cp_encolar
• cp_desencolar
• cp_frente
• cp_vaciar

Operaciones pendientes / restricciones

No hay operaciones pendientes para esta estructura en esta fase.

Estructura del TAD en C

struct cp_nodo {
    int valor;
    int prioridad;
    struct cp_nodo *sgte;
};

typedef struct cp_nodo CPNodo;

typedef struct {
    CPNodo *delante;  
    CPNodo *atras;    
    int cantidad;    
} ColaPrioridad;

Metodos del TAD en C

Codigo C: encolar(valor, prioridad)

Crea nodo nuevo y lo conecta al final; si la cola estaba vacia actualiza tanto frente como final.

/**
 * @brief Encola un elemento con su valor y prioridad asociada.
 *
 * @details
 * Reserva dinámicamente un nuevo @c CPNodo, almacena @p valor y
 * @p prioridad en él y lo enlaza al extremo @c atras de la cola.
 * Si la cola estaba vacía, tanto @c delante como @c atras apuntarán
 * al nuevo nodo. El orden de extracción depende de la prioridad,
 * no del orden de inserción.
 *
 * @param[in,out] cola      Puntero a la ColaPrioridad destino.
 * @param[in]     valor     Dato entero a almacenar.
 * @param[in]     prioridad Número de prioridad (menor valor = mayor prioridad).
 *
 * @return @c true  si el nodo fue creado e insertado correctamente.
 * @return @c false si @p cola es NULL o @c malloc() falla.
 *
 * @pre  La cola debe haber sido inicializada con cp_inicializar().
 * @post El tamaño de la cola aumenta en 1.
 * @note Complejidad temporal: O(1).
 */
bool cp_encolar(ColaPrioridad *cola, int valor, int prioridad) {
    CPNodo *nuevo;
    if (cola == NULL) {
        return false;
    }

    nuevo = cp_crear_nodo(valor, prioridad);
    if (nuevo == NULL) {
        return false;
    }

    if (cola->delante == NULL) {
        cola->delante = nuevo;
    } else {
        cola->atras->sgte = nuevo;
    }
    cola->atras = nuevo;
    cola->cantidad++;
    return true;
}

Codigo C: desencolar

Extrae el nodo del frente, avanza el puntero de frente y ajusta final cuando se elimina el ultimo elemento.

/**
 * @brief Desencola el elemento de mayor prioridad efectiva.
 *
 * @details
 * Recorre toda la cola buscando el nodo con el valor de prioridad más
 * bajo (número más pequeño). En caso de empate extrae el que fue
 * insertado primero (el que aparece antes en la lista).
 * Una vez encontrado, lo desenlaza actualizando @c delante o
 * @c atras según corresponda, escribe sus datos en los punteros
 * @p valor y @p prioridad y libera su memoria.
 *
 * @param[in,out] cola      Puntero a la ColaPrioridad de origen.
 * @param[out]    valor     Puntero donde se escribe el valor del nodo extraído.
 * @param[out]    prioridad Puntero donde se escribe la prioridad extraída.
 *
 * @return @c true  si se extrajo un elemento correctamente.
 * @return @c false si @p cola, @p valor o @p prioridad son NULL,
 *                  o la cola está vacía.
 *
 * @pre  La cola debe contener al menos un elemento.
 * @post El tamaño de la cola disminuye en 1.
 * @note Complejidad temporal: O(n), donde n es el número de elementos.
 */
bool cp_desencolar(ColaPrioridad *cola, int *valor, int *prioridad) {
    CPNodo *actual;
    CPNodo *prev;
    CPNodo *objetivo;
    CPNodo *objetivoPrev;

    if (cola == NULL || cola->delante == NULL || valor == NULL || prioridad == NULL) {
        return false;
    }

    actual = cola->delante;
    prev = NULL;
    objetivo = actual;
    objetivoPrev = NULL;

    while (actual != NULL) {
        if (actual->prioridad < objetivo->prioridad) {
            objetivo = actual;
            objetivoPrev = prev;
        }
        prev = actual;
        actual = actual->sgte;
    }

    if (objetivo == cola->delante) {
        cola->delante = objetivo->sgte;
        if (cola->delante == NULL) {
            cola->atras = NULL;
        }
    } else {
        objetivoPrev->sgte = objetivo->sgte;
        if (cola->atras == objetivo) {
            cola->atras = objetivoPrev;
        }
    }

    *valor = objetivo->valor;
    *prioridad = objetivo->prioridad;
    free(objetivo);
    if (cola->cantidad > 0) {
        cola->cantidad--;
    }
    return true;
}

Codigo C: frente

Consulta el valor del nodo frontal sin modificar enlaces, preservando el estado interno.

bool cp_frente(const ColaPrioridad *cola, int *valor, int *prioridad) {
    const CPNodo *actual;
    const CPNodo *objetivo;
    if (cola == NULL || cola->delante == NULL || valor == NULL || prioridad == NULL) return false;
    objetivo = cola->delante;
    actual = cola->delante->sgte;
    while (actual != NULL) {
        if (actual->prioridad < objetivo->prioridad) objetivo = actual;
        actual = actual->sgte;
    }
    *valor = objetivo->valor;
    *prioridad = objetivo->prioridad;
    return true;
}

Codigo C: limpiar

Recorre la estructura liberando todos los nodos y deja el puntero raiz en estado nulo para reinicio seguro.

/**
 * @brief Elimina todos los elementos de la cola y libera su memoria.
 *
 * @details
 * Recorre la cola desde @c delante hasta el final usando un puntero
 * @c next para guardar el enlace antes de liberar cada @c CPNodo.
 * Al finalizar, @c delante y @c atras quedan en NULL.
 *
 * @param[in,out] cola Puntero a la ColaPrioridad a vaciar.
 *                     Si es NULL la función no hace nada.
 *
 * @post La cola queda en el mismo estado que tras cp_inicializar().
 * @note Complejidad temporal: O(n).
 */
void cp_vaciar(ColaPrioridad *cola) {
    CPNodo *aux;
    CPNodo *next;

    if (cola == NULL) {
        return;
    }

    aux = cola->delante;
    while (aux != NULL) {
        next = aux->sgte;
        free(aux);
        aux = next;
    }

    cola->delante = NULL;
    cola->atras = NULL;
    cola->cantidad = 0;
}

/* Reinicio recomendado del TAD despues de vaciar */
/**
 * @brief Inicializa una ColaPrioridad poniéndola en estado vacío.
 *
 * Establece @c delante y @c atras a NULL. Debe ser la primera llamada
 * antes de operar sobre la cola. No reserva memoria dinámica.
 *
 * @param[out] cola Puntero a la ColaPrioridad que se va a inicializar.
 *                  Si es NULL la función no hace nada.
 *
 * @post La cola queda vacía y lista para usarse.
 */
void cp_inicializar(ColaPrioridad *cola) {
    if (cola == NULL) {
        return;
    }
    cola->delante = NULL;
    cola->atras = NULL;
    cola->cantidad = 0;
}

Ir a la visualizacion