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

La traduction chinoise de est :

S.No	Numéro de série		File d'attente basée sur un tableau	File d'attente basée sur une liste chaînée
1	Complexité	Il est facile à mettre en œuvre et à effectuer des opérations.	Ce n’est pas facile à mettre en œuvre.
2	Processus de recherche	Cela permet de rechercher facilement et rapidement.	Recherche lente et difficile.
3	Taille de la file d'attente	Définissez la taille de la file d'attente au moment de l'initialisation.	Pas besoin de définir la taille de la file d'attente lors de l'initialisation de la file d'attente.
4	Opérations d'insertion et de suppression	Il est difficile d'insérer des données au début, mais il est facile d'insérer des données à la fin de la file d'attente.	Il permet une insertion simple de données aux deux extrémités de la file d'attente.
5	Accès aux données	Accès aléatoire aux données.	Il fournit un accès séquentiel aux éléments de la file d'attente.
6	Ajustement de la taille de la file d'attente	Modifier la taille de la file d’attente est difficile.	Ajuster la taille de la file d’attente est facile.
7	Utilisation de la mémoire	Il consomme moins de mémoire.	Cela consomme plus de mémoire.
8	Avantages	Plus rapide et plus facile à mettre en œuvre. Il consomme moins de mémoire. Accès aléatoire aux éléments.	L'insertion et la suppression d'éléments de file d'attente sont faciles. Ajustez facilement la taille de la file d'attente sans déclarer la taille de la file d'attente à l'avance.
9	Inconvénients	Redimensionner les files d'attente est difficile. Déclarez la taille de la file d'attente à l'avance.	La vitesse de traitement est très lente. La structure est complexe et consomme beaucoup de mémoire.

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!