[Powered by Google Translate] [File]
[Chris Gerber, Université de Harvard]
C'est CS50, CS50.TV]
Une structure de données utiles pour stocker une collection ordonnée d'éléments est une file d'attente.
Il est utilisé lorsque les éléments doivent être supprimés
dans le même ordre que celui qu'ils ont été ajoutés.
Ce concept est appelé FIFO, qui est un acronyme pour le premier entré, premier sorti.
Afin de mieux visualiser cela, il peut être utile d'image
une ligne de caisse dans un magasin.
Ainsi, lorsqu'ils arrivent, ils attendent à l'arrière de la ligne.
Le caissier prend alors tour à tour au service des clients à l'avant,
qui ont ensuite quitter la ligne à la fois.
En informatique, nous nous référons à l'avant de la file d'attente à la tête
et que l'arrière de la queue.
Un exemple de situation où nous pourrions l'utiliser dans une application
une liste d'attente pour les inscriptions de classe.
Si des places sont disponibles dans la classe,
la personne à la tête de la liste d'attente est prévue la possibilité de s'inscrire dans la classe.
>> Une file d'attente peut être construit en utilisant n'importe quelle collection
qui stocke les données dans l'ordre, par exemple un tableau ou une liste chaînée.
Avec la collection pour stocker les éléments dans la file d'attente,
nous avons également besoin d'une méthode pour ajouter des éléments à la fin de la file d'attente,
qui est appelé mise en file,
et un autre pour supprimer un élément de la tête de la file d'attente,
qui est appelé dequeuing.
Il est souvent utile d'inclure une autre méthode pour retourner la longueur actuelle de la file d'attente
ainsi qu'une méthode pour vérifier si la file d'attente est vide.
Regardons comment nous pourrions implémenter une file d'entiers en C,
à l'aide d'un tableau pour la collection d'éléments.
Tout d'abord, nous créons une structure appelée file d'attente de tenir nos variables.
Nous allons utiliser un tableau de taille fixe index 0 d'entiers
pour stocker les éléments.
Nous allons également inclure une tête variable appelée
qui stocke l'indice de l'élément qui est actuellement à la tête de la file d'attente.
Une troisième variable, appelée longueur, sera utilisé
pour garder une trace du nombre d'éléments dans le tableau.
Comme alternative, vous pouvez envisager d'utiliser une variable appelée queue
pour pointer vers l'élément dernier champ de la matrice.
Avant d'écrire du code plus,
Essayons notre conception.
Commençons par un tableau vide de longueur 0,
avec la tête réglé à 0.
Maintenant, nous allons enqueue 4 valeurs - 6, 2, 3 et 1.
La longueur sera désormais 4,
et la tête restera à 0.
>> Qu'est-ce qui se passe si nous dequeue une valeur?
Nous allons réduire la durée à 3,
mettre la tête à 1,
et retourner la valeur 6.
Ce code pourrait ressembler à ceci.
Ici, nous avons la fonction dequeue,
qui prend un pointeur vers la file d'attente - q - et un pointeur vers l'élément,
qui est un type int.
Nous avons d'abord vérifier la longueur de la file d'attente afin de s'assurer qu'il est supérieur à 0,
faire en sorte qu'il y ait un élément de sortir de la file.
Ensuite, nous regardons dans le tableau des éléments, à la position de la tête,
et régler la valeur de l'élément comme étant la valeur à cette position.
Ensuite, nous changeons la tête à l'index suivant
% De la capacité.
Nous avons ensuite réduire la longueur de la file d'attente de 1.
Enfin, nous retourner true pour indiquer que le dequeue a réussi.
Si nous dequeue encore, la longueur sera 2,
la tête deviendra également 2,
et la valeur de retour sera de 2.
>> Qu'est-ce qui se passe si nous en file d'attente une autre valeur comme un 7?
Comme nous étions à la fin de la file d'attente,
nous aurons besoin pour envelopper et conserver la valeur en 0 élément du tableau.
Mathématiquement, cela peut être représentée en ajoutant la longueur
à l'indice de la tête
et exécuter un module en utilisant la capacité de la file d'attente.
Ici, c'est 2 +2, qui est de 4% 4,
qui est égal à 0.
Traduire cette idée de coder nous avons cette fonction.
Ici, nous voyons la fonction enqueue,
qui prend un pointeur vers la file d'attente - q -
et a l'élément devant être mise en queue, qui est un nombre entier.
Nous avons ensuite assurez-vous que la capacité de la file d'attente
est encore plus grande que la longueur actuelle de la file d'attente.
Ensuite, nous stockons l'élément dans le tableau des éléments
à l'index est déterminée par la longueur de la tête +% de la capacité de la file d'attente.
Nous avons ensuite augmenter la longueur de la file d'attente de 1,
puis retourner true pour indiquer que la fonction enqueue a réussi.
>> En plus de ces deux fonctions que nous avons mentionnés,
il existe deux fonctions supplémentaires.
La première est la fonction IsEmpty,
qui prend un pointeur vers la file d'attente
et vérifie que la longueur est 0.
La seconde est la fonction de la longueur,
qui prend également un pointeur vers la file d'attente
et renvoie la longueur actuelle de la structure.
Ce bref aperçu a démontré une éventuelle mise en œuvre d'une file d'attente.
Une des limites de cette mise en œuvre
est que la file d'attente a une taille maximale fixe.
Si nous essayons d'ajouter d'autres éléments de la file d'attente peut contenir,
nous pourrions avoir besoin pour ignorer la demande et déposer l'élément,
ou on peut préférer d'y retourner un type d'erreur.
En utilisant une liste chaînée plutôt qu'un tableau
il serait plus facile à taille dynamiquement la file d'attente.
Toutefois, étant donné que nous n'avons pas un accès direct aux éléments d'une liste chaînée,
si l'on ne garde pas trace de la queue,
nous aurions à parcourir la liste entière liée à arriver à la fin à chaque fois.
On pourrait également envisager d'utiliser un tableau d'un autre type de données,
tels que les structures, pour créer des files d'attente d'éléments plus complexes.
En repensant à notre exemple d'une liste d'attente de classe,
ces structures pourraient représenter les étudiants individuels.
>> Mon nom est Chris Gerber, et c'est CS50.
[CS50.TV]
Et retours - >> encore une fois.
Et retourner true pour indiquer que - la file d'attente a été un succès.
-% De la capacité de la file d'attente -
Ça va être amusant en édition. [Rires]