1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [File]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Université de Harvard]

3
00:00:05,000 --> 00:00:07,000
C'est CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Une structure de données utiles pour stocker une collection ordonnée d'éléments est une file d'attente.

5
00:00:11,000 --> 00:00:14,000
Il est utilisé lorsque les éléments doivent être supprimés

6
00:00:14,000 --> 00:00:16,000
dans le même ordre que celui qu'ils ont été ajoutés.

7
00:00:16,000 --> 00:00:20,000
Ce concept est appelé FIFO, qui est un acronyme pour le premier entré, premier sorti.

8
00:00:20,000 --> 00:00:23,000
Afin de mieux visualiser cela, il peut être utile d'image

9
00:00:23,000 --> 00:00:25,000
une ligne de caisse dans un magasin.

10
00:00:25,000 --> 00:00:28,000
Ainsi, lorsqu'ils arrivent, ils attendent à l'arrière de la ligne.

11
00:00:28,000 --> 00:00:31,000
Le caissier prend alors tour à tour au service des clients à l'avant,

12
00:00:31,000 --> 00:00:34,000
qui ont ensuite quitter la ligne à la fois.

13
00:00:34,000 --> 00:00:37,000
En informatique, nous nous référons à l'avant de la file d'attente à la tête

14
00:00:37,000 --> 00:00:39,000
et que l'arrière de la queue.

15
00:00:39,000 --> 00:00:41,000
Un exemple de situation où nous pourrions l'utiliser dans une application

16
00:00:41,000 --> 00:00:44,000
une liste d'attente pour les inscriptions de classe.

17
00:00:44,000 --> 00:00:46,000
Si des places sont disponibles dans la classe,

18
00:00:46,000 --> 00:00:50,000
la personne à la tête de la liste d'attente est prévue la possibilité de s'inscrire dans la classe.

19
00:00:50,000 --> 00:00:53,000
>> Une file d'attente peut être construit en utilisant n'importe quelle collection

20
00:00:53,000 --> 00:00:57,000
qui stocke les données dans l'ordre, par exemple un tableau ou une liste chaînée.

21
00:00:57,000 --> 00:01:00,000
Avec la collection pour stocker les éléments dans la file d'attente,

22
00:01:00,000 --> 00:01:02,000
nous avons également besoin d'une méthode pour ajouter des éléments à la fin de la file d'attente,

23
00:01:02,000 --> 00:01:04,000
qui est appelé mise en file,

24
00:01:04,000 --> 00:01:07,000
et un autre pour supprimer un élément de la tête de la file d'attente,

25
00:01:07,000 --> 00:01:09,000
qui est appelé dequeuing.

26
00:01:09,000 --> 00:01:14,000
Il est souvent utile d'inclure une autre méthode pour retourner la longueur actuelle de la file d'attente

27
00:01:14,000 --> 00:01:17,000
ainsi qu'une méthode pour vérifier si la file d'attente est vide.

28
00:01:17,000 --> 00:01:20,000
Regardons comment nous pourrions implémenter une file d'entiers en C,

29
00:01:20,000 --> 00:01:23,000
à l'aide d'un tableau pour la collection d'éléments.

30
00:01:23,000 --> 00:01:27,000
Tout d'abord, nous créons une structure appelée file d'attente de tenir nos variables.

31
00:01:27,000 --> 00:01:30,000
Nous allons utiliser un tableau de taille fixe index 0 d'entiers

32
00:01:30,000 --> 00:01:33,000
pour stocker les éléments.

33
00:01:33,000 --> 00:01:35,000
Nous allons également inclure une tête variable appelée

34
00:01:35,000 --> 00:01:39,000
qui stocke l'indice de l'élément qui est actuellement à la tête de la file d'attente.

35
00:01:39,000 --> 00:01:42,000
Une troisième variable, appelée longueur, sera utilisé

36
00:01:42,000 --> 00:01:45,000
pour garder une trace du nombre d'éléments dans le tableau.

37
00:01:45,000 --> 00:01:48,000
Comme alternative, vous pouvez envisager d'utiliser une variable appelée queue

38
00:01:48,000 --> 00:01:51,000
pour pointer vers l'élément dernier champ de la matrice.

39
00:01:51,000 --> 00:01:53,000
Avant d'écrire du code plus,

40
00:01:53,000 --> 00:01:55,000
Essayons notre conception.

41
00:01:55,000 --> 00:01:58,000
Commençons par un tableau vide de longueur 0,

42
00:01:58,000 --> 00:02:02,000
avec la tête réglé à 0.

43
00:02:02,000 --> 00:02:11,000
Maintenant, nous allons enqueue 4 valeurs - 6, 2, 3 et 1.

44
00:02:11,000 --> 00:02:14,000
La longueur sera désormais 4,

45
00:02:14,000 --> 00:02:17,000
et la tête restera à 0.

46
00:02:17,000 --> 00:02:20,000
>> Qu'est-ce qui se passe si nous dequeue une valeur?

47
00:02:20,000 --> 00:02:24,000
Nous allons réduire la durée à 3,

48
00:02:24,000 --> 00:02:28,000
mettre la tête à 1,

49
00:02:28,000 --> 00:02:33,000
et retourner la valeur 6.

50
00:02:33,000 --> 00:02:36,000
Ce code pourrait ressembler à ceci.

51
00:02:36,000 --> 00:02:38,000
Ici, nous avons la fonction dequeue,

52
00:02:38,000 --> 00:02:41,000
qui prend un pointeur vers la file d'attente - q - et un pointeur vers l'élément,

53
00:02:41,000 --> 00:02:44,000
qui est un type int.

54
00:02:44,000 --> 00:02:47,000
Nous avons d'abord vérifier la longueur de la file d'attente afin de s'assurer qu'il est supérieur à 0,

55
00:02:47,000 --> 00:02:50,000
faire en sorte qu'il y ait un élément de sortir de la file.

56
00:02:50,000 --> 00:02:54,000
Ensuite, nous regardons dans le tableau des éléments, à la position de la tête,

57
00:02:54,000 --> 00:02:58,000
et régler la valeur de l'élément comme étant la valeur à cette position.

58
00:02:58,000 --> 00:03:01,000
Ensuite, nous changeons la tête à l'index suivant

59
00:03:01,000 --> 00:03:04,000
% De la capacité.

60
00:03:04,000 --> 00:03:07,000
Nous avons ensuite réduire la longueur de la file d'attente de 1.

61
00:03:07,000 --> 00:03:12,000
Enfin, nous retourner true pour indiquer que le dequeue a réussi.

62
00:03:12,000 --> 00:03:19,000
Si nous dequeue encore, la longueur sera 2,

63
00:03:19,000 --> 00:03:24,000
la tête deviendra également 2,

64
00:03:24,000 --> 00:03:32,000
et la valeur de retour sera de 2.

65
00:03:32,000 --> 00:03:35,000
>> Qu'est-ce qui se passe si nous en file d'attente une autre valeur comme un 7?

66
00:03:35,000 --> 00:03:37,000
Comme nous étions à la fin de la file d'attente,

67
00:03:37,000 --> 00:03:47,000
nous aurons besoin pour envelopper et conserver la valeur en 0 élément du tableau.

68
00:03:47,000 --> 00:03:50,000
Mathématiquement, cela peut être représentée en ajoutant la longueur

69
00:03:50,000 --> 00:03:52,000
à l'indice de la tête

70
00:03:52,000 --> 00:03:55,000
et exécuter un module en utilisant la capacité de la file d'attente.

71
00:03:55,000 --> 00:04:00,000
Ici, c'est 2 +2, qui est de 4% 4,

72
00:04:00,000 --> 00:04:02,000
qui est égal à 0.

73
00:04:02,000 --> 00:04:05,000
Traduire cette idée de coder nous avons cette fonction.

74
00:04:05,000 --> 00:04:08,000
Ici, nous voyons la fonction enqueue,

75
00:04:08,000 --> 00:04:10,000
qui prend un pointeur vers la file d'attente - q -

76
00:04:10,000 --> 00:04:14,000
et a l'élément devant être mise en queue, qui est un nombre entier.

77
00:04:14,000 --> 00:04:18,000
Nous avons ensuite assurez-vous que la capacité de la file d'attente

78
00:04:18,000 --> 00:04:21,000
est encore plus grande que la longueur actuelle de la file d'attente.

79
00:04:21,000 --> 00:04:24,000
Ensuite, nous stockons l'élément dans le tableau des éléments

80
00:04:24,000 --> 00:04:30,000
à l'index est déterminée par la longueur de la tête +% de la capacité de la file d'attente.

81
00:04:30,000 --> 00:04:33,000
Nous avons ensuite augmenter la longueur de la file d'attente de 1,

82
00:04:33,000 --> 00:04:39,000
puis retourner true pour indiquer que la fonction enqueue a réussi.

83
00:04:39,000 --> 00:04:42,000
>> En plus de ces deux fonctions que nous avons mentionnés,

84
00:04:42,000 --> 00:04:44,000
il existe deux fonctions supplémentaires.

85
00:04:44,000 --> 00:04:46,000
La première est la fonction IsEmpty,

86
00:04:46,000 --> 00:04:48,000
qui prend un pointeur vers la file d'attente

87
00:04:48,000 --> 00:04:51,000
et vérifie que la longueur est 0.

88
00:04:51,000 --> 00:04:53,000
La seconde est la fonction de la longueur,

89
00:04:53,000 --> 00:04:55,000
qui prend également un pointeur vers la file d'attente

90
00:04:55,000 --> 00:04:58,000
et renvoie la longueur actuelle de la structure.

91
00:04:58,000 --> 00:05:03,000
Ce bref aperçu a démontré une éventuelle mise en œuvre d'une file d'attente.

92
00:05:03,000 --> 00:05:06,000
Une des limites de cette mise en œuvre

93
00:05:06,000 --> 00:05:08,000
est que la file d'attente a une taille maximale fixe.

94
00:05:08,000 --> 00:05:11,000
Si nous essayons d'ajouter d'autres éléments de la file d'attente peut contenir,

95
00:05:11,000 --> 00:05:14,000
nous pourrions avoir besoin pour ignorer la demande et déposer l'élément,

96
00:05:14,000 --> 00:05:17,000
ou on peut préférer d'y retourner un type d'erreur.

97
00:05:17,000 --> 00:05:20,000
En utilisant une liste chaînée plutôt qu'un tableau

98
00:05:20,000 --> 00:05:22,000
il serait plus facile à taille dynamiquement la file d'attente.

99
00:05:22,000 --> 00:05:26,000
Toutefois, étant donné que nous n'avons pas un accès direct aux éléments d'une liste chaînée,

100
00:05:26,000 --> 00:05:28,000
si l'on ne garde pas trace de la queue,

101
00:05:28,000 --> 00:05:32,000
nous aurions à parcourir la liste entière liée à arriver à la fin à chaque fois.

102
00:05:32,000 --> 00:05:35,000
On pourrait également envisager d'utiliser un tableau d'un autre type de données,

103
00:05:35,000 --> 00:05:39,000
tels que les structures, pour créer des files d'attente d'éléments plus complexes.

104
00:05:39,000 --> 00:05:42,000
En repensant à notre exemple d'une liste d'attente de classe,

105
00:05:42,000 --> 00:05:45,000
ces structures pourraient représenter les étudiants individuels.

106
00:05:45,000 --> 00:05:48,000
>> Mon nom est Chris Gerber, et c'est CS50.

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
Et retours - >> encore une fois.

109
00:05:55,000 --> 00:06:00,000
Et retourner true pour indiquer que - la file d'attente a été un succès.

110
00:06:00,000 --> 00:06:03,000
-% De la capacité de la file d'attente -

111
00:06:03,000 --> 00:06:06,000
Ça va être amusant en édition. [Rires]