Filas

Tempo de espera na fila do banco

Criação de um programação com a utilização de fila, para descobrir quantos clientes de uma agência bancária teriam que esperar mais do que 20 minutos na fila do banco.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

Sem medo de errar 

Você foi encarregado de resolver um problema em seu novo emprego, que consiste em criar um programa para descobrir quantos clientes de uma agência bancária teriam que esperar mais do que 20 minutos na fila do banco, contrariando, assim, a nova legislação brasileira. Para isso, você tem como informações a quantidade de clientes e, para cada cliente, o momento que ele entrou na fila o tempo necessário para seu atendimento.

Para resolver esse problema, vamos iniciar lendo o número de clientes que entrarão na agência. Logo depois, você pode adicionar suas informações, uma a uma, em duas filas. Na primeira fila, armazenaremos o tempo em que o cliente entrou na fila. Na segunda, será armazenado o tempo necessário para seu atendimento. Observe parte da solução no Código 4.33 a seguir.

int main() {
    int numClientes, tEntrada, tAtendimento;
    printf("Informe o número de clientes: ");
    scanf("%d", &numClientes);

    struct Fila* filaTEntrada = criar();
    struct Fila* filaTAtendimento = criar();
    
    for(int i = 0; i < numClientes; i++) {
        printf("\nInforme o tempo em que o cliente %d entrou na fila: ", i + 1);
        scanf("%d", &tEntrada);
        enfileirar(filaTEntrada, tEntrada);
        
        printf("\nInforme o tempo de atendimento do cliente %d: ", i + 1);
        scanf("%d", &tAtendimento);
        enfileirar(filaTEntrada, tAtendimento);
        
        printf("\n");
    }
    return 0;
}

Após isso, vamos criar uma função que recebe as duas filas como parâmetros e retorna um número inteiro, representando a quantidade de clientes que terão que esperar mais do que 20 minutos na fila.

int calcularClientesEmEsperaMaxima(struct Fila* filaTEntrada, struct Fila* filaTAtendimento) {
    
    int esperaTotal = 0;
    int clientesEmEsperaMaxima = 0;
    
    while(!vazia(filaTEntrada)) {
        int tEntrada = desenfileirar(filaTEntrada);
        int tAtendimento = desenfileirar(filaTAtendimento);
    
        if (esperaTotal - tEntrada > 20) {
            clientesEmEsperaMaxima += 1;
        }

        esperaTotal += tAtendimento;
    }    
    
    return clientesEmEsperaMaxima;
}

Entre as linhas 6 e 15, os elementos das filas são removidos e o seguinte cálculo é feito: para cada cliente, subtrai-se o tempo de espera total (que é acumulado na linha 14, somando-se o tempo de atendimento de cada cliente) do tempo de entrada do cliente na fila. Por exemplo: supondo que um cliente seja o quarto a ser atendido e que os três antes dele apresentam tempo de atendimento de 10 minutos, ele teria que ficar esperando por 30 minutos, caso tenha chegado no minuto 0. Supondo, entretanto, que ele tenha chegado no minuto 10, seu tempo de espera será de 20 minutos.

Então, nas linhas 10 a 12, verificamos se o tempo de espera do cliente será maior do que 20 minutos. Caso sim, o valor da variável “cientesEmEsperaMaxima” é incrementado de 1. Ao final, o valor dessa variável é retornado para quem chamou a função (linha 17).

O código completo, incluindo a chamada na função “calcularClientesEmEsperaMaxima” é apresentado a seguir:

int calcularClientesEmEsperaMaxima(struct Fila* filaTEntrada, struct Fila* filaTAtendimento) {
    
    int esperaTotal = 0;
    int clientesEmEsperaMaxima = 0;
    
    while(!vazia(filaTEntrada)) {
        int tEntrada = desenfileirar(filaTEntrada);
        int tAtendimento = desenfileirar(filaTAtendimento);
    
        if (esperaTotal - tEntrada > 20) {
            clientesEmEsperaMaxima += 1;
        }

        esperaTotal += tAtendimento;
    }    
    
    return clientesEmEsperaMaxima;
}

int main() {
    int numClientes, tEntrada, tAtendimento, clientesEmEsperaMaxima;
    
    printf("Informe o número de clientes: ");
    scanf("%d", &numClientes);

    struct Fila* filaTEntrada = criar();
    struct Fila* filaTAtendimento = criar();
    
    for(int i = 0; i < numClientes; i++) {
        printf("\nInforme o tempo em que o cliente %d entrou na fila: ", i + 1);
        scanf("%d", &tEntrada);
        enfileirar(filaTEntrada, tEntrada);
        
        printf("\nInforme o tempo de atendimento do cliente %d: ", i + 1);
        scanf("%d", &tAtendimento);
        enfileirar(filaTAtendimento, tAtendimento);
        
        printf("\n");
    }
    
    clientesEmEsperaMaxima = calcularClientesEmEsperaMaxima(filaTEntrada, filaTAtendimento);
    printf("\nNeste dia, %d cliente(s) esperarão mais do que 20 minutos na fila.", clientesEmEsperaMaxima);

    return 0;
}

 Você pode testar a solução completa utilizando a ferramenta Paiza.io.

Avançando na prática

O problema de Josephus

São inúmeras as aplicações da ED Fila. Nesta seção, você vai conhecer o problema clássico conhecido como o problema de Josephus. Esse problema postula um grupo de soldados circundados por uma força inimiga esmagadora. Não há esperanças de vitória sem a chegada de reforços e existe somente um cavalo disponível para escapar. Os soldados entram em um acordo para determinar qual deles deverá escapar e trazer ajuda. Eles formam um círculo e um número N é sorteado em um chapéu. Um de seus nomes também é sorteado. Iniciando pelo soldado cujo nome foi sorteado, eles começam a contar ao longo do círculo em sentido horário. Quando a contagem alcança N, esse soldado é retirado do círculo e a contagem reinicia com o soldado seguinte. O processo continua de maneira que, toda vez que N é alcançado, outro soldado é retirado do círculo. Todo soldado retirado do círculo não entra mais na contagem. O último soldado que restar deverá montar no cavalo e escapar. Com base nesse contexto, crie uma função que, dada uma fila de soldados e um número N, o retorne o soldado que escapará.

Resolução

Você foi encarregado de resolver o tradicional problema de Josephus. Na prática, você deve criar uma função que, dada uma fila de soldados (representados por números inteiros) e um número inteiro N, sua função retorne o número do soldado que escapará para pedir ajuda contra o exército inimigo.

Utilizando a ED, a situação-problema pode ser resolvida da seguinte forma:

int josephus(struct Fila* f, int n) {
    while(tamanho(f) > 1) {
        for(int i = 0; i < n; i++) { 
            enfileirar(f, desenfileirar(f));
        } 
        desenfileirar(f);
    }
    return desenfileirar(f);
}

int main() {
    struct Fila* minha_fila = criar();
    enfileirar(minha_fila, 1);
    enfileirar(minha_fila, 2);
    enfileirar(minha_fila, 3);
    enfileirar(minha_fila, 3);
    printf("Soldado salvo: %d ", josephus(minha_fila, 3));
    liberar(minha_fila);

    return 0;
}

 Teste o código utilizando a ferramenta Paiza.io.

A função “josephus” recebe uma fila “f”, contendo todos os soldados, e um número inteiro “n”. A partir disso, cria-se um laço while que irá iterar enquanto o tamanho da fila for maior do que 1 (linha 2). Isso é feito porque a ideia do problema é ir removendo os soldados um a um até que sobre apenas 1. Uma vez terminada a execução do laço while, sabe-se que resta apenas um soldado na fila, a saber, aquele que será salvo. Portanto, na linha 8 remove e retorna-se o valor do único elemento da fila como resultado do problema de Josephus.

Dentro do laço while, há um laço for (linha 3), que é responsável por iterar na fila até encontrar o elemento que será removido. Esse laço fará sempre “n” iterações e, em cada uma delas, um elemento será removido da fila e reinserido nela. Como o protocolo da fila é FIFO, então cada elemento será retirado do início e inserido no final dela. Assim que o contato “i” do laço for atingir o valor igual a “n”, o laço é interrompido. Isso indica que o soldado a ser retirado encontra-se no início da fila. Então, basta removê-lo, conforme mostra a linha 6.

A função “”main” simplesmente cria uma lista vazia (12) e insere 4 elementos nela (linhas 13 a 16). Após isso, é invocada a função “josephus”, passando a fila criada como parâmetro e o valor de “n” igual a 3. A saída esperada desse código é “Soldado salvo: 2”.