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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: So as jy het
kyk na die video op stapel,

3
00:00:07,370 --> 00:00:09,870
hierdie is waarskynlik gaan om te voel
soos 'n bietjie van deja vu.

4
00:00:09,870 --> 00:00:13,850
Dit gaan 'n baie soortgelyke konsep,
net met 'n effense draai op dit.

5
00:00:13,850 --> 00:00:15,530
Ons gaan nou praat oor toue.

6
00:00:15,530 --> 00:00:19,350
So 'n tou, soortgelyk aan 'n stapel,
is 'n ander soort van data struktuur

7
00:00:19,350 --> 00:00:22,412
wat ons kan gebruik om te handhaaf
data in 'n georganiseerde manier.

8
00:00:22,412 --> 00:00:24,120
Soortgelyk aan 'n stapel,
dit geïmplementeer kan word

9
00:00:24,120 --> 00:00:27,000
as 'n skikking of 'n geskakelde lys.

10
00:00:27,000 --> 00:00:30,320
Anders as 'n stapel, die reëls
wat ons gebruik om te bepaal

11
00:00:30,320 --> 00:00:34,210
wanneer dinge kry bygevoeg en verwyder van
'n tou is 'n bietjie anders.

12
00:00:34,210 --> 00:00:36,590
>> Anders as 'n stapel, wat
is 'n LIFO struktuur,

13
00:00:36,590 --> 00:00:45,610
laaste in, eerste uit, 'n tou is 'n EIEU
struktuur, EIEU, eerste in, eerste uit.

14
00:00:45,610 --> 00:00:49,320
Nou toue, het jy waarskynlik
'n analogie toue.

15
00:00:49,320 --> 00:00:52,820
As jy al ooit in lyn gewees het op
'n pretpark of by 'n bank,

16
00:00:52,820 --> 00:00:56,430
daar is soort van 'n regverdigheid
implementering struktuur.

17
00:00:56,430 --> 00:00:59,160
Die eerste persoon in die lyn by
die bank is die eerste persoon

18
00:00:59,160 --> 00:01:00,760
wat kry om die teller te praat.

19
00:01:00,760 --> 00:01:03,522
>> Dit sou soort van 'n ras
aan die onderkant as die enigste manier

20
00:01:03,522 --> 00:01:06,730
jy het die teller by die praat
bank was om die laaste persoon in lyn wees.

21
00:01:06,730 --> 00:01:09,146
Almal sal wil altyd
om die laaste persoon in lyn,

22
00:01:09,146 --> 00:01:12,580
en die persoon wat eerste daar was
wat wag vir 'n rukkie,

23
00:01:12,580 --> 00:01:14,715
kon daar wees vir ure,
en ure en ure

24
00:01:14,715 --> 00:01:17,590
voordat hulle 'n kans om werklik
enige geld by die bank onttrek.

25
00:01:17,590 --> 00:01:22,510
En so toue is soort van die
regverdigheid implementering struktuur.

26
00:01:22,510 --> 00:01:25,780
Maar dit beteken nie noodwendig
dat stapels is 'n slegte ding nie, net

27
00:01:25,780 --> 00:01:28,160
dat toue is 'n ander manier om dit te doen.

28
00:01:28,160 --> 00:01:32,420
So weer 'n tou is eerste in, eerste
uit teenoor 'n stapel wat laaste in,

29
00:01:32,420 --> 00:01:34,440
eerste uit.

30
00:01:34,440 --> 00:01:36,190
Soortgelyk aan 'n stapel,
ons het twee operasies

31
00:01:36,190 --> 00:01:38,470
dat ons kan uitvoer op toue.

32
00:01:38,470 --> 00:01:43,910
Die name is enqueue, wat is om by te voeg
'n nuwe element tot die einde van die tou,

33
00:01:43,910 --> 00:01:47,330
en dequeue, wat
die oudste verwyder

34
00:01:47,330 --> 00:01:49,670
element van die voorkant van die tou.

35
00:01:49,670 --> 00:01:53,600
So ons gaan elemente voeg
op die einde van die tou,

36
00:01:53,600 --> 00:01:57,220
en ons gaan elemente verwyder
van die voorkant van die tou.

37
00:01:57,220 --> 00:02:00,790
Weereens, met die stapel, is ons die toevoeging
elemente by die top van die stapel

38
00:02:00,790 --> 00:02:03,380
en die verwydering van elemente
Van die top van die stapel.

39
00:02:03,380 --> 00:02:07,570
So met enqueue, is dit toe te voeg tot
die einde, die verwydering van die voorkant.

40
00:02:07,570 --> 00:02:10,639
So die oudste ding daar
is altyd die volgende ding

41
00:02:10,639 --> 00:02:13,620
om uit te kom as ons probeer
en dequeue iets.

42
00:02:13,620 --> 00:02:18,330
>> So weer, met toue, kan ons
skikking gebaseer implementering

43
00:02:18,330 --> 00:02:20,110
en gekoppel-lys gebasseer implementasies.

44
00:02:20,110 --> 00:02:24,620
Ons sal weer begin met
skikking gebaseer implementasies.

45
00:02:24,620 --> 00:02:27,070
Die struktuur definisie
lyk redelik soortgelyk.

46
00:02:27,070 --> 00:02:30,720
Ons het 'n skikking
daar van data tipe waarde

47
00:02:30,720 --> 00:02:32,690
sodat dit kan arbitrêre tipes data te hou.

48
00:02:32,690 --> 00:02:35,570
Ons weer gaan gebruik
heelgetalle in hierdie voorbeeld.

49
00:02:35,570 --> 00:02:39,830
>> En net soos met ons
skikking gebaseer stapel implementering,

50
00:02:39,830 --> 00:02:42,340
want ons is met behulp van 'n
skikking, ons noodwendig

51
00:02:42,340 --> 00:02:46,850
daardie beperking wat C soort
van afdwing op ons, wat is ons

52
00:02:46,850 --> 00:02:51,670
moenie enige dinamika in nie ons
vermoë om te groei en krimp die skikking.

53
00:02:51,670 --> 00:02:55,710
Ons moet besluit aan die begin
Wat is die maksimum aantal van die dinge

54
00:02:55,710 --> 00:02:59,300
dat ons in hierdie kan sit
tou, en in hierdie geval,

55
00:02:59,300 --> 00:03:02,070
kapasiteit sou 'n paar pond te wees
gedefinieer konstante in ons kode.

56
00:03:02,070 --> 00:03:05,430
En vir die doeleindes van hierdie
video, is kapasiteit gaan wees 10.

57
00:03:05,430 --> 00:03:07,690
>> Ons moet tred te hou van
die voorkant van die tou

58
00:03:07,690 --> 00:03:11,160
sodat ons weet watter element
ons wil dequeue,

59
00:03:11,160 --> 00:03:15,070
en ons moet ook tred te hou van
iets else-- die aantal elemente

60
00:03:15,070 --> 00:03:16,690
dat ons in ons ry.

61
00:03:16,690 --> 00:03:19,360
Let ons nie die dop
van die einde van die tou, net

62
00:03:19,360 --> 00:03:21,150
die grootte van die tou.

63
00:03:21,150 --> 00:03:24,310
En die rede vir wat sal hopelik
'n bietjie duideliker in 'n oomblik.

64
00:03:24,310 --> 00:03:26,143
Sodra ons voltooi het
hierdie tipe definisie

65
00:03:26,143 --> 00:03:29,080
ons het 'n nuwe soort data
genoem tou, wat ons kan nou

66
00:03:29,080 --> 00:03:30,630
verklaar veranderlikes van daardie tipe data.

67
00:03:30,630 --> 00:03:35,350
En ietwat verwarrend, het ek besluit
om te noem dit tou q, die letter

68
00:03:35,350 --> 00:03:38,090
q in plaas van die tipe data q.

69
00:03:38,090 --> 00:03:39,600
>> So hier is ons ry.

70
00:03:39,600 --> 00:03:40,700
Dit is 'n struktuur.

71
00:03:40,700 --> 00:03:45,730
Dit bevat drie lede of drie
velde, 'n verskeidenheid van grootte kapasiteit.

72
00:03:45,730 --> 00:03:47,340
In hierdie geval, kapasiteit is 10.

73
00:03:47,340 --> 00:03:49,580
En dit skikking is
gaan heelgetalle te hou.

74
00:03:49,580 --> 00:03:55,240
In groen is die voorkant van ons ry, die
volgende element te verwyder, en in die rooi

75
00:03:55,240 --> 00:03:58,610
sal die grootte van die tou wees,
hoeveel elemente is tans

76
00:03:58,610 --> 00:04:01,190
bestaande in die tou.

77
00:04:01,190 --> 00:04:05,300
So as ons sê q.front gelykes
0 en q.size grootte gelyk 0--

78
00:04:05,300 --> 00:04:07,120
ons is om 0s in die velde.

79
00:04:07,120 --> 00:04:11,070
En op hierdie punt, ons is pretty much
gereed om te begin werk met ons ry.

80
00:04:11,070 --> 00:04:14,140
>> So het die eerste operasie wat ons kan
voer is om iets enqueue,

81
00:04:14,140 --> 00:04:16,860
om 'n nuwe element te voeg tot
die einde van die tou.

82
00:04:16,860 --> 00:04:19,089
Wel, wat moet ons
doen in die algemene geval?

83
00:04:19,089 --> 00:04:23,690
Wel hierdie funksie te enqueue behoeftes
om 'n wyser na ons tou te aanvaar.

84
00:04:23,690 --> 00:04:26,370
Weereens, as ons verklaar het
ons ry wêreldwyd,

85
00:04:26,370 --> 00:04:29,490
sou ons nie nodig het om dit te doen
noodwendig nie, maar in die algemeen, ons

86
00:04:29,490 --> 00:04:32,330
moet pointers te aanvaar
datastrukture

87
00:04:32,330 --> 00:04:35,040
soos hierdie, want anders,
ons verbygaan value-- ons

88
00:04:35,040 --> 00:04:38,140
verby in afskrifte van die tou,
en so is ons nie eintlik verander

89
00:04:38,140 --> 00:04:41,050
die tou wat ons van plan is om te verander.

90
00:04:41,050 --> 00:04:44,860
>> Die ander ding wat dit nodig het om te doen is aanvaar
'n data element van die toepaslike tipe.

91
00:04:44,860 --> 00:04:46,818
Weereens, in hierdie geval, dit is
gaan heelgetalle wees,

92
00:04:46,818 --> 00:04:49,330
Maar jy kon arbitrêr
verklaar dat die tipe data as waarde

93
00:04:49,330 --> 00:04:51,160
en gebruik dit meer algemeen.

94
00:04:51,160 --> 00:04:56,030
Dit is die element wat ons wil enqueue,
ons wil bydra tot die einde van die tou.

95
00:04:56,030 --> 00:04:58,573
Dan wil ons eintlik
plaas dat data in die tou.

96
00:04:58,573 --> 00:05:01,490
In hierdie geval, plaas dit in die
regte plek van ons verskeidenheid,

97
00:05:01,490 --> 00:05:05,040
en dan wil ons die grootte verander
van die tou, hoeveel elemente wat ons

98
00:05:05,040 --> 00:05:07,050
tans het.

99
00:05:07,050 --> 00:05:07,990
>> So laat ons begin.

100
00:05:07,990 --> 00:05:10,890
Hier is weer, dat die algemene
vorm funksie verklaring

101
00:05:10,890 --> 00:05:13,980
vir wat enqueue lyk.

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

103
00:05:14,910 --> 00:05:18,335
Kom ons enqueue die aantal
28 in die tou.

104
00:05:18,335 --> 00:05:19,460
So, wat gaan ons doen?

105
00:05:19,460 --> 00:05:23,390
Wel, die voorkant van ons ry is
by 0, en die grootte van ons ry

106
00:05:23,390 --> 00:05:29,680
is by 0, en so wil ons waarskynlik te sit
die aantal 28 opgestel element getal

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

108
00:05:31,124 --> 00:05:32,540
Dus het ons nou geplaas dat daar in.

109
00:05:32,540 --> 00:05:34,820
So nou wat moet ons verander?

110
00:05:34,820 --> 00:05:37,090
Ons wil nie om te verander
die voorkant van die tou,

111
00:05:37,090 --> 00:05:40,850
want ons wil weet wat element
ons dalk nodig om later dequeue.

112
00:05:40,850 --> 00:05:44,020
So die rede waarom ons het daar voor
is 'n soort van 'n aanwyser van wat

113
00:05:44,020 --> 00:05:46,439
die oudste ding in die skikking.

114
00:05:46,439 --> 00:05:49,730
Wel, die oudste ding in die array-- in
Trouens, die enigste ding wat in die skikking reg

115
00:05:49,730 --> 00:05:53,540
now-- is 28, wat
op verskeidenheid ligging 0.

116
00:05:53,540 --> 00:05:56,160
Sodat ons nie wil
verander dat die groen nommer,

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

118
00:05:57,910 --> 00:06:00,510
Inteendeel, ons wil hê dat die grootte te verander.

119
00:06:00,510 --> 00:06:04,110
So in hierdie geval, sal ons
inkrementeer grootte 1.

120
00:06:04,110 --> 00:06:08,430
>> Nou 'n algemene soort van idee van waar die
volgende element gaan om te gaan in 'n ry

121
00:06:08,430 --> 00:06:12,310
is om die twee getalle te voeg
saam, voor en grootte,

122
00:06:12,310 --> 00:06:16,390
en dat jy weet waar die volgende
element in die ry gaan om te gaan.

123
00:06:16,390 --> 00:06:18,130
So nou, laat ons enqueue ander getal.

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

125
00:06:20,250 --> 00:06:24,480
So 33 gaan in om te gaan
verskeidenheid ligging 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
So in hierdie geval, dit gaan
in verskeidenheid plek 1 om te gaan,

127
00:06:26,840 --> 00:06:29,500
en nou is die grootte van ons ry is 2.

128
00:06:29,500 --> 00:06:31,840
>> Weereens, is ons nie verander
die voorkant van ons ry,

129
00:06:31,840 --> 00:06:34,730
omdat 28 is nog steeds die
oudste element, en ons

130
00:06:34,730 --> 00:06:38,220
wil aan- wanneer ons uiteindelik
om dequeuing, die verwydering van elemente

131
00:06:38,220 --> 00:06:43,300
Van hierdie ry, wil ons weet
waar die oudste element is.

132
00:06:43,300 --> 00:06:48,620
En dus moet ons altyd in stand te hou
sommige aanduiding van waar dit is.

133
00:06:48,620 --> 00:06:50,410
So dit is wat die 0 is daar.

134
00:06:50,410 --> 00:06:52,910
Dit is wat voor is daar.

135
00:06:52,910 --> 00:06:55,022
>> Kom ons in enqueue een element, 19.

136
00:06:55,022 --> 00:06:56,980
Ek is seker jy kan raai
waar 19 gaan om te gaan.

137
00:06:56,980 --> 00:06:59,860
Dit gaan om in te gaan
verskeidenheid ligging nommer 2.

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

139
00:07:01,570 --> 00:07:03,199
En nou het die grootte van ons ry is 3.

140
00:07:03,199 --> 00:07:04,240
Ons het 3 elemente in dit.

141
00:07:04,240 --> 00:07:08,490
So as ons, en ons gaan nie
om nou, enqueue ander element,

142
00:07:08,490 --> 00:07:11,370
dit sou in verskeidenheid plek te gaan
nommer 3, en die grootte van ons ry

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

144
00:07:13,160 --> 00:07:15,279
So het ons 'n paar elemente waglys nou.

145
00:07:15,279 --> 00:07:16,570
Nou laat ons begin om hulle te verwyder.

146
00:07:16,570 --> 00:07:19,450
Kom ons dequeue hulle van die tou.

147
00:07:19,450 --> 00:07:23,340
>> So soortgelyk aan pop, wat is 'n soort
van die analoog van hierdie vir stapels,

148
00:07:23,340 --> 00:07:26,180
dequeue moet 'n aanvaar
wyser na die queue-- weer

149
00:07:26,180 --> 00:07:28,140
tensy dit wêreldwyd is verklaar.

150
00:07:28,140 --> 00:07:31,610
Nou wil ons die plek verander
van die voorkant van die tou.

151
00:07:31,610 --> 00:07:35,050
Dit is waar dit kom soort
in die spel, wat voor veranderlike,

152
00:07:35,050 --> 00:07:37,310
want as ons verwyder
'n element, ons wil

153
00:07:37,310 --> 00:07:40,720
om dit te skuif na die volgende oudste element.

154
00:07:40,720 --> 00:07:44,180
>> Dan wil ons daal
die grootte van die tou,

155
00:07:44,180 --> 00:07:47,130
en dan wil ons die waarde terug
dat is verwyder van die tou.

156
00:07:47,130 --> 00:07:48,921
Weereens, ons wil nie net weggooi nie.

157
00:07:48,921 --> 00:07:51,170
Ons vermoedelik onttrek
dit van die queue-- ons

158
00:07:51,170 --> 00:07:54,170
dequeuing dit omdat ons omgee nie.

159
00:07:54,170 --> 00:08:01,080
So wil ons hierdie funksie om terug te keer
'n data element van die tipe waarde.

160
00:08:01,080 --> 00:08:04,360
Weereens, in hierdie geval, waarde is heelgetal.

161
00:08:04,360 --> 00:08:05,670
>> So nou, laat ons dequeue iets.

162
00:08:05,670 --> 00:08:09,310
Kom ons verwyder 'n element van die tou.

163
00:08:09,310 --> 00:08:15,970
As ons sê int x is gelyk aan & q, ampersand q--
weer dit is 'n muis om hierdie q data

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

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

166
00:08:23,840 --> 00:08:29,480
In hierdie geval, want dit is 'n eerste
in, eerste uit data struktuur, EIEU,

167
00:08:29,480 --> 00:08:33,690
die eerste ding wat ons in hierdie sit
tou was 28, en so in hierdie geval,

168
00:08:33,690 --> 00:08:37,245
ons gaan neem 28 uit
die tou, nie 19, en dit is wat

169
00:08:37,245 --> 00:08:38,870
ons sou gedoen het as dit was 'n stapel.

170
00:08:38,870 --> 00:08:42,220
Ons gaan om te neem 28 uit die tou.

171
00:08:42,220 --> 00:08:44,960
>> Soortgelyk aan wat ons gedoen het met
'n stapel, ons is nie eintlik

172
00:08:44,960 --> 00:08:47,345
gaan verwyder 28
uit die tou self,

173
00:08:47,345 --> 00:08:49,470
ons net gaan om die soort
van voorgee dit is nie daar nie.

174
00:08:49,470 --> 00:08:51,678
So dit gaan om daar te bly
in die geheue, maar ons is net

175
00:08:51,678 --> 00:08:57,820
gaan soort van ignoreer deur die beweging
die ander twee velde van ons q data

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

177
00:08:58,830 --> 00:09:00,230
Ons gaan na die voorkant verander.

178
00:09:00,230 --> 00:09:04,290
Q.front gaan nou
1, want dit is nou

179
00:09:04,290 --> 00:09:07,740
die oudste element wat ons in ons
ry, want ons het alreeds verwyder 28,

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

181
00:09:10,460 --> 00:09:13,540
>> En nou, ons wil om te verander
die grootte van die tou

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

183
00:09:15,780 --> 00:09:20,450
Nou onthou vroeër het ek gesê wanneer ons
wil elemente by die tou,

184
00:09:20,450 --> 00:09:26,000
ons sit dit in 'n skikking plek
wat is die som van die voorkant en grootte.

185
00:09:26,000 --> 00:09:29,050
So in hierdie geval, ons nog steeds om
dit die volgende element in die ry,

186
00:09:29,050 --> 00:09:33,360
in verskeidenheid plek 3 en
ons sal sien dat in 'n sekonde.

187
00:09:33,360 --> 00:09:35,730
>> Dus het ons nou dequeued ons
eerste element van die tou.

188
00:09:35,730 --> 00:09:36,480
Kom ons doen dit weer.

189
00:09:36,480 --> 00:09:38,696
Kom ons 'n ander verwyder
element van die tou.

190
00:09:38,696 --> 00:09:42,400
In die geval, die huidige oudste
element is verskeidenheid plek 1.

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

192
00:09:44,220 --> 00:09:46,980
Dat die groen boks vertel ons dat
dit is die oudste element.

193
00:09:46,980 --> 00:09:49,310
En so sal x 33 geword.

194
00:09:49,310 --> 00:09:52,130
Ons sal net soort van vergeet
dat 33 bestaan ​​in die skikking,

195
00:09:52,130 --> 00:09:55,100
en ons sal nou, die sê dat
nuwe oudste element in die ry

196
00:09:55,100 --> 00:09:58,900
is op verskeidenheid ligging 2, en die grootte
van die tou, die aantal elemente

197
00:09:58,900 --> 00:10:02,152
ons het in die tou, is 1.

198
00:10:02,152 --> 00:10:05,110
Nou laat enqueue iets, en ek
soort het hierdie weg 'n tweede gelede

199
00:10:05,110 --> 00:10:10,340
maar as ons wil hê om in die te sit 40
tou, waar is 40 gaan om te gaan?

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

201
00:10:12,880 --> 00:10:17,730
Wel, ons het is om dit
in q.front plus tou grootte,

202
00:10:17,730 --> 00:10:20,850
en so is dit sinvol om
eintlik hier sit 40.

203
00:10:20,850 --> 00:10:22,840
Nou sien dat by
'n sekere punt, ons gaan

204
00:10:22,840 --> 00:10:27,980
tot aan die einde van die te kry
ons verskeidenheid binnekant van q,

205
00:10:27,980 --> 00:10:32,010
maar dat vervaag 28 en 33--
hulle is eintlik tegnies

206
00:10:32,010 --> 00:10:33,300
oop ruimtes, reg?

207
00:10:33,300 --> 00:10:36,040
En so kan ons eventually--
die reël van die toevoeging

208
00:10:36,040 --> 00:10:40,390
daardie twee saam op ons kan uiteindelik
moet mod deur die grootte van kapasiteit

209
00:10:40,390 --> 00:10:41,410
sodat ons kan draai om.

210
00:10:41,410 --> 00:10:43,620
>> So as ons by element
nommer 10, as ons

211
00:10:43,620 --> 00:10:48,790
vervang dit in element nommer 10, sou ons
eintlik sit dit in die rigting ligging 0.

212
00:10:48,790 --> 00:10:50,997
En as ons gaan
verskeidenheid location-- my verskoon,

213
00:10:50,997 --> 00:10:53,080
as ons bygevoeg hulle saam,
en ons het na die nommer

214
00:10:53,080 --> 00:10:56,330
11 sou wees waar ons sou hê om te sit
dit wat nie bestaan ​​nie in hierdie array--

215
00:10:56,330 --> 00:10:58,200
dit sou gaan buite perke.

216
00:10:58,200 --> 00:11:03,367
Ons kon mod deur 10 en sit
dit opgestel plek 1.

217
00:11:03,367 --> 00:11:04,450
So dit is hoe toue werk.

218
00:11:04,450 --> 00:11:08,540
Hulle is altyd gaan om te gaan van links
na regs en moontlik draai om.

219
00:11:08,540 --> 00:11:11,280
En jy weet dat hulle
volle as die grootte, wat rooi boks,

220
00:11:11,280 --> 00:11:13,710
word gelyk aan kapasiteit.

221
00:11:13,710 --> 00:11:16,720
En so nadat ons 40 het by die
ry, goed wat ons nodig het om te doen?

222
00:11:16,720 --> 00:11:19,890
Wel, die oudste element
in die tou is nog 19,

223
00:11:19,890 --> 00:11:21,990
sodat ons nie wil verander
die voorkant van die tou,

224
00:11:21,990 --> 00:11:23,820
maar nou het ons twee
elemente in die tou,

225
00:11:23,820 --> 00:11:28,710
en so het ons wil verhoog
ons grote 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Dit is pretty much dit met
werk met skikking gebaseer toue,

227
00:11:31,820 --> 00:11:33,630
en soortgelyk aan stapel,
Daar is ook 'n manier

228
00:11:33,630 --> 00:11:36,450
te implementeer 'n tou as 'n geskakelde lys.

229
00:11:36,450 --> 00:11:40,150
Nou as hierdie tipe datastruktuur
lyk bekend vir julle, dit is nie.

230
00:11:40,150 --> 00:11:43,780
Dit is nie 'n een-een gekoppel lys
dit is 'n dubbel geskakelde lys.

231
00:11:43,780 --> 00:11:46,790
En nou, as 'n eenkant, is dit
eintlik moontlik om te implementeer

232
00:11:46,790 --> 00:11:50,160
'n tou as 'n enkel gekoppel lys, maar
Ek dink in terme van visualisering,

233
00:11:50,160 --> 00:11:53,350
dit eintlik kan help om te sien
dit as 'n dubbel geskakelde lys.

234
00:11:53,350 --> 00:11:56,850
Maar dit is beslis moontlik om
doen dit as 'n enkel geskakelde lys.

235
00:11:56,850 --> 00:12:00,110
>> So laat ons 'n blik op
wat dit lyk.

236
00:12:00,110 --> 00:12:02,750
As ons wil enquue--
So nou weer ons

237
00:12:02,750 --> 00:12:05,360
oor te skakel na 'n gekoppelde-lys
gebaseer hier model.

238
00:12:05,360 --> 00:12:08,420
As ons wil enqueue, ons wil
om 'n nuwe element by te voeg, asook

239
00:12:08,420 --> 00:12:09,730
wat moet ons doen?

240
00:12:09,730 --> 00:12:12,770
Wel, die eerste van alles, omdat
Ons voeg tot die einde

241
00:12:12,770 --> 00:12:15,520
en die verwydering van die
begin, ons waarskynlik

242
00:12:15,520 --> 00:12:20,050
wil verwysings na beide die stand
kop en die stert van die geskakelde lys?

243
00:12:20,050 --> 00:12:22,660
Stert is 'n ander term vir
die einde van die geskakelde lys,

244
00:12:22,660 --> 00:12:24,496
die laaste element in die geskakelde lys.

245
00:12:24,496 --> 00:12:26,620
En dit sal waarskynlik
weer voordelig wees om ons te

246
00:12:26,620 --> 00:12:28,477
as hulle globale veranderlikes.

247
00:12:28,477 --> 00:12:31,060
Maar nou, as ons wil 'n nuwe voeg
element wat het ons te doen?

248
00:12:31,060 --> 00:12:35,262
Wat ons net [? malak?] of 'n dinamiese
toeken ons nuwe node vir onsself.

249
00:12:35,262 --> 00:12:38,220
En dan, net soos wanneer ons enige voeg
element om 'n dubbel geskakelde lys,

250
00:12:38,220 --> 00:12:40,410
net om of-- sorteer
daardie laaste drie stappe hier

251
00:12:40,410 --> 00:12:43,330
is net alles oor die verskuiwing van die
wysers op die regte manier

252
00:12:43,330 --> 00:12:46,710
sodat die element kry bygevoeg
die ketting sonder om te breek die ketting

253
00:12:46,710 --> 00:12:49,580
of maak 'n soort van fout
of om 'n soort van 'n ongeluk

254
00:12:49,580 --> 00:12:54,505
gebeur waardeur ons per ongeluk
Orphan sommige elemente van ons ry.

255
00:12:54,505 --> 00:12:55,880
Hier is wat dit kan lyk.

256
00:12:55,880 --> 00:13:00,980
Ons wil die element te voeg
10 aan die einde van hierdie tou.

257
00:13:00,980 --> 00:13:03,380
So die oudste element hier
word verteenwoordig deur kop.

258
00:13:03,380 --> 00:13:06,800
Dit is die eerste ding wat ons het
in hierdie hipotetiese tou hier.

259
00:13:06,800 --> 00:13:10,430
En stert, 13, is die mees
onlangs bygevoeg element.

260
00:13:10,430 --> 00:13:17,030
En so as ons wil enqueue 10 in
hierdie ry, wil ons om dit te sit na 13.

261
00:13:17,030 --> 00:13:19,860
En so gaan ons dinamiese
toeken ruimte vir 'n nuwe node

262
00:13:19,860 --> 00:13:23,280
en kyk vir null om seker te maak
Ons het nie 'n geheue mislukking.

263
00:13:23,280 --> 00:13:27,040
Dan gaan ons
plaas 10 in daardie knoop,

264
00:13:27,040 --> 00:13:30,030
en nou moet ons versigtig wees om
oor hoe ons te organiseer pointers

265
00:13:30,030 --> 00:13:32,180
sodat ons nie breek die ketting.

266
00:13:32,180 --> 00:13:38,910
>> Ons kan 10 se vorige veld stel
om terug te verwys na die ou stert,

267
00:13:38,910 --> 00:13:41,620
en aangesien '10 sal die
nuwe stert op 'n sekere punt

268
00:13:41,620 --> 00:13:44,459
Teen die tyd dat al hierdie
kettings verbind,

269
00:13:44,459 --> 00:13:46,250
niks gaan kom
na 10 nou.

270
00:13:46,250 --> 00:13:49,880
En so 10 se volgende wyser
sal verwys na nul

271
00:13:49,880 --> 00:13:53,580
en dan na ons dit doen, nadat ons het
verbind 10 agtertoe om die ketting,

272
00:13:53,580 --> 00:13:57,780
kan ons die ou hoof, of, verskoning te neem
my die ou stert van die tou.

273
00:13:57,780 --> 00:14:02,980
Die ou einde van die tou,
13, en maak dit wys tot 10.

274
00:14:02,980 --> 00:14:08,220
En nou, op hierdie punt, ons het
waglys die nommer 10 in die tou.

275
00:14:08,220 --> 00:14:14,740
Al wat ons nou moet doen, is net beweeg die
stert om te wys op 10 in plaas van 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing is eintlik
baie soortgelyk aan die knal

277
00:14:17,630 --> 00:14:21,710
uit 'n stapel wat
geïmplementeer as 'n geskakelde lys

278
00:14:21,710 --> 00:14:24,040
as jy die stapels video gesien het.

279
00:14:24,040 --> 00:14:27,280
Al wat ons moet doen is om te begin by die
begin, vind die tweede element,

280
00:14:27,280 --> 00:14:30,480
bevry die eerste element,
en dan skuif die hoof

281
00:14:30,480 --> 00:14:32,930
om te verwys na die tweede element.

282
00:14:32,930 --> 00:14:37,920
Waarskynlik beter om dit te visualiseer
net om ekstra duidelik daaroor wees.

283
00:14:37,920 --> 00:14:39,230
So hier is ons ry weer.

284
00:14:39,230 --> 00:14:42,600
12 is die oudste element
in ons ry, die hoof.

285
00:14:42,600 --> 00:14:46,210
10 is die nuutste element
in ons ry, ons stert.

286
00:14:46,210 --> 00:14:49,310
>> En so wanneer ons wil
om 'n element dequeue,

287
00:14:49,310 --> 00:14:52,202
ons wil die oudste element verwyder.

288
00:14:52,202 --> 00:14:52,910
So, wat doen ons?

289
00:14:52,910 --> 00:14:55,243
Wel, ons het 'n traversal wyser
wat begin by die kop,

290
00:14:55,243 --> 00:14:57,840
en ons beweeg dit so dat dit
wys na die tweede element

291
00:14:57,840 --> 00:15:02,290
van hierdie queue-- iets deur te sê trav
gelyk trav pyl volgende, byvoorbeeld,

292
00:15:02,290 --> 00:15:07,170
sou trav daar beweeg om aan te dui
15, wat, na ons dequeue 12,

293
00:15:07,170 --> 00:15:13,030
of na ons verwyder 12, sal
geword het van die destydse oudste element.

294
00:15:13,030 --> 00:15:16,360
>> Nou het ons 'n houvas op die eerste
element via die wyser hoof

295
00:15:16,360 --> 00:15:19,440
en die tweede element
via die wyser trav.

296
00:15:19,440 --> 00:15:25,170
Ons kan nou gratis kop, en dan kan ons
sê niks kom voor 15 nie.

297
00:15:25,170 --> 00:15:29,990
So kan ons 15 se vorige verander
wyser om te verwys na nul

298
00:15:29,990 --> 00:15:31,874
en ons het net beweeg die kop oor.

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

300
00:15:32,540 --> 00:15:35,840
Nou het ons suksesvol
dequeued 12, en nou is ons

301
00:15:35,840 --> 00:15:39,180
het 'n ander tou van 4 elemente.

302
00:15:39,180 --> 00:15:41,700
Dit is pretty much al
daar is om te toue,

303
00:15:41,700 --> 00:15:45,810
beide array gebaseerde en gekoppel-lys gebasseer.

304
00:15:45,810 --> 00:15:46,860
Ek is Doug Lloyd.

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

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