C++ Problème liste d'attente élaborée

Bonjour à tous,

nouveau sur ce site j'aurais besoin de conseil de pro ..

j'ai besoin définir une file d'attente en C++ à partir de priorité de de position d'arriver

ENONCE
File d’attente élaboré

Un patient a un nom et un type. Il y a trois types de patients T1 : les très urgent ; T2 : urgent et T3 : non urgent.

J’ai une file d’attente unique (salle d’attente) pour ces trois types de patients. La règle est : a priorité égale, premier arrivée premier servi », sinon le T1 passent devant les T2 qui passent devant les T3.

Exemple : file vide. Arrivent « Joe, T3 » puis « Jack T3 » puis « William » T2. La file est <William, Joe, Jack>. Le médecin se libère, il traite donc « William ». Arrivent « Lucky Luke T1 » puis « Avrell T2 ». On a donc <Lucky Luke, Avrell, Joe, Jack>. Arrivent ensuite « Jessie James T1 », « Billy the Kid T2 » et « Ma Dalton T3 ». On a donc <Lucky Luke, Jessie James, Avrell, Billy the Kid , Joe, Jack, Ma Dalton>.

Le programme doit pouvoir (menu principal en fait) :
- Afficher la liste en cours ;
- Ajouter une personne ;
- Supprimer le premier de la file ;
- Sauvegarder/récupérer la file.

Si quelqu'un a deja fait ca ou c'est me dire comment gérer le file d'attente, ce serai gentil ;-)

merci

Bonjour,

où bloques-tu exactement?

Cela te donnerai la solution à cet exercice.

Il serait plus interessant pour toi de te poser les bonnes questions en lisant le problème:
- qu'est-ce qu'une file d'attente, de manière abstraite? quel est son role?
- qu'est-ce que va contenir ta file?
- quelles sont les actions a effectuer?
- etc...

Je t'ai donnée des premiers indices.

Citation:

---

Envoyé par Valou6323

Si quelqu'un a deja fait ca ou c'est me dire comment gérer le file d'attente, ce serai gentil ;-)

---

std::priority_queue...

Citation:

---

Envoyé par JolyLoic

std::priority_queue...

---

Afin de gagner du temps, je me propose d'anticiper la suite :

Oui, mais j'ai pas le droit.... :cry:

Salut,

Le principe est assez trivial et peut s'envisager sous la forme de

Code:

---

1 2 3 4 5

Si Priorité de l'élément à insérer inférieure a un élément testé passer à l'élément précédent dans la file Sinon insérer l'élément entre l'élément testé et son suivant Fin Si

---

Reste à savoir:

1. comment comparer la priorité des éléments à insérer
2. comment insérer un élément entre deux autres
3. comment relier les différents élément les un aux autres ;)

A toi de jouer :D

Citation:

---

Envoyé par poukill

Afin de gagner du temps, je me propose d'anticiper la suite :

Oui, mais j'ai pas le droit.... :cry:

---

Sauf le droit de s'en inspirer ?

Vu l'algo, je ne me serais pas enquiquiner.
Trois files en fonction du type de patient et récupération dans la liste de plus haut priorité non vide.
Reste plus que le verrouillage des inserts durant le scan des 3 files.

Citation:

---

Envoyé par bacelar

Vu l'algo, je ne me serais pas enquiquiner.
Trois files en fonction du type de patient et récupération dans la liste de plus haut priorité non vide.

---

Tu imagine la difficulté de l'algorithme, si tu le fais ainsi :question:

L'insertion serait effectivement facile, mais pour le reste, tu tombe sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Pour Renvoyer le patition de plus haute priorité   si urgent non vide renvoyer urgent top sinon si moyen non vide renvoyer moyen top sinon si non_urgent non vide renvoyer non_urgent top fin si fin si fin si renvoyer rien     Pour sortir un patient de la liste si patient:priorite egal urgent retirer urgent top sinon si patient: priorite égal moyen retirer moyen top sinon si patient:priorite égal non_urgent retirer non_urgent top fin si fin si fin si

---

Si tu places tous les patients dans une seule et même liste, l'insertion sera certes un peu plus lente, mais le reste de la gestion se fera beaucoup plus rapidement, vu que tu évite les tests ;)
[/QUOTE]Reste plus que le verrouillage des inserts durant le scan des 3 files.[/QUOTE]Ce serait plus problématique que cela...

Tu utiliserais sans doute le double check; verrouiller, tester si vide, déverrouiller retester.

Avec trois listes, rien ne t'empêche d'ajouter un élément dans les listes sur lesquelles tu ne travaille pas (il serait dommage de verrouiller les trois listes alors que tu ne travailles que sur une).

tu devrais donc revérifier les listes de priorité supérieure lors deux deuxième test :aie: Encore du temps de perdu :aie:

Le prix d'un déplacement pour insertion me parait tellement aberrant, que je foncerai sans hésiter une seule seconde vers la triple file -- si NIH interdisant la solution standard.

Quant au lock ... le temps des déplacements est tel, que c'est pour moi un argument de plus en faveur de la triple file -- un seul lock global suffisant amplement comparé à 3 micro-locks (et si on a accès à des listes lock-free, le problème ne se pose pas)(quant à l'aspect : un cas urgent arrive alors que l'on pioche la fiche d'un cas de moindre priorité, c'est tant pis, il faut rester simple).

Maintenant, j'ai tendance à supposer qu'il y a beaucoup d'éléments dans la queue pour justifier un système de passe-droits. La dimension du problème est à étudier avant de valider la meilleure des approches.

Citation:

---

Envoyé par Luc Hermitte

Le prix d'un déplacement pour insertion me parait tellement aberrant, que je foncerai sans hésiter une seule seconde vers la triple file

---

Il me parait tellement aberrant, que j'utiliserais peut-être une structure de base où il n'existe pas (liste chaînée).