Dando continuidade ao nosso Curso de Programação C, nesta aula vamos aprender como implementar a estrutura de dados fila de prioridade.

Como exemplo vamos simular uma fila de prioridade por idade semelhante às tantas filas que vemos no dia a dia. Assim, se a pessoa a ser inserida tiver uma idade menor que 60 anos, então ela será inserido no final da fila, caso contrário, será inserida no início da fila após a última prioridade, caso já exista alguma.

No trecho de código a seguir implementamos esse processo. Alocamos um novo Nó e verificamos se a fila está vazia. Caso a fila esteja vazia, então este novo nó será o primeiro nó da fila. Contudo, se a fila não estiver vazia, precisamos então verificar se o elemento a ser inserido é uma prioridade.

Se o novo nó for uma prioridade, perceba que ainda existem duas possibilidades: pode ser que esta seja a primeira prioridade, então teremos uma inserção no início da fila; ou pode ser que já exista alguma prioridade na fila, então teremos uma inserção no meio da fila, após a última prioridade.

Caso não seja uma prioridade, basta percorrer a fila até o final e inserir o novo nó. Perceba que esta inserção poderia ser direta se existisse um ponteiro para o fim da fila, dispensando a necessidade de caminhar na fila até o final.

/*
   Função para inserir com prioridade por idade
*/
void inserir_com_prioridade(No **fila, int num){
    No *aux, *novo = malloc(sizeof(No));
    if(novo){
        novo->valor = num;
        novo->proximo = NULL;
        if(*fila == NULL) // a fila está vazia?
            *fila = novo;
        else{
            if(num > 59){ // é prioridade?
                if((*fila)->valor < 60){ // é a primeira prioridade?
                    novo->proximo = *fila; // insere no início da fila
                    *fila = novo;
                }
                else{
                    aux = *fila;
                    while(aux->proximo && aux->proximo->valor > 59)
                        aux = aux->proximo;
                    novo->proximo = aux->proximo; // insere depois da última prioridade
                    aux->proximo = novo;
                }
            }
            else{ // não é prioridade, então insere no final
                aux = *fila;
                while(aux->proximo)
                    aux = aux->proximo;
                aux->proximo = novo;
            }
        }
    }
    else
        printf("\nErro ao alocar memoria.\n");
}

Código completo em C para uma Fila de Prioridade por Idade

/*

        Código escrito por Wagner Gaspar
        Agosto de 2021

        Aula 241: FILA de Prioridade
*/

typedef struct no{
    int valor;
    struct no *proximo;
}No;

void inserir_na_fila(No **fila, int num){
    No *aux, *novo = malloc(sizeof(No));
    if(novo){
        novo->valor = num;
        novo->proximo = NULL;
        if(*fila == NULL)
            *fila = novo;
        else{
            aux = *fila;
            while(aux->proximo)
                aux = aux->proximo;
            aux->proximo = novo;
        }
    }
    else
        printf("\nErro ao alocar memoria.\n");
}

void inserir_com_prioridade(No **fila, int num){
    No *aux, *novo = malloc(sizeof(No));
    if(novo){
        novo->valor = num;
        novo->proximo = NULL;
        if(*fila == NULL)
            *fila = novo;
        else{
            // é prioridade?
            if(num > 59){
                if((*fila)->valor < 60){ // é a primeira prioridade?
                    novo->proximo = *fila; // insere no início da fila
                    *fila = novo;
                }
                else{
                    aux = *fila;
                    while(aux->proximo && aux->proximo->valor > 59)
                        aux = aux->proximo;
                    novo->proximo = aux->proximo; // insere depois da última prioridade
                    aux->proximo = novo;
                }
            }
            else{
                aux = *fila;
                while(aux->proximo)
                    aux = aux->proximo;
                aux->proximo = novo;
            }
        }
    }
    else
        printf("\nErro ao alocar memoria.\n");
}

No* remover_da_fila(No **fila){
    No *remover = NULL;

    if(*fila){
        remover = *fila;
        *fila = remover->proximo;
    }
    else
        printf("\tFila vazia\n");
    return remover;
}

void imprimir(No *fila){
    printf("\t------- FILA --------\n\t");
    while(fila){
        printf("%d ", fila->valor);
        fila = fila->proximo;
    }
    printf("\n\t------- FIM FILA --------\n");
}

int main(){
    No *r, *fila = NULL;
    int opcao, valor;

    do{
        printf("\t0 - Sair\n\t1 - Inserir\n\t2 - Remover\n\t3 - Imprimir\n\t4 - inserir com prioridade\n");
        scanf("%d", &opcao);

        switch(opcao){
        case 1:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_na_fila(&fila, valor);
            break;
        case 2:
            r = remover_da_fila(&fila);
            if(r){
                printf("Removido: %d\n", r->valor);
                free(r);
            }
            break;
        case 3:
            imprimir(fila);
            break;
        case 4:
            printf("Digite um valor: ");
            scanf("%d", &valor);
            inserir_com_prioridade(&fila, valor);
            break;
        default:
            if(opcao != 0)
                printf("\nOpcao invaluda!\n");
        }

    }while(opcao != 0);

    return 0;
}