1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Donc, si vous avez
regardé la vidéo sur la pile,

3
00:00:07,370 --> 00:00:09,870
Cela va probablement se sentir
comme un peu de déjà-vu.

4
00:00:09,870 --> 00:00:13,850
Il va à un concept très similaire,
seulement avec une légère torsion sur elle.

5
00:00:13,850 --> 00:00:15,530
Nous allons maintenant parler des files d'attente.

6
00:00:15,530 --> 00:00:19,350
Donc, une file d'attente, semblable à une pile,
est un autre type de structure de données

7
00:00:19,350 --> 00:00:22,412
que nous pouvons utiliser pour maintenir
les données d'une manière organisée.

8
00:00:22,412 --> 00:00:24,120
Semblable à une pile,
elle peut être réalisée

9
00:00:24,120 --> 00:00:27,000
comme un tableau ou une liste chaînée.

10
00:00:27,000 --> 00:00:30,320
Contrairement à une pile, les règles
que nous utilisons pour déterminer

11
00:00:30,320 --> 00:00:34,210
Quand les choses deviennent ajoutés ou supprimés
une file d'attente sont un peu différent.

12
00:00:34,210 --> 00:00:36,590
>> Contrairement à une pile, qui
est une structure LIFO,

13
00:00:36,590 --> 00:00:45,610
dernier entré, premier sorti, une file d'attente est une FIFO
structure FIFO, premier entré, premier sorti.

14
00:00:45,610 --> 00:00:49,320
Maintenant, les files d'attente, vous avez probablement
avoir une analogie de files d'attente.

15
00:00:49,320 --> 00:00:52,820
Si vous avez déjà été dans la ligne à
un parc d'attractions ou dans une banque,

16
00:00:52,820 --> 00:00:56,430
il ya une sorte de l'équité
la mise en oeuvre structure.

17
00:00:56,430 --> 00:00:59,160
La première personne en ligne à
la banque est la première personne

18
00:00:59,160 --> 00:01:00,760
qui arrive à parler à la caissière.

19
00:01:00,760 --> 00:01:03,522
>> Ce serait une sorte de course
vers le bas si le seul moyen

20
00:01:03,522 --> 00:01:06,730
vous avez à parler à la caissière au
banque devait être la dernière personne en ligne.

21
00:01:06,730 --> 00:01:09,146
Tout le monde voudrait toujours
être la dernière personne en ligne,

22
00:01:09,146 --> 00:01:12,580
et la personne qui était là en premier
qui a été en attente pendant un certain temps,

23
00:01:12,580 --> 00:01:14,715
pourrait être là pendant des heures,
et des heures, et des heures

24
00:01:14,715 --> 00:01:17,590
avant qu'ils aient une chance de réellement
retirer de l'argent à la banque.

25
00:01:17,590 --> 00:01:22,510
Et si les files d'attente sont en quelque sorte de la
mise en œuvre de l'équité structure.

26
00:01:22,510 --> 00:01:25,780
Mais cela ne signifie pas nécessairement
que les piles sont une mauvaise chose, juste

27
00:01:25,780 --> 00:01:28,160
que les files d'attente sont une autre façon de le faire.

28
00:01:28,160 --> 00:01:32,420
Donc encore une fois une file d'attente est premier entré, premier
sur, par rapport à une pile qui dure en,

29
00:01:32,420 --> 00:01:34,440
premier sorti.

30
00:01:34,440 --> 00:01:36,190
Semblable à une pile,
nous avons deux opérations

31
00:01:36,190 --> 00:01:38,470
que nous pouvons effectuer sur les files d'attente.

32
00:01:38,470 --> 00:01:43,910
Les noms sont en file d'attente, qui consiste à ajouter
un nouvel élément à la fin de la file d'attente,

33
00:01:43,910 --> 00:01:47,330
et dequeue, qui est
pour enlever la plus ancienne

34
00:01:47,330 --> 00:01:49,670
élément de l'avant de la file d'attente.

35
00:01:49,670 --> 00:01:53,600
Donc, nous allons ajouter des éléments
sur l'extrémité de la file d'attente,

36
00:01:53,600 --> 00:01:57,220
et nous allons supprimer des éléments
à partir de l'avant de la file d'attente.

37
00:01:57,220 --> 00:02:00,790
Encore une fois, avec la pile, nous avons ajouté
éléments au sommet de la pile

38
00:02:00,790 --> 00:02:03,380
et des éléments de retirer
à partir du haut de la pile.

39
00:02:03,380 --> 00:02:07,570
Donc, avec enqueue, il est à ajouter à
Finalement, l'élimination de l'avant.

40
00:02:07,570 --> 00:02:10,639
Ainsi, la plus vieille chose là
est toujours la chose suivante

41
00:02:10,639 --> 00:02:13,620
de sortir si nous essayons
et dequeue quelque chose.

42
00:02:13,620 --> 00:02:18,330
>> Donc encore une fois, avec des files d'attente, nous pouvons
implémentations sur baie

43
00:02:18,330 --> 00:02:20,110
et liste liée implémentations basées.

44
00:02:20,110 --> 00:02:24,620
Nous allons commencer à nouveau avec
implémentations sur les baies.

45
00:02:24,620 --> 00:02:27,070
La définition de la structure
semble assez similaire.

46
00:02:27,070 --> 00:02:30,720
Nous avons un autre tableau
il de la valeur de type de données,

47
00:02:30,720 --> 00:02:32,690
de sorte qu'il peut contenir des types de données arbitraires.

48
00:02:32,690 --> 00:02:35,570
Nous allons utiliser à nouveau
des nombres entiers dans cet exemple.

49
00:02:35,570 --> 00:02:39,830
>> Et tout comme avec notre
la mise en œuvre de la pile basée sur la baie,

50
00:02:39,830 --> 00:02:42,340
parce que nous sommes en utilisant un
tableau, nous avons nécessairement

51
00:02:42,340 --> 00:02:46,850
avoir cette limitation que C genre
du fait respecter sur nous, ce qui est nous

52
00:02:46,850 --> 00:02:51,670
ne pas avoir de dynamisme dans notre
capacité à croître et rétrécir le tableau.

53
00:02:51,670 --> 00:02:55,710
Nous devons décider au début
Quel est le nombre maximum de choses

54
00:02:55,710 --> 00:02:59,300
que nous pouvons mettre dans cette
file d'attente, et dans ce cas,

55
00:02:59,300 --> 00:03:02,070
la capacité serait une livre
constante définie dans notre code.

56
00:03:02,070 --> 00:03:05,430
Et pour les fins de la présente
vidéo, la capacité va être 10.

57
00:03:05,430 --> 00:03:07,690
>> Nous avons besoin de garder une trace de
la face de la file d'attente

58
00:03:07,690 --> 00:03:11,160
nous savons donc quel élément
nous voulons dequeue,

59
00:03:11,160 --> 00:03:15,070
et nous avons aussi besoin de garder une trace de
quelque chose else-- le nombre d'éléments

60
00:03:15,070 --> 00:03:16,690
que nous avons dans notre file d'attente.

61
00:03:16,690 --> 00:03:19,360
Remarquez que nous ne sommes pas garder la trace
de la fin de la file d'attente, juste

62
00:03:19,360 --> 00:03:21,150
la taille de la file d'attente.

63
00:03:21,150 --> 00:03:24,310
Et la raison de qui nous l'espérons
devenu un peu plus clair dans un instant.

64
00:03:24,310 --> 00:03:26,143
Une fois que nous avons terminé
cette définition de type,

65
00:03:26,143 --> 00:03:29,080
nous avons un nouveau type de données
appelée file d'attente, ce qui nous pouvons maintenant

66
00:03:29,080 --> 00:03:30,630
déclarer des variables de ce type de données.

67
00:03:30,630 --> 00:03:35,350
Et peu à confusion, je me suis décidé
d'appeler cette file d'attente q, la lettre

68
00:03:35,350 --> 00:03:38,090
q à la place du type de données q.

69
00:03:38,090 --> 00:03:39,600
>> Donc voici notre file d'attente.

70
00:03:39,600 --> 00:03:40,700
Il est d'une structure.

71
00:03:40,700 --> 00:03:45,730
Il contient trois membres ou trois
champs, un tableau de taille CAPACITÉ.

72
00:03:45,730 --> 00:03:47,340
Dans ce cas, la capacité est de 10.

73
00:03:47,340 --> 00:03:49,580
Et ce tableau est
va tenir entiers.

74
00:03:49,580 --> 00:03:55,240
Dans le vert est la face de notre file d'attente, la
l'élément suivant à être enlevé, et en rouge

75
00:03:55,240 --> 00:03:58,610
sera la taille de la file d'attente,
combien d'éléments sont actuellement

76
00:03:58,610 --> 00:04:01,190
qui sont dans la file d'attente.

77
00:04:01,190 --> 00:04:05,300
Donc, si nous disons égaux q.front
0, et la taille de q.size égale 0--

78
00:04:05,300 --> 00:04:07,120
nous mettons 0s dans ces domaines.

79
00:04:07,120 --> 00:04:11,070
Et à ce moment, nous sommes à peu près
prêt à commencer à travailler avec notre file d'attente.

80
00:04:11,070 --> 00:04:14,140
>> Donc, la première opération que nous pouvons
à effectuer est en file d'attente de quelque chose,

81
00:04:14,140 --> 00:04:16,860
pour ajouter un nouvel élément à
la fin de la file d'attente.

82
00:04:16,860 --> 00:04:19,089
Eh bien ce que devons-nous
faire dans le cas général?

83
00:04:19,089 --> 00:04:23,690
Eh bien cette fonction en file d'attente besoins
à accepter un pointeur à notre file d'attente.

84
00:04:23,690 --> 00:04:26,370
Encore une fois, si nous avions déclaré
notre file d'attente à l'échelle mondiale,

85
00:04:26,370 --> 00:04:29,490
nous ne serions pas besoin de faire cela
nécessairement, mais en général, nous

86
00:04:29,490 --> 00:04:32,330
besoin d'accepter des pointeurs
de structures de données

87
00:04:32,330 --> 00:04:35,040
comme ça, parce que sinon,
nous passons par value-- nous sommes

88
00:04:35,040 --> 00:04:38,140
passant dans les copies de la file d'attente,
et donc nous ne sommes pas réellement changer

89
00:04:38,140 --> 00:04:41,050
la file d'attente que nous avons l'intention de changer.

90
00:04:41,050 --> 00:04:44,860
>> L'autre chose qu'il doit faire est d'accepter
un élément de données du type approprié.

91
00:04:44,860 --> 00:04:46,818
Là encore, dans ce cas, il est
va être entiers,

92
00:04:46,818 --> 00:04:49,330
Mais vous pourriez arbitrairement
déclarer le type de données que la valeur

93
00:04:49,330 --> 00:04:51,160
et utiliser ce plus généralement.

94
00:04:51,160 --> 00:04:56,030
Voilà l'élément que nous voulons en file d'attente,
nous voulons ajouter à la fin de la file d'attente.

95
00:04:56,030 --> 00:04:58,573
Ensuite, nous voulons effectivement
placer ces données dans la file d'attente.

96
00:04:58,573 --> 00:05:01,490
Dans ce cas, le plaçant dans le
emplacement correct de notre tableau,

97
00:05:01,490 --> 00:05:05,040
et ensuite nous voulons changer la taille
de la file d'attente, le nombre d'éléments nous

98
00:05:05,040 --> 00:05:07,050
ont actuellement.

99
00:05:07,050 --> 00:05:07,990
>> Donc, nous allons commencer.

100
00:05:07,990 --> 00:05:10,890
Voici, encore une fois, que le général
déclaration de fonction de forme

101
00:05:10,890 --> 00:05:13,980
pour ce enqueue pourrait ressembler.

102
00:05:13,980 --> 00:05:14,910
Et c'est reparti.

103
00:05:14,910 --> 00:05:18,335
Disons ENQUEUE le nombre
28 dans la file d'attente.

104
00:05:18,335 --> 00:05:19,460
Alors qu'est-ce qu'on va faire?

105
00:05:19,460 --> 00:05:23,390
Eh bien, la face de notre file d'attente est
à 0, et la taille de notre file d'attente

106
00:05:23,390 --> 00:05:29,680
est à 0, et donc nous voulons probablement de mettre
le nombre 28 dans le tableau numéro d'élément

107
00:05:29,680 --> 00:05:31,124
0, non?

108
00:05:31,124 --> 00:05:32,540
Donc, nous avons désormais mis ça là.

109
00:05:32,540 --> 00:05:34,820
Alors maintenant, que devons-nous changer?

110
00:05:34,820 --> 00:05:37,090
Nous ne voulons pas changer
l'avant de la file d'attente,

111
00:05:37,090 --> 00:05:40,850
parce que nous voulons savoir ce que l'élément
nous pourrions avoir besoin de dequeue tard.

112
00:05:40,850 --> 00:05:44,020
Donc, la raison pour laquelle nous avons avant il
est une sorte d'indicateur de ce qui est

113
00:05:44,020 --> 00:05:46,439
la plus vieille chose dans le tableau.

114
00:05:46,439 --> 00:05:49,730
Eh bien, la plus vieille chose dans le array-- dans
fait, la seule chose dans le tableau à droite

115
00:05:49,730 --> 00:05:53,540
est maintenant-- 28, qui est
à l'emplacement de tableau 0.

116
00:05:53,540 --> 00:05:56,160
Donc, nous ne voulons pas
changer ce numéro vert,

117
00:05:56,160 --> 00:05:57,910
parce que ce l'élément le plus ancien.

118
00:05:57,910 --> 00:06:00,510
Au contraire, nous voulons changer la taille.

119
00:06:00,510 --> 00:06:04,110
Donc dans ce cas, nous allons
incrémenter la taille à 1.

120
00:06:04,110 --> 00:06:08,430
>> Maintenant, une sorte de général idée d'où le
élément suivant va aller dans une file d'attente

121
00:06:08,430 --> 00:06:12,310
est d'ajouter ces deux nombres
ensemble, avant et taille,

122
00:06:12,310 --> 00:06:16,390
et que vais vous dire où la prochaine
élément dans la file d'attente va aller.

123
00:06:16,390 --> 00:06:18,130
Alors maintenant, nous allons ENQUEUE un autre numéro.

124
00:06:18,130 --> 00:06:20,250
Disons ENQUEUE 33.

125
00:06:20,250 --> 00:06:24,480
Donc 33 va aller dans
Lieu de gamme 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Donc dans ce cas, il va
pour aller dans l'emplacement du tableau 1,

127
00:06:26,840 --> 00:06:29,500
et maintenant la taille de notre file d'attente est de 2.

128
00:06:29,500 --> 00:06:31,840
>> Encore une fois, nous ne sommes pas changer
l'avant de notre file d'attente,

129
00:06:31,840 --> 00:06:34,730
parce que 28 est toujours le
le plus ancien élément, et nous

130
00:06:34,730 --> 00:06:38,220
to-- veulent quand nous obtenons finalement
à dequeuing, la suppression d'éléments

131
00:06:38,220 --> 00:06:43,300
à partir de cette file d'attente, nous voulons savoir
où l'élément le plus ancien est.

132
00:06:43,300 --> 00:06:48,620
Et donc nous avons toujours besoin de maintenir
un indicateur de l'endroit où ce qui est.

133
00:06:48,620 --> 00:06:50,410
Voilà ce que le 0 est là pour cela.

134
00:06:50,410 --> 00:06:52,910
Voilà ce que l'avant est là pour cela.

135
00:06:52,910 --> 00:06:55,022
>> Voyons dans enqueue un élément de plus, 19.

136
00:06:55,022 --> 00:06:56,980
Je suis sûr que vous pouvez deviner
où 19 va aller.

137
00:06:56,980 --> 00:06:59,860
Il va aller dans
tableau emplacement numéro 2.

138
00:06:59,860 --> 00:07:01,570
Voilà plus 2 0.

139
00:07:01,570 --> 00:07:03,199
Et maintenant, la taille de notre file d'attente est de 3.

140
00:07:03,199 --> 00:07:04,240
Nous avons 3 éléments en elle.

141
00:07:04,240 --> 00:07:08,490
Donc, si nous devions, et on ne va pas
à ce moment, un autre élément en file d'attente,

142
00:07:08,490 --> 00:07:11,370
il irait dans l'emplacement de tableau
Numéro 3, et la taille de notre file d'attente

143
00:07:11,370 --> 00:07:13,160
serait 4.

144
00:07:13,160 --> 00:07:15,279
Nous avons donc mis en file plusieurs éléments maintenant.

145
00:07:15,279 --> 00:07:16,570
Maintenant, nous allons commencer à les retirer.

146
00:07:16,570 --> 00:07:19,450
Donnons-leur DEQUEUE de la file.

147
00:07:19,450 --> 00:07:23,340
>> Si semblable à la pop, qui est une sorte
de l'analogue de ce pour les piles,

148
00:07:23,340 --> 00:07:26,180
dequeue doit accepter un
pointeur vers le nouveau queue--,

149
00:07:26,180 --> 00:07:28,140
sauf si elle est déclarée à l'échelle mondiale.

150
00:07:28,140 --> 00:07:31,610
Maintenant, nous voulons changer l'emplacement
de l'avant de la file d'attente.

151
00:07:31,610 --> 00:07:35,050
Ceci est où il vient sorte de
en jeu, cette variable avant,

152
00:07:35,050 --> 00:07:37,310
car une fois que nous enlevons
un élément, nous voulons

153
00:07:37,310 --> 00:07:40,720
pour le déplacer vers le prochain élément le plus ancien.

154
00:07:40,720 --> 00:07:44,180
>> Ensuite, nous voulons diminuer
la taille de la file d'attente,

155
00:07:44,180 --> 00:07:47,130
et ensuite nous voulons retourner la valeur
qui a été retiré de la file d'attente.

156
00:07:47,130 --> 00:07:48,921
Encore une fois, nous ne voulons pas simplement le jeter.

157
00:07:48,921 --> 00:07:51,170
Nous vraisemblablement extrayons
à partir de la queue-- nous sommes

158
00:07:51,170 --> 00:07:54,170
dequeuing parce que nous nous soucions de lui.

159
00:07:54,170 --> 00:08:01,080
Donc, nous voulons cette fonction pour revenir
un élément de données d'une valeur de type.

160
00:08:01,080 --> 00:08:04,360
Encore une fois, dans ce cas, la valeur est entier.

161
00:08:04,360 --> 00:08:05,670
>> Alors maintenant, nous allons DEQUEUE quelque chose.

162
00:08:05,670 --> 00:08:09,310
Enlevons un élément de la file d'attente.

163
00:08:09,310 --> 00:08:15,970
Si nous disons int x est égal & q, esperluette q--
nouveau ce est un pointeur vers ces données q

164
00:08:15,970 --> 00:08:20,177
structure-- quel élément
va être dequeued?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
Dans ce cas, parce qu'il est un premier
entré, premier sorti structure de données, FIFO,

167
00:08:29,480 --> 00:08:33,690
la première chose que nous mettons dans ce
file d'attente était de 28, et dans ce cas,

168
00:08:33,690 --> 00:08:37,245
nous allons prendre 28 sur
la file d'attente, et non pas 19, ce qui est

169
00:08:37,245 --> 00:08:38,870
nous aurions fait si cela avait une pile.

170
00:08:38,870 --> 00:08:42,220
Nous allons prendre 28 hors de la file d'attente.

171
00:08:42,220 --> 00:08:44,960
>> Semblable à ce que nous avons fait avec
une pile, nous ne sommes pas réellement

172
00:08:44,960 --> 00:08:47,345
va supprimer 28
à partir de la file d'attente elle-même,

173
00:08:47,345 --> 00:08:49,470
nous allons juste genre
de prétendre qu'il n'y est pas.

174
00:08:49,470 --> 00:08:51,678
Donc il va y rester
dans la mémoire, mais nous sommes juste

175
00:08:51,678 --> 00:08:57,820
aller au genre de l'ignorer en déplaçant
les deux autres domaines de nos données q

176
00:08:57,820 --> 00:08:58,830
la structure.

177
00:08:58,830 --> 00:09:00,230
Nous allons changer l'avant.

178
00:09:00,230 --> 00:09:04,290
Q.front va maintenant
être 1, car cela est maintenant

179
00:09:04,290 --> 00:09:07,740
l'élément le plus ancien que nous avons dans notre
file d'attente, parce que nous avons déjà enlevé 28,

180
00:09:07,740 --> 00:09:10,460
qui était l'ancien élément le plus ancien.

181
00:09:10,460 --> 00:09:13,540
>> Et maintenant, nous voulons changer
la taille de la file d'attente

182
00:09:13,540 --> 00:09:15,780
à deux éléments au lieu de trois.

183
00:09:15,780 --> 00:09:20,450
Maintenant, rappelez-tôt je l'ai dit lorsque nous
vouloir ajouter des éléments à la file d'attente,

184
00:09:20,450 --> 00:09:26,000
on le met dans une situation de tableau
qui est la somme de l'avant et de taille.

185
00:09:26,000 --> 00:09:29,050
Donc dans ce cas, nous sommes encore en mettant
il, l'élément suivant dans la file d'attente,

186
00:09:29,050 --> 00:09:33,360
dans l'emplacement du tableau 3, et
nous verrons que, dans une seconde.

187
00:09:33,360 --> 00:09:35,730
>> Donc, nous avons maintenant notre dequeued
premier élément de la file.

188
00:09:35,730 --> 00:09:36,480
Faisons le encore.

189
00:09:36,480 --> 00:09:38,696
Enlevons autre
élément de la file d'attente.

190
00:09:38,696 --> 00:09:42,400
Dans le cas, le courant le plus ancien
élément est l'emplacement du tableau 1.

191
00:09:42,400 --> 00:09:44,220
Voilà ce que nous dit q.front.

192
00:09:44,220 --> 00:09:46,980
Cette boîte verte nous dit que
qui est l'élément le plus ancien.

193
00:09:46,980 --> 00:09:49,310
Et donc, deviendra x 33.

194
00:09:49,310 --> 00:09:52,130
Nous allons juste genre de oublions
qui 33 existe dans le tableau,

195
00:09:52,130 --> 00:09:55,100
et nous disons que maintenant, la
nouveau plus ancien élément de la file d'attente

196
00:09:55,100 --> 00:09:58,900
est au tableau localité 2, et de la taille
de la file d'attente, le nombre d'éléments

197
00:09:58,900 --> 00:10:02,152
nous avons dans la file d'attente, est 1.

198
00:10:02,152 --> 00:10:05,110
Maintenant, nous allons ENQUEUE quelque chose, et je
sorte de donné cette distance il ya une seconde,

199
00:10:05,110 --> 00:10:10,340
mais si nous voulons mettre 40 dans la
file d'attente, où est 40 va aller?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Eh bien, nous avons été le mettons
en plus de file d'attente q.front taille,

202
00:10:17,730 --> 00:10:20,850
et il fait donc sens pour
effectivement de mettre 40 ici.

203
00:10:20,850 --> 00:10:22,840
Maintenant, remarquez qu'au
un certain point, nous allons

204
00:10:22,840 --> 00:10:27,980
se rendre à la fin de
notre tableau à l'intérieur de q,

205
00:10:27,980 --> 00:10:32,010
mais fanée sur 28 et 33--
ils sont en fait, techniquement

206
00:10:32,010 --> 00:10:33,300
espaces ouverts, non?

207
00:10:33,300 --> 00:10:36,040
Et donc, nous pouvons eventually--
cette règle d'ajouter

208
00:10:36,040 --> 00:10:40,390
ces deux together-- nous pouvons éventuellement
mod besoin de par la taille de la capacité

209
00:10:40,390 --> 00:10:41,410
afin que nous puissions envelopper.

210
00:10:41,410 --> 00:10:43,620
>> Donc, si nous arrivons à l'élément
Numéro 10, si nous sommes

211
00:10:43,620 --> 00:10:48,790
remplaçant dans l'élément numéro 10, nous serions
effectivement le mettre dans un endroit de tableau 0.

212
00:10:48,790 --> 00:10:50,997
Et si nous allions
tableau location-- excusez-moi,

213
00:10:50,997 --> 00:10:53,080
si nous les avons ajoutés ensemble,
et nous sommes arrivés à nombre

214
00:10:53,080 --> 00:10:56,330
11 serait le cas où nous aurions à mettre
, ce qui ne existe pas dans ce array--

215
00:10:56,330 --> 00:10:58,200
ce serait aller en dehors des limites.

216
00:10:58,200 --> 00:11:03,367
Nous pourrions mod de 10 et de mettre
dans l'emplacement du tableau 1.

217
00:11:03,367 --> 00:11:04,450
Voilà donc comment fonctionnent les files d'attente.

218
00:11:04,450 --> 00:11:08,540
Ils vont toujours aller de gauche à droite
à droite et éventuellement enrouler autour.

219
00:11:08,540 --> 00:11:11,280
Et vous savez qu'ils sont
complète si la taille, cette boîte rouge,

220
00:11:11,280 --> 00:11:13,710
devient égale à la capacité.

221
00:11:13,710 --> 00:11:16,720
Et donc après nous avons ajouté 40 à la
file d'attente, ainsi que devons-nous faire?

222
00:11:16,720 --> 00:11:19,890
Eh bien, l'élément le plus ancien
dans la file d'attente est toujours 19,

223
00:11:19,890 --> 00:11:21,990
de sorte que nous ne voulons pas changer
l'avant de la file d'attente,

224
00:11:21,990 --> 00:11:23,820
mais maintenant nous avons deux
éléments dans la file d'attente,

225
00:11:23,820 --> 00:11:28,710
et donc nous voulons augmenter
notre taille de 1 à 2.

226
00:11:28,710 --> 00:11:31,820
>> Voilà à peu près tout avec
travailler avec des files d'attente sur les baies,

227
00:11:31,820 --> 00:11:33,630
et semblable à empiler,
il ya également un moyen

228
00:11:33,630 --> 00:11:36,450
de mettre en œuvre une file d'attente comme une liste chaînée.

229
00:11:36,450 --> 00:11:40,150
Or, si ce type de structure de données
semble familier pour vous, il est.

230
00:11:40,150 --> 00:11:43,780
Il est pas une liste chaînée,
il est une liste doublement chaînée.

231
00:11:43,780 --> 00:11:46,790
Et maintenant, comme un côté, il est
effectivement possible de mettre en œuvre

232
00:11:46,790 --> 00:11:50,160
une file d'attente comme une liste chaînée, mais
Je pense en termes de visualisation,

233
00:11:50,160 --> 00:11:53,350
il fait pourrait aider à voir
cela comme une liste doublement chaînée.

234
00:11:53,350 --> 00:11:56,850
Mais il est certainement possible de
faire cela comme une liste chaînée.

235
00:11:56,850 --> 00:12:00,110
>> Donc, nous allons jeter un oeil à
ce que cela pourrait ressembler.

236
00:12:00,110 --> 00:12:02,750
Si nous voulons enquue--
alors maintenant, nous sommes à nouveau

237
00:12:02,750 --> 00:12:05,360
le passage à une liste chaînée
modèle basé ici.

238
00:12:05,360 --> 00:12:08,420
Si nous voulons en file d'attente, nous voulons
pour ajouter un nouvel élément, ainsi

239
00:12:08,420 --> 00:12:09,730
Que devons-nous faire?

240
00:12:09,730 --> 00:12:12,770
Eh bien, tout d'abord, parce que
nous ajoutons à la fin

241
00:12:12,770 --> 00:12:15,520
et l'élimination de la
commencer, nous avons probablement

242
00:12:15,520 --> 00:12:20,050
veulent maintenir pointeurs à la fois le
la tête et la queue de la liste chaînée?

243
00:12:20,050 --> 00:12:22,660
Tail être un autre terme pour
la fin de la liste liée,

244
00:12:22,660 --> 00:12:24,496
le dernier élément de la liste chaînée.

245
00:12:24,496 --> 00:12:26,620
Et ce sera probablement,
encore une fois, être bénéfique pour nous

246
00:12:26,620 --> 00:12:28,477
si elles sont des variables globales.

247
00:12:28,477 --> 00:12:31,060
Mais maintenant, si nous voulons ajouter un nouveau
élément que devons-nous faire?

248
00:12:31,060 --> 00:12:35,262
Ce que nous venons [? Malak?] ou dynamiquement
allouer notre nouveau noeud pour nous-mêmes.

249
00:12:35,262 --> 00:12:38,220
Et puis, tout comme lorsque nous ajoutons tout
élément à une liste que nous avons doublement chaînée,

250
00:12:38,220 --> 00:12:40,410
suffit de trier de--
ces trois dernières étapes ici

251
00:12:40,410 --> 00:12:43,330
sont juste tout sur le déplacement du
pointeurs dans le bon sens

252
00:12:43,330 --> 00:12:46,710
de sorte que l'élément est ajouté à
la chaîne sans rupture de la chaîne

253
00:12:46,710 --> 00:12:49,580
ou de faire une sorte de erreur
ou d'avoir une sorte d'accident

254
00:12:49,580 --> 00:12:54,505
arriver lequel nous avons accidentellement
orphelin quelques éléments de notre file d'attente.

255
00:12:54,505 --> 00:12:55,880
Voici ce que cela pourrait ressembler.

256
00:12:55,880 --> 00:13:00,980
Nous voulons ajouter l'élément
10 à la fin de cette file d'attente.

257
00:13:00,980 --> 00:13:03,380
Donc, l'élément le plus ancien ici
est représenté par la tête.

258
00:13:03,380 --> 00:13:06,800
Voilà la première chose que nous avons mis
dans cette file d'attente hypothétique ici.

259
00:13:06,800 --> 00:13:10,430
Et la queue, 13, est le plus
élément récemment ajouté.

260
00:13:10,430 --> 00:13:17,030
Et si nous voulons en file d'attente dans 10
cette file d'attente, nous voulons le mettre après le 13.

261
00:13:17,030 --> 00:13:19,860
Et donc nous allons dynamiquement
allouer de l'espace pour un nouveau noeud

262
00:13:19,860 --> 00:13:23,280
et vérifier null pour vous assurer
nous ne disposons pas d'une défaillance de la mémoire.

263
00:13:23,280 --> 00:13:27,040
Ensuite, nous allons
placer 10 dans ce nœud,

264
00:13:27,040 --> 00:13:30,030
et maintenant nous devons être prudents
sur la façon dont nous organisons des pointeurs

265
00:13:30,030 --> 00:13:32,180
afin de ne pas briser la chaîne.

266
00:13:32,180 --> 00:13:38,910
>> Nous pouvons mettre en champ précédent de 10
pour pointer à la vieille queue,

267
00:13:38,910 --> 00:13:41,620
et depuis '10 sera le
nouvelle queue à un certain point

268
00:13:41,620 --> 00:13:44,459
au moment où l'ensemble de ces
les chaînes sont connectés,

269
00:13:44,459 --> 00:13:46,250
rien ne va à venir
après 10 dès maintenant.

270
00:13:46,250 --> 00:13:49,880
Et donc la prochaine pointeur de 10
pointera à null,

271
00:13:49,880 --> 00:13:53,580
et puis après nous faisons cela, après que nous ayons
10 vers l'arrière reliée à la chaîne,

272
00:13:53,580 --> 00:13:57,780
nous pouvons prendre la vieille tête, ou, excuse
moi, la vieille queue de la file d'attente.

273
00:13:57,780 --> 00:14:02,980
Le vieux fin de la file d'attente,
13, et le faire pointer vers 10.

274
00:14:02,980 --> 00:14:08,220
Et maintenant, à ce stade, nous avons
en file d'attente le numéro 10 dans cette file d'attente.

275
00:14:08,220 --> 00:14:14,740
Tout ce que nous devons faire maintenant est simplement déplacer le
queue pour pointer sur la place de 10 à 13.

276
00:14:14,740 --> 00:14:17,630
>> Est en fait dequeuing
très similaire à éclater

277
00:14:17,630 --> 00:14:21,710
à partir d'une pile qui est
mis en œuvre comme une liste chaînée

278
00:14:21,710 --> 00:14:24,040
si vous avez vu la vidéo des piles.

279
00:14:24,040 --> 00:14:27,280
Tout ce que nous devons faire est de commencer à la
commencer, trouvez le deuxième élément,

280
00:14:27,280 --> 00:14:30,480
libérer le premier élément,
et puis déplacez la tête

281
00:14:30,480 --> 00:14:32,930
pour pointer vers le second élément.

282
00:14:32,930 --> 00:14:37,920
Probablement mieux le visualiser
juste pour être très clair à ce sujet.

283
00:14:37,920 --> 00:14:39,230
Alors, voici à nouveau notre file d'attente.

284
00:14:39,230 --> 00:14:42,600
12 est l'élément le plus ancien
dans notre file d'attente, la tête.

285
00:14:42,600 --> 00:14:46,210
10 est l'élément le plus récent
dans notre file d'attente, notre queue.

286
00:14:46,210 --> 00:14:49,310
>> Et donc quand nous voulons
dequeue à un élément,

287
00:14:49,310 --> 00:14:52,202
nous voulons supprimer l'élément le plus ancien.

288
00:14:52,202 --> 00:14:52,910
Alors que faisons-nous?

289
00:14:52,910 --> 00:14:55,243
Eh bien nous avons mis un pointeur de parcours
qui commence à la tête,

290
00:14:55,243 --> 00:14:57,840
et nous nous déplaçons pour qu'il
des points sur le second élément

291
00:14:57,840 --> 00:15:02,290
de cette queue-- quelque chose en disant trav
égal trav flèche à côté, par exemple,

292
00:15:02,290 --> 00:15:07,170
ferait passer trav là pour pointer vers
15, qui, après nous DEQUEUE 12,

293
00:15:07,170 --> 00:15:13,030
ou après nous enlevons 12, sera
devenu l'élément puis plus ancienne.

294
00:15:13,030 --> 00:15:16,360
>> Maintenant, nous avons une emprise sur le premier
élément via la tête de pointeur

295
00:15:16,360 --> 00:15:19,440
et le second élément
via le pointeur de trav.

296
00:15:19,440 --> 00:15:25,170
Nous pouvons tête maintenant libre, et alors nous pouvons
rien ne vient dire avant le 15 plus.

297
00:15:25,170 --> 00:15:29,990
Donc, nous pouvons changer de 15 précédente
pointeur pour pointer vers null,

298
00:15:29,990 --> 00:15:31,874
et nous passons juste la tête au-dessus.

299
00:15:31,874 --> 00:15:32,540
Et là nous allons.

300
00:15:32,540 --> 00:15:35,840
Maintenant, nous avons avec succès
dequeued 12, et maintenant nous

301
00:15:35,840 --> 00:15:39,180
avoir une autre file d'attente de 4 éléments.

302
00:15:39,180 --> 00:15:41,700
Voilà à peu près tout
il ya des files d'attente,

303
00:15:41,700 --> 00:15:45,810
à la fois basée sur la baie et la liste chaînée base.

304
00:15:45,810 --> 00:15:46,860
Je suis Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Ceci est 50 CS.

306
00:15:49,100 --> 00:15:50,763