Différence entre la file d'attente de tableau et la file d'attente de liste chaînée

Présentation

Une file d'attente est une structure de données linéaire qui insère et supprime des éléments de file d'attente dans un ordre spécifique. Nous pouvons implémenter des files d'attente en C++ en utilisant des tableaux et des listes chaînées. Les deux implémentations de files d'attente ont leurs propres avantages et utilisations. Dans ce didacticiel, nous ferons la différence entre les files d'attente basées sur des tableaux et les files d'attente basées sur des listes chaînées.

Qu'est-ce qu'une file d'attente ?

Une file d'attente est une série d'éléments qui utilisent le principe FIFO (premier entré, premier sorti) pour l'insertion et la suppression d'éléments. Les files d'attente en informatique sont similaires aux files d'attente dans la vie réelle, la première personne à entrer dans la file d'attente sera supprimée en premier.

Le processus de suppression des données de la file d'attente s'appelle deQueue. L'opération d'ajout de données à la file d'attente est appelée enQueue.

La file d'attente comporte deux points -

• After- Les éléments de la file d'attente sont insérés à partir d'ici.

• Front- L'élément dans la file d'attente sera supprimé d'ici.

Nous pouvons implémenter des files d'attente de deux manières -

• File d'attente basée sur un tableau

• File d'attente basée sur une liste ou file d'attente de liste chaînée

File d'attente basée sur un tableau

La file d'attente implémentée à l'aide de tableaux est appelée file d'attente basée sur un tableau. Il utilise deux pointeurs : Front et Rear, qui représentent respectivement le point de suppression et le point d'insertion dans la file d'attente.

Dans cette implémentation, la taille du tableau est prédéfinie avant d'insérer les données. Il s'agit du moyen le plus simple d'insérer et de supprimer des données de file d'attente.

File d'attente basée sur une liste

Dans la file d'attente basée sur une liste ou la file d'attente basée sur une liste chaînée, la liste chaînée est utilisée pour l'implémentation de la file d'attente. Chaque nœud de file d'attente se compose de deux parties : une partie est utilisée pour stocker les données et l'autre partie est la partie liaison ou la partie mémoire.

Chaque élément de file d'attente est connecté à la mémoire de l'élément de file d'attente suivant. Il y a deux pointeurs dans une file d'attente basée sur une liste -

• Pointeur précédent- Représente la mémoire du dernier élément de la file d'attente.

• Pointeur arrière- mémoire représentant le premier élément de la file d'attente.

La différence entre la file d'attente de tableau et la file d'attente de liste chaînée

Utilisez des files d'attente basées sur des tableaux et des files d'attente basées sur des listes chaînées

Si votre file d'attente a une taille fixe et qu'il n'est pas nécessaire de modifier la taille de la file d'attente, vous pouvez implémenter la file d'attente à l'aide d'un tableau. Les files d'attente basées sur des tableaux sont également utiles lorsque la recherche est rapide et consomme moins de mémoire.

L'implémentation de file d'attente basée sur une liste chaînée est très utile lorsque la taille de la file d'attente est dynamique et que les éléments de la file d'attente sont insérés et supprimés plusieurs fois. Bien qu'il consomme plus de mémoire, il convient aux applications à grande échelle

Conclusion

L'utilisation de files d'attente basées sur des tableaux et de files d'attente basées sur des listes chaînées dépend des exigences. Dans les applications à grande échelle, les files d'attente basées sur des tableaux échouent et des files d'attente de liste chaînée sont utilisées à la place.

Les files d'attente basées sur des tableaux utilisent moins de mémoire mais gaspillent beaucoup de mémoire car après l'insertion d'éléments dans le backend, il reste de la mémoire inutilisée avant le premier élément.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!