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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Dus als je hebt
keek naar de video op stapel,

3
00:00:07,370 --> 00:00:09,870
Dit is waarschijnlijk te voelen
als een beetje van deja vu.

4
00:00:09,870 --> 00:00:13,850
Het gaat om een ​​zeer vergelijkbaar concept,
alleen met een lichte draai aan het.

5
00:00:13,850 --> 00:00:15,530
We gaan nu over wachtrijen.

6
00:00:15,530 --> 00:00:19,350
Dus een wachtrij, gelijkend op een stapel,
is een ander soort gegevensstructuur

7
00:00:19,350 --> 00:00:22,412
die we kunnen gebruiken om te behouden
data op een georganiseerde manier.

8
00:00:22,412 --> 00:00:24,120
Net als een stapel,
het kan worden toegepast

9
00:00:24,120 --> 00:00:27,000
als een matrix of een gekoppelde lijst.

10
00:00:27,000 --> 00:00:30,320
In tegenstelling tot een stapel, de regels
die we gebruiken om te bepalen

11
00:00:30,320 --> 00:00:34,210
wanneer dingen toegevoegd en verwijderd uit
een wachtrij zijn een beetje anders.

12
00:00:34,210 --> 00:00:36,590
>> In tegenstelling tot een stapel, die
een LIFO structuur

13
00:00:36,590 --> 00:00:45,610
last in, first out, een wachtrij is een FIFO
structuur, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Nu wachtrijen, u waarschijnlijk
hebben een analogie met wachtrijen.

15
00:00:49,320 --> 00:00:52,820
Als je ooit in de lijn geweest bij
een pretpark of bij een bank,

16
00:00:52,820 --> 00:00:56,430
er is een soort van een fairness
uitvoeringsstructuur.

17
00:00:56,430 --> 00:00:59,160
De eerste persoon in de rij bij
de bank is de eerste persoon

18
00:00:59,160 --> 00:01:00,760
wie krijgt om de teller te spreken.

19
00:01:00,760 --> 00:01:03,522
>> Het zou een soort van race
naar beneden als de enige manier

20
00:01:03,522 --> 00:01:06,730
je moet de teller bij het spreken
bank was de laatste persoon in de rij zijn.

21
00:01:06,730 --> 00:01:09,146
Iedereen zou willen altijd
om de laatste persoon in de rij,

22
00:01:09,146 --> 00:01:12,580
en de persoon die als eerste was er
die heeft gewacht voor een tijdje,

23
00:01:12,580 --> 00:01:14,715
zou er voor uren,
en uren en uren

24
00:01:14,715 --> 00:01:17,590
voordat ze een kans hebben om daadwerkelijk
geen geld bij de bank te trekken.

25
00:01:17,590 --> 00:01:22,510
En zo wachtrijen zijn soort van de
billijkheid uitvoeringsstructuur.

26
00:01:22,510 --> 00:01:25,780
Maar dat betekent niet noodzakelijk
dat stapels zijn een slechte zaak, maar

27
00:01:25,780 --> 00:01:28,160
dat de wachtrijen zijn een andere manier om het te doen.

28
00:01:28,160 --> 00:01:32,420
Dus nogmaals een wachtrij is first in, first
out, tegenover een stapel die last in,

29
00:01:32,420 --> 00:01:34,440
first out.

30
00:01:34,440 --> 00:01:36,190
Net als een stapel,
we hebben twee operaties

31
00:01:36,190 --> 00:01:38,470
die we kunnen uitvoeren op wachtrijen.

32
00:01:38,470 --> 00:01:43,910
De namen zijn enqueue, dat is toe te voegen
een nieuw element aan het einde van de wachtrij,

33
00:01:43,910 --> 00:01:47,330
en dequeue, dat is
het oudste verwijderen

34
00:01:47,330 --> 00:01:49,670
element vanaf de voorkant van de wachtrij.

35
00:01:49,670 --> 00:01:53,600
Dus we gaan om elementen toe te voegen
op het einde van de wachtrij,

36
00:01:53,600 --> 00:01:57,220
en we gaan om elementen te verwijderen
vanaf de voorkant van de wachtrij.

37
00:01:57,220 --> 00:02:00,790
Opnieuw, met de stack, werden we voegen
elementen naar de top van de stack

38
00:02:00,790 --> 00:02:03,380
en het verwijderen van onderdelen
van de bovenkant van de stapel.

39
00:02:03,380 --> 00:02:07,570
Dus met enqueue, is het toe te voegen aan
Uiteindelijk verwijderen van voren.

40
00:02:07,570 --> 00:02:10,639
Dus de oudste ding er
is altijd het volgende ding

41
00:02:10,639 --> 00:02:13,620
om uit te komen als we proberen
en dequeue iets.

42
00:02:13,620 --> 00:02:18,330
>> Dus nogmaals, met wachtrijen, kunnen wij
array-gebaseerde implementaties

43
00:02:18,330 --> 00:02:20,110
en gekoppeld-lijst gebaseerde implementaties.

44
00:02:20,110 --> 00:02:24,620
We zullen weer beginnen met
array-gebaseerde implementaties.

45
00:02:24,620 --> 00:02:27,070
De structuurdefinitie
ziet er redelijk vergelijkbaar.

46
00:02:27,070 --> 00:02:30,720
We hebben een andere array
er gegevens soort waarde,

47
00:02:30,720 --> 00:02:32,690
dus het kan willekeurige data types te houden.

48
00:02:32,690 --> 00:02:35,570
We zijn weer gaan gebruiken
integers in dit voorbeeld.

49
00:02:35,570 --> 00:02:39,830
>> En net als met onze
array-gebaseerde stack implementatie,

50
00:02:39,830 --> 00:02:42,340
omdat we met behulp van een
array, we noodzakelijkerwijs

51
00:02:42,340 --> 00:02:46,850
hebben die beperking dat soort C
van dwingt ons, die we

52
00:02:46,850 --> 00:02:51,670
hebben geen dynamiek in niet onze
vermogen om te groeien en krimpen van de array.

53
00:02:51,670 --> 00:02:55,710
We moeten beslissen begin
Wat is het maximum aantal dingen

54
00:02:55,710 --> 00:02:59,300
dat we in deze kunnen zetten
wachtrij, en in dit geval,

55
00:02:59,300 --> 00:03:02,070
capaciteit zou wat zijn pond
gedefinieerde constante in onze code.

56
00:03:02,070 --> 00:03:05,430
En voor de toepassing van deze
video, wordt vermogen gaat worden 10.

57
00:03:05,430 --> 00:03:07,690
>> We moeten houden van
de voorkant van de wachtrij

58
00:03:07,690 --> 00:03:11,160
zodat we weten welke element
we willen dequeue,

59
00:03:11,160 --> 00:03:15,070
en we moeten ook bijhouden
iets else-- het aantal elementen

60
00:03:15,070 --> 00:03:16,690
dat we in onze rij.

61
00:03:16,690 --> 00:03:19,360
Merken we niet bijhouden
het einde van de wachtrij, net

62
00:03:19,360 --> 00:03:21,150
de grootte van de wachtrij.

63
00:03:21,150 --> 00:03:24,310
En de reden daarvoor zal hopelijk
word een beetje duidelijker in een moment.

64
00:03:24,310 --> 00:03:26,143
Zodra we hebben afgerond
dit type definitie

65
00:03:26,143 --> 00:03:29,080
wij hebben een nieuw type data
genaamd wachtrij, die we kunnen nu

66
00:03:29,080 --> 00:03:30,630
verklaren variabelen van dat type data.

67
00:03:30,630 --> 00:03:35,350
En enigszins verwarrend, heb ik besloten
te roepen deze wachtrij q, de letter

68
00:03:35,350 --> 00:03:38,090
q in plaats van het type data q.

69
00:03:38,090 --> 00:03:39,600
>> Dus hier is onze wachtrij.

70
00:03:39,600 --> 00:03:40,700
Het is een structuur.

71
00:03:40,700 --> 00:03:45,730
Het bevat drie leden of drie
velden, een array van grootte capaciteit.

72
00:03:45,730 --> 00:03:47,340
In dit geval, de capaciteit is 10.

73
00:03:47,340 --> 00:03:49,580
En deze array is
gaat integers te houden.

74
00:03:49,580 --> 00:03:55,240
In het groen is de voorkant van onze wachtrij, de
volgende element te verwijderen, en rode

75
00:03:55,240 --> 00:03:58,610
de grootte van de wachtrij,
hoeveel elementen zijn

76
00:03:58,610 --> 00:04:01,190
bestaande uit de wachtrij.

77
00:04:01,190 --> 00:04:05,300
Dus als we zeggen q.front gelijken
0 en q.size grootte gelijk 0--

78
00:04:05,300 --> 00:04:07,120
We zetten 0s in die gebieden.

79
00:04:07,120 --> 00:04:11,070
En op dit punt, we zijn vrij veel
klaar om te beginnen werken met onze wachtrij.

80
00:04:11,070 --> 00:04:14,140
>> Dus de eerste operatie kunnen we
uit te voeren is om iets enqueue,

81
00:04:14,140 --> 00:04:16,860
een nieuw element aan
het einde van de wachtrij.

82
00:04:16,860 --> 00:04:19,089
Nou wat hebben we nodig om te
doen in het algemene geval?

83
00:04:19,089 --> 00:04:23,690
Nou deze functie enqueue behoeften
een pointer naar onze wachtrij accepteren.

84
00:04:23,690 --> 00:04:26,370
Nogmaals, als we had verklaard
onze wachtrij wereldwijd,

85
00:04:26,370 --> 00:04:29,490
zouden we niet nodig om dit te doen
se, maar in het algemeen, we

86
00:04:29,490 --> 00:04:32,330
moeten pointers accepteren
datastructuren

87
00:04:32,330 --> 00:04:35,040
als dit, want anders,
we langs value-- we

88
00:04:35,040 --> 00:04:38,140
passeren in kopieën van de wachtrij,
en zo zijn we eigenlijk niet veranderen

89
00:04:38,140 --> 00:04:41,050
de rij die we willen veranderen.

90
00:04:41,050 --> 00:04:44,860
>> De andere wat het moet doen is accepteren
een data-element van hetzelfde type.

91
00:04:44,860 --> 00:04:46,818
Ook in dit geval is het
naar gehele getallen,

92
00:04:46,818 --> 00:04:49,330
maar je kon willekeurig
verklaren het type gegevens als waarde

93
00:04:49,330 --> 00:04:51,160
en deze meer in het algemeen.

94
00:04:51,160 --> 00:04:56,030
Dat is het element dat we willen enqueue,
we willen toevoegen aan het einde van de wachtrij.

95
00:04:56,030 --> 00:04:58,573
Dan eigenlijk willen we
plaatst die gegevens in de wachtrij.

96
00:04:58,573 --> 00:05:01,490
In dit geval, te plaatsen in de
juiste locatie van ons aanbod,

97
00:05:01,490 --> 00:05:05,040
en dan willen we de grootte te veranderen
van de wachtrij, hoeveel elementen we

98
00:05:05,040 --> 00:05:07,050
momenteel.

99
00:05:07,050 --> 00:05:07,990
>> Dus laten we aan de slag.

100
00:05:07,990 --> 00:05:10,890
Hier is, nogmaals, dat de algemene
vorm functie verklaring

101
00:05:10,890 --> 00:05:13,980
voor wat enqueue eruit zou kunnen zien.

102
00:05:13,980 --> 00:05:14,910
En hier gaan we.

103
00:05:14,910 --> 00:05:18,335
Laten enqueue het aantal
28 in de wachtrij.

104
00:05:18,335 --> 00:05:19,460
Dus wat gaan we doen?

105
00:05:19,460 --> 00:05:23,390
Nou, de voorkant van onze wachtrij
op 0, en de grootte van onze wachtrij

106
00:05:23,390 --> 00:05:29,680
is op 0, en dus willen we waarschijnlijk te zetten
de nummer 28 in de array-element nummer

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

108
00:05:31,124 --> 00:05:32,540
Dus we hebben nu geplaatst dat daar.

109
00:05:32,540 --> 00:05:34,820
Dus nu wat hebben we nodig om te veranderen?

110
00:05:34,820 --> 00:05:37,090
We willen niet veranderen
de voorkant van de wachtrij,

111
00:05:37,090 --> 00:05:40,850
omdat we willen weten wat element
we zouden moeten later dequeue.

112
00:05:40,850 --> 00:05:44,020
Dus de reden dat we er vooraan
is een soort van een indicator van wat er

113
00:05:44,020 --> 00:05:46,439
de oudste ding in de array.

114
00:05:46,439 --> 00:05:49,730
Nou, de oudste zaak van de array-- in
Sterker nog, het enige wat in de array juiste

115
00:05:49,730 --> 00:05:53,540
now-- is 28, wat
in serie locatie 0.

116
00:05:53,540 --> 00:05:56,160
Dus we willen niet
veranderen groen nummer,

117
00:05:56,160 --> 00:05:57,910
want dat is de oudste element.

118
00:05:57,910 --> 00:06:00,510
Integendeel, we willen de grootte te veranderen.

119
00:06:00,510 --> 00:06:04,110
Dus in dit geval, zullen we
increment grootte 1.

120
00:06:04,110 --> 00:06:08,430
>> Nu een algemene soort idee van waar de
volgende element gaat om te gaan in een wachtrij

121
00:06:08,430 --> 00:06:12,310
is om deze twee nummers toe te voegen
samen voorzijde en grootte,

122
00:06:12,310 --> 00:06:16,390
en dat zal u vertellen waar de volgende
element in de wachtrij zal gaan.

123
00:06:16,390 --> 00:06:18,130
Dus laten we nu enqueue ander nummer.

124
00:06:18,130 --> 00:06:20,250
Laten enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Dus 33 is in te gaan op om te gaan
scala locatie 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Dus in dit geval, het gaat
in de serie locatie 1 te gaan,

127
00:06:26,840 --> 00:06:29,500
en nu de omvang van onze wachtrij is 2.

128
00:06:29,500 --> 00:06:31,840
>> Nogmaals, we zijn niet veranderen
de voorzijde van onze wachtrij,

129
00:06:31,840 --> 00:06:34,730
omdat 28 blijft de
oudste element, en we

130
00:06:34,730 --> 00:06:38,220
willen to-- toen we uiteindelijk krijgen
dequeuing te verwijderen elementen

131
00:06:38,220 --> 00:06:43,300
uit deze wachtrij, willen we weten
waarbij het oudste element.

132
00:06:43,300 --> 00:06:48,620
En dus moeten we altijd behouden
enkele indicator van de plaats waar dat is.

133
00:06:48,620 --> 00:06:50,410
Dus dat is wat de 0 is er voor.

134
00:06:50,410 --> 00:06:52,910
Dat is wat de voorkant is er voor.

135
00:06:52,910 --> 00:06:55,022
>> Laten we in enqueue één element, 19.

136
00:06:55,022 --> 00:06:56,980
Ik weet zeker dat je kan raden
waar de 19 zal gaan.

137
00:06:56,980 --> 00:06:59,860
Het gaat in te gaan
scala locatie nummer 2.

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

139
00:07:01,570 --> 00:07:03,199
En nu de omvang van onze wachtrij is 3.

140
00:07:03,199 --> 00:07:04,240
We hebben 3 elementen daarin.

141
00:07:04,240 --> 00:07:08,490
Dus als we, en we gaan niet
om nu, enqueue een ander element,

142
00:07:08,490 --> 00:07:11,370
het zou in serie locatie gaan
nummer 3, en de grootte van onze wachtrij

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

144
00:07:13,160 --> 00:07:15,279
Daarom hebben we een aantal elementen enqueued nu.

145
00:07:15,279 --> 00:07:16,570
Laten we nu eens beginnen om ze te verwijderen.

146
00:07:16,570 --> 00:07:19,450
Laten dequeue ze uit de wachtrij.

147
00:07:19,450 --> 00:07:23,340
>> Dus vergelijkbaar met pop, dat is een soort
van de analoog daarvan voor stapels,

148
00:07:23,340 --> 00:07:26,180
dequeue moet een accepteren
wijzer naar het queue-- weer,

149
00:07:26,180 --> 00:07:28,140
tenzij het wereldwijd is verklaard.

150
00:07:28,140 --> 00:07:31,610
Nu willen we de locatie te veranderen
van de voorkant van de wachtrij.

151
00:07:31,610 --> 00:07:35,050
Dit is waar het vandaan komt soort
in het spel, dat voor de variabele,

152
00:07:35,050 --> 00:07:37,310
want zodra we verwijderen
een element, we willen

153
00:07:37,310 --> 00:07:40,720
om het te verplaatsen naar de volgende oudste element.

154
00:07:40,720 --> 00:07:44,180
>> Dan willen we verlagen
de grootte van de wachtrij,

155
00:07:44,180 --> 00:07:47,130
en dan willen we de waarde terug
die is verwijderd uit de wachtrij.

156
00:07:47,130 --> 00:07:48,921
Nogmaals, willen we niet gewoon gooi hem weg.

157
00:07:48,921 --> 00:07:51,170
We vermoedelijk zijn extraheren
het uit de queue-- we

158
00:07:51,170 --> 00:07:54,170
dequeuing het omdat we de zorg over het.

159
00:07:54,170 --> 00:08:01,080
Dus we willen deze functie terug te keren
een data-element van het type waarde.

160
00:08:01,080 --> 00:08:04,360
Ook in dit geval waarde integer.

161
00:08:04,360 --> 00:08:05,670
>> Dus laten we nu dequeue iets.

162
00:08:05,670 --> 00:08:09,310
Laten we het verwijderen van een element uit de wachtrij.

163
00:08:09,310 --> 00:08:15,970
Als we zeggen int x evenaart & q, ampersand q--
nogmaals, dat is een verwijzing naar deze q gegevens

164
00:08:15,970 --> 00:08:20,177
structure-- wat element
zal worden dequeued?

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

166
00:08:23,840 --> 00:08:29,480
In dit geval, omdat het een eerste
in, first out datastructuur, FIFO,

167
00:08:29,480 --> 00:08:33,690
het eerste wat we in dit gezet
wachtrij was 28, en dus in dit geval,

168
00:08:33,690 --> 00:08:37,245
we gaan nemen 28 van de
de wachtrij, niet 19, wat

169
00:08:37,245 --> 00:08:38,870
we zouden hebben gedaan als dit was een stapel.

170
00:08:38,870 --> 00:08:42,220
We gaan nemen 28 uit de wachtrij.

171
00:08:42,220 --> 00:08:44,960
>> Vergelijkbaar met wat we hebben gedaan met
een stapel, we zijn niet echt

172
00:08:44,960 --> 00:08:47,345
gaan verwijderen 28
uit de wachtrij zelf,

173
00:08:47,345 --> 00:08:49,470
we gaan gewoon om vriendelijk
van te doen alsof het er niet is.

174
00:08:49,470 --> 00:08:51,678
Dus het gaat om daar te blijven
in het geheugen, maar we zijn gewoon

175
00:08:51,678 --> 00:08:57,820
gaat soort negeren door het bewegen
de andere twee gebieden van onze q data

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

177
00:08:58,830 --> 00:09:00,230
We gaan naar het front te veranderen.

178
00:09:00,230 --> 00:09:04,290
Q.front gaat nu
1 zijn, omdat nu

179
00:09:04,290 --> 00:09:07,740
de oudste element hebben wij in onze
wachtrij, omdat we al hebt verwijderd 28,

180
00:09:07,740 --> 00:09:10,460
dat was de voormalige oudste element.

181
00:09:10,460 --> 00:09:13,540
>> En nu willen we veranderen
de grootte van de wachtrij

182
00:09:13,540 --> 00:09:15,780
twee elementen in plaats van drie.

183
00:09:15,780 --> 00:09:20,450
Nu herinner ik eerder gezegd toen we
wilt elementen toe te voegen aan de wachtrij,

184
00:09:20,450 --> 00:09:26,000
we zetten in een array locatie
waarbij de som van de voorste en grootte.

185
00:09:26,000 --> 00:09:29,050
Dus in dit geval, zijn we nog steeds zetten
het, het volgende element in de wachtrij,

186
00:09:29,050 --> 00:09:33,360
in serie locatie 3, en
we zullen zien dat in een tweede.

187
00:09:33,360 --> 00:09:35,730
>> Dus we hebben nu onze dequeued
eerste element uit de wachtrij.

188
00:09:35,730 --> 00:09:36,480
Laten we het nog eens doen.

189
00:09:36,480 --> 00:09:38,696
Laten we een ander te verwijderen
element uit de wachtrij.

190
00:09:38,696 --> 00:09:42,400
In het geval van de huidige oudste
element serie locatie 1.

191
00:09:42,400 --> 00:09:44,220
Dat is wat q.front ons vertelt.

192
00:09:44,220 --> 00:09:46,980
Dat groene doos vertelt ons dat
dat is de oudste element.

193
00:09:46,980 --> 00:09:49,310
En zo is, zal x 33 geworden.

194
00:09:49,310 --> 00:09:52,130
We zullen gewoon een soort van vergeten
die 33 bestaat in de array,

195
00:09:52,130 --> 00:09:55,100
en we zullen nu zeggen dat de
nieuwe oudste element in de wachtrij

196
00:09:55,100 --> 00:09:58,900
is op scala locatie 2, en de grootte
van de rij, het aantal elementen

197
00:09:58,900 --> 00:10:02,152
we hebben in de wachtrij, is 1.

198
00:10:02,152 --> 00:10:05,110
Laten we nu enqueue iets, en ik
soort gaf deze weg een tweede geleden,

199
00:10:05,110 --> 00:10:10,340
maar als we willen in de om te zetten 40
wachtrij, waar is 40 gaat om te gaan?

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

201
00:10:12,880 --> 00:10:17,730
Nou we zijn zetten het
in q.front plus wachtrijgrootte,

202
00:10:17,730 --> 00:10:20,850
en dus is het zinvol om
eigenlijk om hier te zetten 40.

203
00:10:20,850 --> 00:10:22,840
Nu merken dat bij
een bepaald punt, we gaan

204
00:10:22,840 --> 00:10:27,980
aan het einde aan te krijgen
ons aanbod binnenkant van q,

205
00:10:27,980 --> 00:10:32,010
maar dat vervaagde 28 en 33--
ze zijn eigenlijk, technisch

206
00:10:32,010 --> 00:10:33,300
open ruimtes, toch?

207
00:10:33,300 --> 00:10:36,040
En zo kunnen we eventually--
die regel toe te voegen

208
00:10:36,040 --> 00:10:40,390
die twee together-- we kunnen uiteindelijk
mod moet door de grootte van de capaciteit

209
00:10:40,390 --> 00:10:41,410
dus we kunnen wikkelen.

210
00:10:41,410 --> 00:10:43,620
>> Dus als we naar element
nummer 10, als we

211
00:10:43,620 --> 00:10:48,790
vervangen in element nummer 10, zouden we
eigenlijk zet het in serie locatie 0.

212
00:10:48,790 --> 00:10:50,997
En als we zouden gaan
scala locatie-- me niet kwalijk,

213
00:10:50,997 --> 00:10:53,080
als we toegevoegd ze samen,
en we kregen te nummer

214
00:10:53,080 --> 00:10:56,330
11 zou zijn waar we zouden moeten zetten
het, die niet bestaat in deze array--

215
00:10:56,330 --> 00:10:58,200
het zou gaan out of bounds.

216
00:10:58,200 --> 00:11:03,367
We konden mod 10 en zet
in serie locatie 1.

217
00:11:03,367 --> 00:11:04,450
Dus dat is hoe wachtrijen werken.

218
00:11:04,450 --> 00:11:08,540
Ze altijd gaan om te gaan van links
naar rechts en eventueel wikkelen.

219
00:11:08,540 --> 00:11:11,280
En je weet dat ze
full als de grootte, dat rode doos,

220
00:11:11,280 --> 00:11:13,710
gelijk aan de capaciteit.

221
00:11:13,710 --> 00:11:16,720
En dus nadat we 40 heeft toegevoegd aan de
wachtrij, tja, wat moeten we doen?

222
00:11:16,720 --> 00:11:19,890
Nou, de oudste element
in de wachtrij nog 19,

223
00:11:19,890 --> 00:11:21,990
zodat we niet willen veranderen
de voorkant van de wachtrij,

224
00:11:21,990 --> 00:11:23,820
maar nu hebben we twee
elementen in de wachtrij,

225
00:11:23,820 --> 00:11:28,710
en dus willen we verhogen
onze grootte 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Dat is vrij veel met
werken met array-gebaseerde wachtrijen,

227
00:11:31,820 --> 00:11:33,630
en dergelijke te stapelen,
Er is ook een manier

228
00:11:33,630 --> 00:11:36,450
de implementatie van een wachtrij als een gekoppelde lijst.

229
00:11:36,450 --> 00:11:40,150
Nu, als dit soort data structuur
lijkt u bekend voor, het is.

230
00:11:40,150 --> 00:11:43,780
Het is niet een enkelvoudig gelinkte lijst,
het is een dubbel gelinkte lijst.

231
00:11:43,780 --> 00:11:46,790
En nu, als een terzijde, het is
echt mogelijk uit te voeren

232
00:11:46,790 --> 00:11:50,160
een wachtrij als een enkelvoudig gelinkte lijst, maar
Ik denk in termen van visualisatie,

233
00:11:50,160 --> 00:11:53,350
het eigenlijk zou kunnen helpen om te bekijken
dit als een dubbel gelinkte lijst.

234
00:11:53,350 --> 00:11:56,850
Maar het is zeker mogelijk om
doe dit als een afzonderlijk gekoppelde lijst.

235
00:11:56,850 --> 00:12:00,110
>> Dus laten we eens een kijkje op
wat dit eruit zou kunnen zien.

236
00:12:00,110 --> 00:12:02,750
Als we willen enquue--
dus nu weer zijn we

237
00:12:02,750 --> 00:12:05,360
overschakelen naar een gekoppelde-lijst
gebaseerde hier model.

238
00:12:05,360 --> 00:12:08,420
Als we willen enqueue, we willen
een nieuw element toe te voegen, goed

239
00:12:08,420 --> 00:12:09,730
Wat moeten we doen?

240
00:12:09,730 --> 00:12:12,770
Nou, allereerst, omdat
we toe te voegen aan het einde

241
00:12:12,770 --> 00:12:15,520
en het verwijderen van de
begin, we waarschijnlijk

242
00:12:15,520 --> 00:12:20,050
willen verwijzingen naar zowel het behouden
kop en de staart van de gelinkte lijst?

243
00:12:20,050 --> 00:12:22,660
Staart die een andere term voor
het einde van de gekoppelde lijst,

244
00:12:22,660 --> 00:12:24,496
het laatste element in de gekoppelde lijst.

245
00:12:24,496 --> 00:12:26,620
En deze zullen waarschijnlijk,
weer gunstig zijn voor ons

246
00:12:26,620 --> 00:12:28,477
als ze globale variabelen.

247
00:12:28,477 --> 00:12:31,060
Maar nu willen we een nieuwe toe te voegen
element wat we moeten doen?

248
00:12:31,060 --> 00:12:35,262
Wat we net [? malak?] of dynamisch
toewijzen onze nieuwe knooppunt voor onszelf.

249
00:12:35,262 --> 00:12:38,220
En dan, net als toen we elke voegen
element een dubbel gelinkte lijst wij,

250
00:12:38,220 --> 00:12:40,410
gewoon van-- sorteren
die laatste drie stappen hier

251
00:12:40,410 --> 00:12:43,330
zijn gewoon allemaal over het verplaatsen van de
pointers op de juiste wijze

252
00:12:43,330 --> 00:12:46,710
zodat het element wordt toegevoegd aan
de ketting zonder de ketting

253
00:12:46,710 --> 00:12:49,580
of het maken van een soort van fout
of het hebben van een soort van ongeval

254
00:12:49,580 --> 00:12:54,505
gebeuren waarbij we per ongeluk
verweesde sommige elementen van onze wachtrij.

255
00:12:54,505 --> 00:12:55,880
Hier is wat dit eruit zou kunnen zien.

256
00:12:55,880 --> 00:13:00,980
We willen het element toe te voegen
10 aan het einde van de wachtrij.

257
00:13:00,980 --> 00:13:03,380
Dus de oudste element hier
wordt vertegenwoordigd door het hoofd.

258
00:13:03,380 --> 00:13:06,800
Dat is het eerste wat we zetten
in deze hypothetische wachtrij hier.

259
00:13:06,800 --> 00:13:10,430
En staart 13, het meest
recent toegevoegde element.

260
00:13:10,430 --> 00:13:17,030
En dus als we willen enqueue 10 in
deze wachtrij, willen we het te zetten na 13.

261
00:13:17,030 --> 00:13:19,860
En dus gaan we naar dynamisch
toewijzen ruimte voor een nieuw knooppunt

262
00:13:19,860 --> 00:13:23,280
en controleer op nul om ervoor te zorgen
we hebben geen geheugen mislukking.

263
00:13:23,280 --> 00:13:27,040
Dan gaan we
Plaats 10 in dat knooppunt,

264
00:13:27,040 --> 00:13:30,030
en nu moeten we voorzichtig zijn
over hoe organiseren we pointers

265
00:13:30,030 --> 00:13:32,180
zodat we niet breken de keten.

266
00:13:32,180 --> 00:13:38,910
>> Wij kunnen 10 van de vorige veld instellen
om terug te verwijzen naar de oude staart,

267
00:13:38,910 --> 00:13:41,620
en aangezien '10 zullen de
nieuwe staart op een bepaald punt

268
00:13:41,620 --> 00:13:44,459
tegen de tijd al deze
kettingen zijn verbonden,

269
00:13:44,459 --> 00:13:46,250
niets gaat komen
na 10 nu.

270
00:13:46,250 --> 00:13:49,880
En zo 10 de volgende pointer
zal wijzen op null,

271
00:13:49,880 --> 00:13:53,580
en dan nadat we dit doen, nadat we hebben
verbonden 10 naar achteren om de keten,

272
00:13:53,580 --> 00:13:57,780
kunnen we de oude hoofd, of, excuus nemen
me, de oude staart van de wachtrij.

273
00:13:57,780 --> 00:14:02,980
Het oude einde van de wachtrij,
13, en maken het wijzen naar 10.

274
00:14:02,980 --> 00:14:08,220
Nu, op dit punt, we
enqueued het nummer 10 in deze wachtrij.

275
00:14:08,220 --> 00:14:14,740
Alles wat we nu moeten doen is gewoon bewegen de
staart te wijzen op 10 in plaats van 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing is eigenlijk
zeer vergelijkbaar met popping

277
00:14:17,630 --> 00:14:21,710
een stapel die is
geïmplementeerd als een gekoppelde lijst

278
00:14:21,710 --> 00:14:24,040
als je de stapels video gezien heb.

279
00:14:24,040 --> 00:14:27,280
Alles wat we moeten doen is beginnen bij de
begin, vindt het tweede element,

280
00:14:27,280 --> 00:14:30,480
bevrijden het eerste element,
en verplaats de kop

281
00:14:30,480 --> 00:14:32,930
te wijzen aan het tweede element.

282
00:14:32,930 --> 00:14:37,920
Waarschijnlijk beter om het te visualiseren
alleen maar om extra duidelijk over zijn.

283
00:14:37,920 --> 00:14:39,230
Dus hier is onze wachtrij weer.

284
00:14:39,230 --> 00:14:42,600
12 is het oudste element
in onze wachtrij, het hoofd.

285
00:14:42,600 --> 00:14:46,210
10 is het nieuwste element
in onze rij, onze staart.

286
00:14:46,210 --> 00:14:49,310
>> En dus als we willen
een element dequeue,

287
00:14:49,310 --> 00:14:52,202
we willen de oudste element te verwijderen.

288
00:14:52,202 --> 00:14:52,910
Dus wat doen we?

289
00:14:52,910 --> 00:14:55,243
Wel stellen we een traversal pointer
dat begint bij de kop,

290
00:14:55,243 --> 00:14:57,840
en gaan we het zo dat het
verwijst naar het tweede element

291
00:14:57,840 --> 00:15:02,290
van deze queue-- iets door te zeggen trav
gelijk trav pijl naast bijvoorbeeld

292
00:15:02,290 --> 00:15:07,170
zou trav daarheen te verhuizen om te wijzen op
15, die, na dequeue 12,

293
00:15:07,170 --> 00:15:13,030
of na het verwijderen we 12, zal
uitgegroeid tot de toenmalige oudste element.

294
00:15:13,030 --> 00:15:16,360
>> Nu hebben we een greep op de eerste
element via de pointer kop

295
00:15:16,360 --> 00:15:19,440
en het tweede element
via de pointer Trav.

296
00:15:19,440 --> 00:15:25,170
We kunnen nu gratis hoofd, en dan kunnen we
zeggen niets komt voor 15 meer.

297
00:15:25,170 --> 00:15:29,990
Dus we kunnen 15 eerdere veranderen
pointer om te wijzen op null,

298
00:15:29,990 --> 00:15:31,874
en we bewegen het hoofd over.

299
00:15:31,874 --> 00:15:32,540
En daar gaan we.

300
00:15:32,540 --> 00:15:35,840
Nu met succes hebben we
dequeued 12, en nu zijn we

301
00:15:35,840 --> 00:15:39,180
nog een rij van 4 elementen.

302
00:15:39,180 --> 00:15:41,700
Dat is vrijwel alle
er wachtrijen,

303
00:15:41,700 --> 00:15:45,810
zowel-array gebaseerde en gekoppeld-lijst op basis.

304
00:15:45,810 --> 00:15:46,860
Ik ben Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Dit is CS 50.

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