Je sais assez bien où utiliser les piles, les files d'attente et les arbres dans les applications logicielles, mais je n'ai jamais utilisé de Deque (file d'attente à double extrémité) auparavant. Où les rencontrerais-je généralement dans la nature? Serait-ce aux mêmes endroits qu'une file d'attente mais avec des gribbilies supplémentaires?
data-structures
Ingénieur du monde
la source
la source
Réponses:
Une façon d'utiliser un deque consiste à «vieillir» les éléments. Il est généralement utilisé comme fonction d'annulation ou d'historique. Une nouvelle action est insérée dans la deque. Les éléments les plus anciens sont à l'avant. Une limite sur la taille de la déque force les éléments à l'avant à être retirés à un moment donné lorsque de nouveaux éléments sont insérés (vieillissant les plus anciens). Il fournit ensuite un moyen rapide d'accéder aux deux extrémités de la structure, car vous connaissez instantanément les éléments les plus anciens et les plus récents pour supprimer le front et valider l'action la plus ancienne en O (1) ou annuler en O (1).
la source
Excellente question. Je ne me souviens pas de notre cours CS 102 mentionnant une seule application pour la file d'attente double.
À ce jour, la seule application que je connaisse est le planificateur de vol de travail mentionné dans l'article Wikipedia .
Il fonctionne essentiellement comme suit:
Dans un modèle procédural normal à un seul thread, chaque appel de fonction envoie un enregistrement d'activation sur une soi-disant pile d'appels . Un enregistrement d'activation contient les variables locales et les paramètres de cet appel. Une fois l'appel à la méthode terminé («retourne»), le dernier enregistrement d'activation est extrait de la pile d'appels.
Ceci est particulièrement important car c'est ainsi que la récursivité est implémentée: la structure de la récursivité est représentée dans l'état actuel de la pile d'appels.
Lors de la parallélisation d'un algorithme récursif, nous pouvons exploiter cette propriété en remplaçant la pile d'appels par une file d'attente d'appels. Chaque thread du calcul obtient sa propre file d'attente d'appels et pousse et affiche les enregistrements d'activation comme dans une exécution séquentielle.
Mais une fois qu'un thread a terminé son travail (= sa file d'attente d'appels est vide), il vole le travail d'un autre thread en supprimant un enregistrement d'activation de la file d'attente d'appels de ce thread en le supprimant de la «mauvaise» extrémité.
Fondamentalement, la file d'attente des appels agit comme deux piles d'appels qui desservent désormais deux threads.
la source