Quels sont les bons exemples simples de files d'attente? [fermé]

J'enseigne CS2 ( Java and data structures), et j'ai du mal à trouver de bons exemples à utiliser lors de l'enseignement des files d'attente. Les deux applications principales pour lesquelles je les utilise sont la multithreadedtransmission de messages (mais la programmation MT est hors de portée pour le cours) et BFS-style algorithms(et je ne couvrirai les graphiques que plus tard dans le trimestre).

Je veux également éviter les exemples artificiels. La plupart des choses auxquelles je pense, si j'allais réellement les résoudre de manière monothread, j'utiliserais simplement une liste plutôt qu'une file d'attente. J'ai tendance à n'utiliser les files d'attente que lorsque le traitement et la découverte sont entrelacés (par exemple la recherche), ou dans d'autres cas spéciaux comme les tampons à longueur limitée (par exemple, en conservant les N derniers éléments). Dans la mesure du possible, j'essaie d'enseigner à mes élèves de bonnes façons de faire des choses dans de vrais programmes, pas seulement des jouets pour montrer une fonctionnalité.

Des suggestions de bons algorithmes simples ou d'applications de files d'attente que je peux utiliser comme exemples mais qui nécessitent un minimum d'autres connaissances préalables?

Lorsque j'apprenais les files d'attente, mon professeur utilisait toujours l'exemple d'un magasin. Il y a un ou plusieurs registres ouverts à un moment donné, et les clients entrent dans une file d'attente ou une autre et se déplacent dans cette file d'attente pour acheter tous leurs articles.

Nous avons en fait dû mettre en œuvre un programme simple qui pouvait déplacer les clients dans une file d'attente de registre, donc si vous cherchez réellement un programme, vous pouvez donner aux étudiants cet exemple est simple et direct, mais aussi quelque chose que chaque étudiant a vu dans la vie réelle, etc. cela peut les aider à mieux comprendre le concept.

Quand j'ai appris les files d'attente, mon professeur me les a présentées en utilisant une file d'attente pour les voitures au poste de police. Il y avait une file d'attente contenant les voitures ("file d'attente") et le policier contrôlait toujours la prochaine voiture dans la file d'attente et l'envoyait à son collègue pour de nouvelles inspections ou laissait la voiture passer.

Un exemple très souvent utilisé est la file d'attente dans le super-marché ...

Pourquoi ne demandez-vous pas à vos élèves de donner eux-mêmes des exemples?

Un exemple qui me vient à l'esprit est une chaîne de traitement de hamburgers, par exemple chez McDonalds. Il existe plusieurs types de hamburgers différents, chacun pouvant être produit par plusieurs travailleurs différents et chacun ayant sa propre file d'attente. De là, après un certain temps, les hamburgers prêts sont pris, dans l'ordre FIFO, par l'un des caissiers qui ont commandé ce type de hamburger.

Il y a donc plusieurs producteurs et consommateurs, et chaque file d'attente est limitée.

J'ai pensé à utiliser Amazon comme exemple, quelque part dans leur énorme système, il doit y avoir une file d'attente de commandes à traiter. qui pourrait être géré par une simple mise en file d'attente et de retrait. le système mettrait en file d'attente une commande dans le système chaque fois qu'un client achèterait un livre, et une personne de l'entrepôt la retirerait ensuite afin de la prendre et de la poster.

Il serait alors facile de commencer à parler des files d'attente prioritaires, en introduisant des clients principaux, qui pourraient sauter la file d'attente, vous pourriez introduire des files d'attente prioritaires.

Quel manuel utilisez-vous?

Un exemple parfait de file d'attente serait une banque traitant des transactions sur un compte. Habituellement, vous verrez une liste des transactions "en attente" à la fin de la journée. Lorsque la comptabilité est terminée, ces transactions sont appliquées au compte. Vous pouvez même entrer dans le domaine des files d'attente prioritaires avec cela. Il semble que la plupart des banques accordent la priorité aux débits lors du traitement des transactions nocturnes afin de pouvoir vous éviter les frais de dossier avant d'appliquer les crédits en attente.

Les transactions sont insérées dans la file d'attente par ordre de temps exécuté et retiré de la file d'attente et appliquées au compte par le processus comptable.

J'étais programmeur en télécommunications, alors cela me vient à l'esprit:

Une hotline service client. Un appel arrive, il n'y a pas suffisamment d'opérateurs pour gérer l'appel et il est placé dans une file d'attente. Le prochain appel arrive et il est également placé dans la file d'attente. Ensuite, lorsque l'opérateur suivant devient disponible, le premier appel entré dans la file d'attente est attribué à l'opérateur disponible.

Les exemples évidents du monde réel seraient des choses comme les lignes de paiement, et ainsi de suite, mais comme vous recherchez un exemple strictement lié à l'informatique, puis-je suggérer des files d'attente de planification des travaux ?

Je ne sais pas combien de vos élèves ont suivi un cours sur les systèmes d'exploitation, mais il y a fort à parier que tous ont utilisé le gestionnaire de tâches pour vérifier leurs processus à un moment ou à un autre. Vous pouvez introduire un exemple simplifié d'une file d'attente de planification et leur affecter des devoirs pour écrire un programme qui génère (ou accepte) une "tâche" d'une taille donnée, et les traite dans l'ordre FIFO lorsqu'ils "la démarrent".

C'est un concept assez facile à comprendre, démontre l'idée que la file d'attente fonctionne sur son contenu dans l'ordre dans lequel il les accepte et leur donne une introduction (très rudimentaire et simplifiée) à la planification du processeur. Juste mes deux morceaux.

Vous pourriez présenter leur application en multithreading, mais à moins que les étudiants aient déjà une certaine expérience de l'écriture de programmes threadés, je ne leur assignerais pas de travail qui pourrait être frustrant. Je me souviens avoir eu du mal à apprendre les structures de données (en particulier en Java, n'ayant pas fait de C ++ et n'ayant rien appris sur les pointeurs) au cours de ma deuxième année de collège, donc un exemple simple mais pratique directement lié à l'informatique est probablement le meilleur.

Monde réel:

• Chaque fois que les gens font la queue: caissier à l'épicerie, au restaurant en attente d'une table (vous pouvez travailler dans ces bips qu'ils donnent parfois à l'analogie), etc. C'est utile lorsque vous remarquez qu'au Royaume-Uni, ils appeler ces files d'attente au lieu de lignes (commun en NA)
• Reading book series ', author.publish => queue.push et student.read => queue.pop

Monde non réel:

• Traitement de toutes les données soumises dans un environnement à un seul thread où le traitement prend plus de temps que la soumission (opérations de paiement pour les magasins en ligne, par exemple.)
• Toute collection FIFO qui peut être itérée peut utiliser des files d'attente et utiliser à la while(queue.peek)place d'un itérateur.

J'aime utiliser les jeux comme exemple parce que c'est généralement un peu plus excitant que les fichiers IO ou tout ce que vous pouvez trouver.

Donc, lorsque vous souhaitez envoyer plusieurs commandes d'affilée à une unité dans un jeu de stratégie (par exemple, demandez à un Zergling de repérer les 4 coins d'une base dans l'ordre, puis de vous suicider au centre de la base, une file d'attente serait un bon choix). .)

Ou peut-être avez-vous une application qui ne peut traiter que 30 images par seconde, mais vous pouvez obtenir 4 ou 5 entrées entre les images. Si vous avez une entrée de changement d'arme et une entrée de tir, vous voulez vous assurer que celles-ci sont traitées dans l'ordre où elles ont été reçues, sinon vous pouvez grenade lorsque vous vouliez vous poignarder. Et si vous grenade quand vous voulez vous poignarder, vous allez passer un mauvais moment. (mettez ça sur le meme moniteur de ski et jetez le dans vos slides) :)

Un serveur qui gère les demandes est une autre bonne chose.

Une machine CNC prenant des données. La machine ne peut aller aussi vite, elle doit donc mettre en file d'attente les entrées.

Quelques exemples auxquels je peux penser:

• Calculatrice - peut introduire le préfixe et le suffixe en même temps
• Instructions pour attacher les chaussures. Impossible de terminer l'opération suivante tant que vous n'avez pas effectué la dernière
• Tampons - Peut-être un tampon téléphonique utilisé pour stocker des numéros que l'utilisateur a saisis mais qui n'ont pas encore émis la tonalité
• Digestion

Les lignes de fabrication sont remplies de files d'attente. Pensez à une ligne de bouteilles vides se dirigeant vers une machine de remplissage. Le premier entré, premier sorti est un moyen naturel d'appliquer un processus séquentiellement à de nombreux objets. Les files d'attente sont également utilisées pour découpler un processus d'un autre: la machine de remplissage n'a pas à s'arrêter immédiatement en cas de problème à court terme avec la machine d'étiquetage.

Les files d'attente sont utilisées dans les logiciels de la même manière. La sortie d'un processus peut être mise en file d'attente pour être entrée dans un autre processus. Cela est vrai que vous parliez de communication inter-processus, de communication inter-thread, ou simplement de diviser un processus compliqué en parties qui pourraient toutes être gérées par le même thread.

Dans les systèmes d'exploitation, les files d'attente sont souvent utilisées pour traiter les entrées dans l'ordre. Le système de fichiers peut lire des blocs à partir d'un périphérique de stockage et les ajouter à une file d'attente, par exemple. Ou les interruptions qui gèrent des choses comme les pressions sur les touches et les mouvements de la souris créent des événements qui sont ajoutés à une file d'attente d'événements afin que vous n'obteniez pas "uqeeu" au lieu de "file d'attente" lorsque vous tapez.

Pour une tâche simple d'étudiant, je pense que n'importe quelle tâche qui accepte un certain nombre d'entrées puis les traite fonctionnerait. Par exemple, vous pourriez leur demander d'écrire un évaluateur d'expression postfixe simple. Il comporterait trois parties:

• lire une entrée, l'ajouter à la file d'attente d'entrée et répéter jusqu'à ce qu'il n'y ait plus d'entrées

• obtenir un élément de la file d'attente

  • si l'élément est un nombre, poussez-le sur la pile d'arguments
  • si l'élément est un opérateur, entrez les arguments nécessaires et évaluez
  • ajouter le résultat à la file d'attente de sortie
  • répéter jusqu'à ce que la pile soit vide

• lire un élément de la file d'attente de sortie, l'imprimer et répéter jusqu'à ce que la file d'attente de sortie soit vide

Dans l'enseignement des structures de données, j'utilise généralement l'application de la simulation de file d'attente bancaire où les clients attendent dans une file d'attente et il existe un certain nombre de fenêtres de service.

Le problème est de simuler le processus afin de trouver des statistiques sur les éléments suivants: temps d'attente des clients dans la file d'attente (max, min, moyenne) et nombre de clients en attente dans la file d'attente. J'utilise une fréquence prédéfinie d'arrivée de nouveaux clients toutes les minutes d'une journée et un temps de service moyen d'un client sur la fenêtre de service avec les valeurs du générateur de nombres aléatoires.

Le résultat sera des recommandations pour le nombre optimal de fenêtres de service et le nombre optimal de chaises dans la salle d'attente qui garantiraient la satisfaction du client. Application très intéressante pour les étudiants.

Tout algorithme de planification implique presque toujours une file d'attente.

Cela peut aller d'une simple file d'attente du premier arrivé, premier servi à la demande de tampon pour un seul consommateur.

Vers une file d'attente de planification de travaux complexe où les «tâches» peuvent avoir des priorités et les «travailleurs» ont des capacités différentes.

Un bon exemple d'utilisation pourrait être "Vous disposez d'un serveur d'impression central avec quatre imprimantes connectées, deux capables de couleur, une capable d'imprimer recto verso et une capable d'imprimer sur du papier plus grand. Les utilisateurs peuvent payer un supplément pour une tâche urgente, ou moins si cela ne les dérange pas d'attendre plus longtemps. Vous pouvez encourir des pénalités si vous livrez en retard, vous voulez donc autant de débit que possible. "