C++ Como fazer uma fila de prioridade

Dcosta7 · 26 de outubro de 2019

O exercício pede para que sejam cadastrados clientes de uma instituição financeira, o cliente digitara se é prioridade ou não. A partir dai, uma opção de atendimento deverá listar os clientes respeitando a ordem de chegada mas, a cada dois clientes sem prioridade deverá chamar um de prioridade.

Dúvida em fazer o programa chamar os clientes na ordem e respeitando o que foi pedido.

código:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#include <windows.h>	 
	struct cadastro {
		char nome[50];
		char prioridade;
		char normal;
		char pri;
	};


int main()
{
	struct cadastro cad[200];
char opc, Ppri[200], Pnormal[200];
int cont=-1, contp=0, j=0, tes=0, tes2=0, i;
contp++;
while (1)
{
	system("cls");
	printf ("\n 1 - INSERIR\n");
	printf ("\n 2 - LISTAR\n");
	printf ("\n 3 - ATENDIMENTO\n");
	printf ("\n 4 - SAIR\n");
	opc=getche();

	if(opc=='1')
	{
		system("cls");
		cont++;	
		printf ("\n digite seu nome:\n");
		fflush(stdin);
		scanf ("%[a-z A-Z]s",&cad[cont].nome);
		printf ("\n prioridade S/N\n");
		cad[cont].prioridade=getche();
		if (cad[cont].prioridade=='n')
		{
			cad[cont].normal=cad[cont].prioridade;
		}
		if (cad[cont].prioridade=='s')
		{
			cad[cont].pri=cad[cont].prioridade;
		}
	}
		if (opc=='2')
	{
		system("cls");
		if (cont==-1)
			printf ("\n nao existe nome cadastrado\n");
		for ( i=0;i<=cont;i++)	
		{
			printf ("\n nome do paciente --> %s\n senha --> %d\n prioridade --> %c   \n", cad[i].nome, i+1, cad[cont].pri, cad[cont].normal );
		}
			system("pause");	
	}
	if(opc=='3')
	{
		system("cls");
		printf ("\n -------PROXIMO--------- \n");
		while (cad[cont].normal!=0 && cad[cont].pri!=0)
	{
		for (int i=0;i<3;i++)
		{
			j=i;
			if (j==2)	
				{
					if (cad[cont].pri==0)
					{
					printf ("\n nome --> %s \n senha --> %d \n prioridade --> %c\n", cad[i].nome, i, cad[i].normal);
					}
					else 
					{
					printf ("\n nome --> %s \n senha --> %d \n prioridade --> %c\n", cad[i].nome, i, cad[i].pri);
					}
				}
				else
				{	
					if (cad[cont].normal==0)
					{
					printf ("\n nome --> %s \n senha --> %d \n prioridade --> %c\n", cad[i].nome, i, cad[i].pri);
					}
					else {
					printf ("\n nome --> %s \n senha --> %d \n prioridade --> %c\n", cad[i].nome,i, cad[i].normal);
					}
				}
		
		}
			j++;
		system("pause");
	}
		}
	if (opc=='4')
	{
		exit(1);
	}
}
return 0;
}

Ansi C · 26 de outubro de 2019

@Dcosta7 , Boa Noite.

Ao invés de usar uma lista com todos, use duas com uma para cada tipo de atendimento.

Dcosta7 · 26 de outubro de 2019

5 minutos atrás, Mauro Britivaldo disse:

@Dcosta7 , Boa Noite.

Ao invés de usar uma lista com todos, use duas com uma para cada tipo de atendimento.

pensei em fazer isso mas não sei como.

arfneto · 26 de outubro de 2019

1 hora atrás, Dcosta7 disse:

o cliente digitara se é prioridade ou não. A partir dai, uma opção de atendimento deverá listar os clientes respeitando a ordem de chegada mas, a cada dois clientes sem prioridade deverá chamar um de prioridade.

Dúvida em fazer o programa chamar os clientes na ordem e respeitando o que foi pedido

Esse é um problema de lógica e não de C ou C# ou C++

Você listou o tema como C++. Em C++ você tem filas e outras estruturas de dados que podem ajudar bem, fazendo quase todo o serviço. Mas a julgar pelo código deve ser em C.

Eu sempre recomendo isso e aqui vou escrever de novo: não acho que deva perder tempo lendo entrada ou criando menus e formatando texto ou cores, ou mesmo deslocando cursor antes de ter a lógica disso funcionando. Vou tentar mostrar mais a seguir.

Estrutura de dados

Quanto mais perto seus dados estiverem do modelo de atendimento mais fácil vai ser programar a solução. Claro que há sempre um milhão de maneiras de tratar isso, mas vou te descrever uma maneira "mais matemática do que programática" de fazer isso. Afinal existe uma disciplina chamada Teoria das Filas até.

1 hora atrás, Dcosta7 disse:

pensei em fazer isso mas não sei como

@Dcosta7 sugeriu usar uma fila para cada atendimento e é perfeitamente possível usar isso. E em seu programa tem dois vetores que parecem indicar que você está fazendo isso. Eu vou sugerir usar uma única fila

Você pode ver as filas de dois lados: do lado do servidor ou do lado do cliente. Você está programando o recurso do lado do servidor. Os outros elementos são o tempo de atendimento e o tempo em si. Algumas regras

A cada dois clientes sem prioridade você deve atender um prioritário
Pode não haver cliente prioritário
Pode haver apenas clientes prioritários
Pode não ter ninguém pra atender

Então se tem alguém pra atender entra a noção da fila de prioridade e você tem que escolher entre as regras mas também entre o mix da fila no momento em que o servidor está livre, o único caixa digamos, por simplicidade.

Se você numerar os atendimentos a partir do início--- e isso é trivial porque estamos usando um computador --- eles vão estar assim 1,2,3,4,5,6,7,8,9,10 e você deve atentar para os atendimentos 3, 6, 9, ... para ver a fila de clientes que solicitaram prioridade.

Mas isso tem uma fórmula:

(numero_do_atendimento % 3 == 0)

Lembro que o operador % --- módulo --- é o resto da divisão do primeiro operando pelo segundo, como

17 % 3 = 2 porque 17 = 3*5 + 2;	// exemplo

Desculpe se estou escrevendo algo óbvio.

Sua estrutura tem uma capacidade, como tem uma capacidade o lugar onde os caras vão ficar na fila. Você está usando 200. Então esse é o limite. Como já alocou os 200 direto pode usar duas variáveis para marcar o óbvio: o início e o final da fila. E usar o índice do vetor como a clássica "senha" do cliente.

Quando você vai atender pode ser uma função

atendimento(numero_do_atendimento, fila) ;

por exemplo. Você incrementa o número e faz aquela conta

(numero_do_atendimento % 3 == 0)

e se for a hora chama o próximo prioritário se tiver algum. Se não for chama o próximo apenas. Por isso sugiro usar uma única fila...

E como controlar os atendimentos e prioridades? Pode ser algo bem ingênuo: não sei de sua familiaridade com estruturas e ponteiros e vetores de mais de uma dimensão então vamos ficar com o minimalista: 200 senhas e um status, onde status pode ser por exemplo 0 para atendimento normal, 1 para atendimento prioritário e -1 para cliente já atendido. Isso já deve ser suficiente para controlar as duas filas (em uma) e as prioridades. E a sua fila tem um ponteiro para o próximo atendimento e para o último atendimento. Dois valores positivos. Algo como:

const int    NORMAL = 0;
const int    PRIORIDADE = 1;
const int    VAGO = -1;

int          fila[200];
int          proximo_cliente = -1;
int          ultimo_cliente = -1;

Porque os dois ponteiros? porque assim você sabe quantos clientes tem na fila a cada momento e pode usar o vetor como circular, para não ter que ficar controlando nada ou deslocando os elementos no vetor.

Ao começar o atendimento você marca todas as posições como VAGO.
Quando alguém entra na fila é cadastrado na próxima posição livre no vetor, e o status normal ou prioritário. Isso é trivial porque é só preencher o índice do vetor correspondente à senha. Com o status correto.
Quando vai haver um atendimento você vê pelo número de atendimento se é hora de buscar preferencialmente alguém com status prioritário. Se tem atende esse e marca lá no vetor como atendido porque pode estar bem adiante na fila, claro.
Se não tem ninguém para atender, não faz nada.
Se estourou a fila para o atendimento até atender alguém. É a realidade

Ao invés de ficar lendo --- porque vai levar uma eternidade para testar a fila como já expliquei ou você já descobriu --- crie uma lista de serviço, como um vetorzinho em main() que entra com os atendimentos e chegadas para você poder progredir rápido, ao invés do menu ultra chato e lerdo. E use uma fila de uns 5 caras no máximo

Se não entendeu o que expliquei, ou não sabe implementar mas se interessou, escreva de novo. É bem simples.

Ansi C · 26 de outubro de 2019

22 horas atrás, Dcosta7 disse:

pensei em fazer isso

Já trabalhavas essa solução no código.

Esqueça a linguagem (por enquanto) se imagine no lugar de um funcionário de uma agencia bancaria designado para fazer esse serviço de lápis e papel na mão (como antigamente sem desperdiçar tempo com cálculos superestimados). Depois de elaborar a lógica pense como o C faria o que você fez manualmente (essa parte pode ser muito difícil então dica: você faz uma pergunta objetivando aquela tarefa que fez com papel e lápis que nós ajudamos um pouco mais com a linguagem).

Não aconselho estudo teórico, complexos e superestimados por enquanto. Nesse momento de Construção do Conhecimento é mais importante foco na lógica das bases. Simule, pra tanto, soluções práticas e manuais.

Fique a vontade e pergunte o quanto precisar.

@Dcosta7 Obrigado.

arfneto · 27 de outubro de 2019

Em 26/10/2019 às 09:42, Mauro Britivaldo disse:

Depois de elaborar a lógica pense como o C faria o que você fez manualmente (essa parte pode ser muito difícil

Em 26/10/2019 às 09:42, Mauro Britivaldo disse:

Não aconselho estudo teórico, complexos e superestimados por enquanto. Nesse momento de Construção do Conhecimento é mais importante foco na lógica das bases

@Mauro Britivaldo

Talvez não tenha notado o significado do título do tópico: Como fazer uma fila de prioridade Essa é a "lógica das bases" nesse caso, imagino, e daí vem o título do tópico.

Isso (fila de prioridade) é um "estudo teórico", mas básico no estudo de estruturas de dados. E é o tópico em questão, como está descrito.

Veja umas referências, como

esse trabalho de Siang Wun Song para justamente um curso de estrutura de dados de uma escola em SP, aqui
ou essa aula em português disponível aqui, aula 24 em português, falando sobre o uso dessas tais filas. É voltado a java mas explica bem o ponto em questão
ou essa aula sobre como usar filas de prioridade para classificar dados --- sort --- e como usar isso para escrever o ultra rápido heap sort aqui, uma aula do MIT que está disponível online junto com todo o curso 6.006 de estruturas de dados. Em inglês, infelizmente.

De volta ao tópico, @Dcosta7eis um resumo da lógica, como já te mostrei

A cada dois clientes sem prioridade você deve atender um prioritário
Pode não haver cliente prioritário
Pode haver apenas clientes prioritários
Pode não ter ninguém pra atender
Ao começar o atendimento você marca todas as posições como VAGO.
Quando alguém entra na fila é cadastrado na próxima posição livre no vetor, e o status normal ou prioritário. Isso é trivial porque é só preencher o índice do vetor correspondente à senha. Com o status correto.
Quando vai haver um atendimento você vê pela ordem dos atendimentos se é hora de buscar alguém com status prioritário. Se tem atende esse e marca lá no vetor como atendido porque pode estar bem adiante na fila, claro.
Se não tem ninguém para atender, não faz nada.
Se estourou a fila para o atendimento até atender alguém. É a realidade

Esse exemplo é um pouco besta, apesar de ser comum: essencialmente essas filas tem dois lados e tem UM PROGRAMA DE CADA LADO e não um menu com as funções para entrar na fila e atender, no mesmo menu. Os usuários chegam e pegam uma senha por exemplo num menu, mas o caixa chama os clientes pelo outro lado. São produtores e consumidores de um mesmo serviço.

Escrevi um exemplo

que você pode ler aqui São só 3 arquivos, um .h e um .c com as rotinas e um outro com um programa pra testar. Ou pode baixar para rodar em sua máquina. Como te disse antes, essa aproximação de ler dados a cada vez durante os testes é um inferno como já deve ter descoberto e demora demais para rodar até mesmo um único modesto ciclo de testes.

Eis o que eu sugiro, e o que eu escrevi ontem: pense em seu menu no meio do caminho entre os caras que chegam e os caras que atendem: são só quatro funções:

Entra alguém, com direito a atendimento prioritário
Entra alguém, sem direito a atendimento prioritário
Atende alguém, seguindo o critério estabelecido
Lista a situação: caras na fila, últimas senhas chamadas e tal

E para ficar dinâmico tem o tempo que passa. Então escrevi uma rotina que usa as letras NPLA para sinalizar as opções, e um modesto programa de teste que lê uma sequência dessas e executa, e permite que você digite essas sequências direto na linha de comando para não ter que ficar compilando o programa apenas para mudar os dados.

Exemplo para o tal programa fila-1.exe (Windows) ou fila-1 (outras plataformas)

fila1 LA

mostra a situação da fila, que está vazia (L) , e tenta atender alguém com a fila vazia (A)

fila1 NNNNPPPPLAAL

NNNN mostra a chegada de quatro caras para atendimento normal
PPPP quatro caras com atendimento prioritário
L mostra o painel de status com a fila e as últimas senhas chamadas (nenhuma)
A atende alguém. Lógico que o primeiro a ser atendido deve ser o da fila com atendimento prioritário, certo? Ou tente explicar pra ele que a regra não vale para o primeiro cliente
A atende outro cliente, que deve ser o que pegou a primeira senha
L mostra o painel depois do segundo atendimento, com duas senhas chamadas e presumimos seis caras na fila
ao final do serviço o programa termina então está implicita a função de sair

Acho que deu pra entender.

Você escreve no terminal

lista-1 NNNNPPPPLAAL

E o programa roda como se você usse o menu e fizesse essas mesmas opções, gerando dados arrumadinhos conforme o caso. Você roda direto da linha de comando porque é claro como as coisas funcionam: você vai rodar o seu programa em algum lugar, não o seu ambiente de desenvolvimento. Claro, você tem as duas opções, não é obrigado a usar a linha de comando.

Não vou dizer que esse modo de fazer é melhor ou pior ou mesmo bom, mas é uma maneira consagrada de desenvolver essas coisas, porque você começa a testar em 15 minutos e vai refinando os resultados

Depois que está razoável você começa a empacotar a solução

Eis as funções que eu usei aqui, com funções de acordo com os nomes:

int ciclo(char servico);
int inicia_trabalhos();
int lista();
int marca_senha_painel(int);
int move_a_fila(int);
int pega_senha(int);

E os dados

struct cadastro
{
    char nome[50];
    int senha;
    int posicao_na_fila;
};
typedef struct cadastro Cadastro;

Cadastro cad[CAPACIDADE]; // cada elemento e a fila
char fila[CAPACIDADE]; // representa as filas
int q_fila_normal; // na fila normal
int q_fila_prioridade; // na fila prioridade
int q_fila; // todo mundo que esta na fila
int ja_atendidos; // ajuda a testar
int ultimas_senhas[5]; // o painel  superfluo tambem

Bem simples como vê. Mas podia ser mais simples.

Exemplo de uma execução para o segundo caso NNNNPPPPLAAL

***** iniciando expediente CAPACIDADE=20 CLIENTES *****

***** Rotina=[LNNNNPPPPLAAL] Capacidade 20 *****

Total de acoes: 13


---------- ---------- ---------- ----------

Painel
Fila Vazia

---------- ---------- ---------- ----------
    CADASTRADO 'Jose dos Santos de 2501 Jr.' com senha 501 na fila [Normal] pos=1
    CADASTRADO 'Jose dos Santos de 2502 Jr.' com senha 502 na fila [Normal] pos=2
    CADASTRADO 'Jose dos Santos de 2503 Jr.' com senha 503 na fila [Normal] pos=3
    CADASTRADO 'Jose dos Santos de 2504 Jr.' com senha 504 na fila [Normal] pos=4
    CADASTRADO 'Jose dos Santos de 2505 Jr.' com senha 505 na fila [Prioridade] pos=5
    CADASTRADO 'Jose dos Santos de 2506 Jr.' com senha 506 na fila [Prioridade] pos=6
    CADASTRADO 'Jose dos Santos de 2507 Jr.' com senha 507 na fila [Prioridade] pos=7
    CADASTRADO 'Jose dos Santos de 2508 Jr.' com senha 508 na fila [Prioridade] pos=8

---------- ---------- ---------- ----------

Painel
Tamanho da fila:......   8
Normal:...............   4
Prioritario: .........   4

Fila (8 clientes):

#  1: [Jose dos Santos de 2501 Jr.], Senha 501 [N]
#  2: [Jose dos Santos de 2502 Jr.], Senha 502 [N]
#  3: [Jose dos Santos de 2503 Jr.], Senha 503 [N]
#  4: [Jose dos Santos de 2504 Jr.], Senha 504 [N]
#  5: [Jose dos Santos de 2505 Jr.], Senha 505 [P]
#  6: [Jose dos Santos de 2506 Jr.], Senha 506 [P]
#  7: [Jose dos Santos de 2507 Jr.], Senha 507 [P]
#  8: [Jose dos Santos de 2508 Jr.], Senha 508 [P]

---------- ---------- ---------- ----------
    ATENDENDO [Jose dos Santos de 2505 Jr.] senha 505 [PRIORIDADE]
    ATENDENDO [Jose dos Santos de 2501 Jr.] senha 501 [NORMAL]

---------- ---------- ---------- ----------

Painel
Tamanho da fila:......   6
Normal:...............   3
Prioritario: .........   3

Fila (6 clientes):

#  1: [Jose dos Santos de 2502 Jr.], Senha 502 [N]
#  2: [Jose dos Santos de 2503 Jr.], Senha 503 [N]
#  3: [Jose dos Santos de 2504 Jr.], Senha 504 [N]
#  4: [Jose dos Santos de 2506 Jr.], Senha 506 [P]
#  5: [Jose dos Santos de 2507 Jr.], Senha 507 [P]
#  6: [Jose dos Santos de 2508 Jr.], Senha 508 [P]

Ja atendidos: 2. Ultimas 5 senhas chamadas: 501  505

Ultima: 501

---------- ---------- ---------- ----------

Note que em inicia_trabalhos() e em pega_senha() um cadastro é preenchido com os clientes com nome certinho e senha e tal,, sem que seja preciso perder tempo com isso.

main() como seria?

int            main(int argc, char** argv)
{
    if (argc > 1)    // veio algo na linha de comando
    {
        inicia_trabalhos();
        testa_rotina(argv[1]);
        return 0;
    }    // end if

    inicia_trabalhos();
    char* rotina = "LNNNNPPPPLAAL";
    testa_rotina(rotina);
    return 0;
}    // end main()

Algo assim atende o caso da linha de comando mas permite que você use dentro do IDE para testar seguidamente atrás de algum problema: basta ir alterando a string rotina

E essa testa_rotina?

Essa simula o uso do menu e deixa tudo mais ágil

int    testa_rotina(char* servico)
{
    printf("\n***** Rotina=[%s] Capacidade %d *****\n", servico, CAPACIDADE);
    int n = strlen(servico);
    printf("\nTotal de acoes: %d\n\n", n);
    for (int i = 0; i < n; i++)
    {
        ciclo(servico[i]);
    };    // end for
    return n;
}    // end testa_rotina()

E a rotina ciclo() simula a passagem do tempo e roda as funções.

Veja um trecho de código para um atendimento prioritário por exemplo:

    case PRIORIDADE:
        if (q_fila == CAPACIDADE)
        {
            printf("    SEM mais senhas. Por favor AGUARDE\n");
            return -1;
        }    // end if
        q_fila += 1;
        fila[q_fila] = PRIORIDADE;            // entra no fim da fila
        pega_senha(q_fila);
        printf(
            "    CADASTRADO '%s' com senha %03d na fila [Prioridade] pos=%d\n",
            cad[q_fila].nome,
            cad[q_fila].senha,
            cad[q_fila].posicao_na_fila
        );
        q_fila_prioridade += 1;
        break;

o atendimento é um pouco mais longo mas não tem nem 30 linhas se tirar os milhões de comentários. Estou usando esse programa para um outro propósito, ou mais do mesmo, com um outro pessoal

Como exemplo esse trecho abaixo trata o caso de pegar um cara na fila de atendimento prioritário

    // o inicio da fila pode apontar para um cliente
    // prioritario que ja foi antendido na sequencia
    if (q_fila <= 0)
    {
        printf("    ATENDIMENTO: Fila Vazia\n");
        return 0;
    }    // end if

    a_atender = SEM_CLIENTE;
    if (sequencia % 3 == 0)
    {
        // vai procurar proximo cliente com prioridade
        for (int i = 1, pos = i; i <= q_fila;)
        {
             if (fila[pos] == PRIORIDADE)
            {
                a_atender = pos;        // marca pra chamar esse
                break;    // sai do loop: achou
            }
            else
            {
                if (fila[pos] == LIVRE) continue;    // nao tem cliente
                i = i + 1;                // tem cliente aqui    
            }    // end if
            pos = pos + 1;
        }    // end for
    }    // end if

Não vou comentar o código todo. Se se interessou pode perguntar qualquer coisa. O programa está lá no link. Espero que ajude. E espero que entenda a diferença de escrever um programa com isso em mente: estrutura de dados, rotina de testes, geração de dados de amostra e tal. Demora muito menos. Não é minha ideia.

E onde iria com isso para colocar o menu e os dados?

Simples: o cliente vai criar uma entrada de cadastro usando o menu, você pega uma senha e conforme ele tenha ou não prioridade você chama ciclo() com a função certa. O cadastro ele já preencheu, a senha ele já pegou chamando a função pega_senha() e a fila anda com a chamada de um próximo ciclo(). Ele usou a opção listar? Ou atender? Basta colocar um N P L ou A no ciclo...

Espero que ajude.