J'apprends les files d'attente circulaires. Quelle implémentation de la file d'attente circulaire est la meilleure, l'implémentation de tableau ou l'implémentation de liste chaînée?Quelle implémentation de la file circulaire est la meilleure?
Si vous le faites dans une liste chaînée, alors cela peut être circulaire, car le dernier nœud pointe vers le premier. Mais je pense que vous devez clarifier ce que vous voulez dire par «meilleur».
Vous avez raison.Mais nous pouvons aussi apporter quelques modifications au programme normal de la file d'attente de telle sorte que lorsque le dernier index atteint dans le tableau, nous pouvons faire pointer le tableau vers le premier index de l'array.So cela fonctionne parfaitement comme une file d'attente circulaire. Précision pour BEST: Meilleur en termes de vitesse d'accès aux données et de gestion de la mémoire. – NEO
Vous n'avez pas encore vraiment clarifié ce que vous entendez par là: évidemment, la vitesse est importante, et la gestion de la mémoire n'est pas vraiment une métrique. Fyi, c'est aussi souvent appelé un anneau-tampon. –
Je dirais que la version liste liée serait la meilleure des deux solutions pour le fait que vous n'avez pas besoin de continuer à ajuster la mémoire qui est la votre pour permettre plus d'éléments dans votre tableau. En plus de ce que Skilldrick a dit à propos d'une liste chaînée, à propos de cela, elle pointe vers l'endroit auquel elle appartient (le dernier nœud pointe vers la première, le rendant ainsi circulaire).
Cela dépend des opérations que vous devrez effectuer sur la liste circulaire. Par exemple, si vous avez besoin d'un accès aléatoire ("donnez-moi le 237ème élément de la liste"), l'implémentation de la matrice sera beaucoup plus rapide. D'autre part, avec un outil, vous devrez parfois redimensionner la liste, ce qui sera lent. Vous pouvez l'amortir pour obtenir le temps amorti O (1) par insertion, mais sur un système en temps réel, le fonctionnement lent occasionnel peut être inacceptable.
La file d'attente circulaire est une file d'attente limitée qui implémente des tableaux. C'est mieux qu'une file d'attente normale parce que nous pouvons utiliser efficacement l'espace mémoire. Si nous avons une file d'attente normale et que nous avons supprimé des éléments, de l'espace vide est créé et même si la file contient des cellules vides. nous ne pouvons pas non plus insérer de nouveaux éléments car l'insertion doit être effectuée d'un seul côté (arrière ou arrière) et la suppression doit être effectuée d'un autre côté (avant ou arrière) .Mais en cas de file d'attente circulaire avant et arrière sont adjacents les uns aux autres.
Question: Quel type d'ours est le meilleur? – NullUserException
Les ours vont vous manger! –
@Null C'est une question ridicule ... – quantumSoup